检索结果-内蒙古大学图书馆

Recovering Asymmetric Communities in the Stochastic Block Model

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2018年第3期5卷 237-246页

作者： Caltagirone, Francesco Lelarge, Marc Miolane, Leo PSL Res Univ CNRS Ecole Normale Super Dept Informat ENS F-75005 Paris France

We consider the sparse stochastic block model in the case where the degrees are uninformative. The case where the two communities have approximately the same size has been extensively studied and we concentrate here on the community detection problem in the case of unbalanced communities. In this setting, spectral algorithms based on the non-backtracking matrix are known to solve the community detection problem (i.e., do strictly better than a random guess) when the signal is sufficiently large namely above the so-called Kesten-Stigum threshold. In this regime and when the average degree tends to infinity, we show that if the community of a vanishing fraction of the vertices is revealed, then a local algorithm (belief propagation) is optimal down to Kesten-Stigum threshold and we quantify explicitly its performance. Below the Kesten-Stigum threshold, we show that, in the large degree limit, there is a second threshold called the spinodal curve below which, the community detection problem is not solvable. The spinodal curve is equal to the Kesten-Stigum threshold when the fraction of vertices in the smallest community is above p* = 1/2 - 1/2 root 3, so that the Kesten-Stigum threshold is the threshold for solvability of the community detection in this case. However when the smallest community is smaller than p*, the spinodal curve only provides a lower bound on the threshold for solvability. In the regime below the Kesten-Stigum bound and above the spinodal curve, we also characterize the performance of best local algorithms as a function of the fraction of revealed vertices. Our proof relies on a careful analysis of the associated reconstruction problem on trees which might be of independent interest. In particular, we show that the spinodal curve corresponds to the reconstruction threshold on the tree.

关键词： Network theory communities network clustering message-passing algorithms statistical learning

来源：评论

学校读者我要写书评

暂无评论

Analysis of the Min-Sum Algorithm for Packing and Covering Problems via Linear Programming

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2015年第10期61卷 5295-5305页

作者： Even, Guy Halabi, Nissim Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

message-passing algorithms based on belief-propagation (BP) are successfully used in many applications, including decoding error correcting codes and solving constraint satisfaction and inference problems. The BP-based algorithms operate over graph representations, called factor graphs, that are used to model the input. Although in many cases, the BP-based algorithms exhibit impressive empirical results, not much has been proved when the factor graphs have cycles. This paper deals with packing and covering integer programs in which the constraint matrix is zero-one, the constraint vector is integral, and the variables are subject to box constraints. We study the performance of the min-sum algorithm when applied to the corresponding factor graph models of packing and covering linear programmings (LPs). We compare the solutions computed by the min-sum algorithm for packing and covering problems to the optimal solutions of the corresponding LP relaxations. In particular, we prove that if the LP has an optimal fractional solution, then for each fractional component, the minsum algorithm either computes multiple solutions or the solution oscillates below and above the fraction. This implies that the min-sum algorithm computes the optimal integral solution only if the LP has a unique optimal solution that is integral. The converse is not true in general. For a special case of packing and covering problems, we prove that if the LP has a unique optimal solution that is integral and on the boundary of the box constraints, then the min-sum algorithm computes the optimal solution in pseudopolynomial time. Our results unify and extend recent results for the maximum weight matching problem and for the maximum weight independent set problem.

关键词： Belief propagation (BP) message-passing algorithms min-sum algorithm max-product algorithm dynamic programming linear programming (LP) combinatorial optimization packing problems covering problems factor graphs graph cover

来源：评论

学校读者我要写书评

暂无评论

On Decoding Irregular Tanner Codes With Local-Optimality Guarantees

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第1期60卷 191-211页

作者： Halabi, Nissim Even, Guy Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

We consider decoding of binary linear Tanner codes using message-passing iterative decoding and linear-programming (LP) decoding in memoryless binary-input output-symmetric (MBIOS) channels. We present new certificates that are based on a combinatorial characterization for the local optimality of a codeword in irregular Tanner codes with respect to any MBIOS channel. This characterization is a generalization of (Arora et al., Proc. ACM Symp. Theory of Computing, 2009) and (Vontobel, Proc. Inf. Theory and Appl. Workshop, 2010) and is based on a conical combination of normalized weighted subtrees in the computation trees of the Tanner graph. These subtrees may have any finite height (even equal or greater than half of the girth of the Tanner graph). In addition, the degrees of local-code nodes in these subtrees are not restricted to two (i.e., these subtrees are not restricted to skinny trees). We prove that local optimality in this new characterization implies maximum-likelihood (ML) optimality and LP optimality, and show that a certificate can be computed efficiently. We also present a new message-passing iterative decoding algorithm, called normalized weighted min-sum (NWMS). NWMS decoding is a belief-propagation (BP) type algorithm that applies to any irregular binary Tanner code with single parity-check local codes (e. g., low-density and high-density parity-check codes). We prove that if a locally optimal codeword with respect to height parameter exists (whereby notably is not limited by the girth of the Tanner graph), then NWMS decoding finds this codeword in iterations. The decoding guarantee of the NWMS decoding algorithm applies whenever there exists a locally optimal codeword. Because local optimality of a codeword implies that it is the unique ML codeword, the decoding guarantee also provides an ML certificate for this codeword. Finally, we apply the new local-optimality characterization to regular Tanner codes, and prove lower bounds on the noise threshol

关键词： Error bounds factor graphs graph cover IDPC codes linear programming (LP) decoding local optimality max-product algorithm maximum-likelihood (ML) certificate memoryless binary-input output-symmetric (MBIOS) channel message-passing algorithms min-sum algorithm Tanner codes thresholds

来源：评论

学校读者我要写书评

暂无评论

Learning Factorizations in Estimation of Distribution algorithms Using Affinity Propagation

引用

EVOLUTIONARY COMPUTATION 2010年第4期18卷 515-546页

作者： Santana, Roberto Larranaga, Pedro Lozano, Jose A. Univ Politecn Madrid Fac Informat E-28660 Madrid Spain Univ Politecn Madrid Dept Inteligencia Artificial E-28660 Madrid Spain Univ Basque Country Intelligent Syst Grp Dept Comp Sci & Artificial Intelligence San Sebastian 20018 Spain

Estimation of distribution algorithms (EDAs) that use marginal product model factorizations have been widely applied to a broad range of mainly binary optimization problems. In this paper, we introduce the affinity propagation EDA (AffEDA) which learns a marginal product model by clustering a matrix of mutual information learned from the data using a very efficient message-passing algorithm known as affinity propagation. The introduced algorithm is tested on a set of binary and nonbinary decomposable functions and using a hard combinatorial class of problem known as the HP protein model. The results show that the algorithm is a very efficient alternative to other EDAs that use marginal product model factorizations such as the extended compact genetic algorithm (ECGA) and improves the quality of the results achieved by ECGA when the cardinality of the variables is increased.

关键词： Estimation of distribution algorithms affinity propagation factorized distribution algorithms message-passing algorithms marginal product models factorizations extended compact genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Distributed algorithms for Spectrum Access in Cognitive Radio Relay Networks

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2012年第10期30卷 1947-1957页

作者： Shamaiah, Manohar Lee, Sang Hyun Vishwanath, Sriram Vikalo, Haris Univ Texas Austin Dept Elect & Comp Engn Austin TX 78712 USA

We develop distributed algorithms for efficient spectrum access strategies in cognitive radio relay networks. In our setup, primary users permit secondary users access to the resource (spectrum) as long as they consent to aiding the primary users as relays in addition to transmitting their own data. Given a pool of primary and secondary users, we desire to optimize overall network utility by determining the best configuration/pairing of secondary users with primary users. This optimization can be stated in a form similar to the maximum weighted matching problem. Given such formulation, we develop an algorithm based on affinity propagation technique that is completely distributed in its structure. We demonstrate the convergence of the developed algorithm and show that it performs close to the optimal centralized scheme.

关键词： Cognitive radios Spectrum access strategy Distributed algorithms message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Convergence of Min-Sum message passing for Quadratic Optimization

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第5期55卷 2413-2423页

作者： Moallemi, Ciamac C. Van Roy, Benjamin Columbia Univ Grad Sch Business New York NY 10025 USA Stanford Univ Dept Management Sci Stanford CA 94305 USA Stanford Univ Dept Engn & Elect Engn Stanford CA 94305 USA

We establish the convergence of the min-sum message passing algorithm for minimization of a quadratic objective function given a convex decomposition. Our results also apply to the equivalent problem of the convergenc... 详细信息

关键词： Decentralized optimization message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Bootstrap decoding of low-density parity-check codes

引用

IEEE COMMUNICATIONS LETTERS 2002年第9期6卷 391-393页

作者： Nouh, A Banihashemi, AH Carleton Univ Dept Syst & Comp Engn BCWS Ctr Ottawa ON K1S 5B6 Canada

An initial bootstrap step for the decoding of low-density parity-check (LDPC) codes is proposed. Decoding is initiated by first erasing a number of less reliable bits. New values and reliabilities are then assigned to erasure bits by passing messages from nonerasure bits through the reliable check equations. The bootstrap step is applied to the weighted bit-flipping algorithm to decode a number of LDPC codes. Large improvements in both performance and complexity are observed.

关键词： bootstrap decoding iterative decoding low-density parity-check (LDPC) codes message-passing algorithms message-passing schedule weighted bit-flipping algorithm

来源：评论

学校读者我要写书评

暂无评论

Comments on Successive Relaxation for Decoding of LDPC Codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2009年第10期57卷 2846-2848页

作者： Xiao, Hua Banihashemi, Amir H. Carleton Univ Dept Syst & Comp Engn Broadband Commun & Wireless Syst BCWS Ctr Ottawa ON K1S 5B6 Canada

The application of successive relaxation (SR) to the fixed-point problem associated with the iterative decoding of low-density parity-check (LDPC) codes was proposed by Hemati et al. The simulation results presented by Hemati et al. for the SR version of belief propagation (BP) in the likelihood ratio (LR) domain and that of min-sum (MS) in the log-liketihood ratio (LLR) domain are based on the assumption of all-zero codeword transmission. This assumption however results in erroneous error rates when SR is applied in the LR domain. Here, we correct the simulation results reported by Hemati et al. for SR-BP in the LR domain.. Furthermore, we investigate the performance of SR-BP and SR-MS in the LLR and LR domains, respectively. The results for a binary input additive white Gaussian noise (BIAWGN) channel show that for both BP and MS, the application of SR in the two domains of LR and LLR results in different error correcting performance. In particular, for the tested codes, it is shown that among the four algorithms, SR-MS-LLR has the best performance. It outperforms standard MS and BP by up to about 0.6 dB and 0.3dB, respectively, offering an attractive solution in terms of performance/complexity tradeoff.

关键词： Successive relaxation low-density parity-check (LDPC) codes belief propagation (BP) algorithm min-sum (MS) algorithm iterative decoding message-passing algorithms successive substitution

来源：评论

学校读者我要写书评

暂无评论

Averting Cascading Failures in Networked Infrastructures: Poset-Constrained Graph algorithms

引用

IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING 2018年第4期12卷 733-748页

作者： Yu, Pei-Duo Tan, Chee Wei Fu, Hung-Lin City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China City Univ Hong Kong Comp Sci Hong Kong Hong Kong Peoples R China Natl Chiao Tung Univ Inst Combinator & Its Applicat Hsinchu 300 Taiwan Natl Chiao Tung Univ Dept Appl Math Hsinchu 300 Taiwan

Cascading failures in critical networked infrastructures that result even from a single source of failure often lead to rapidly widespread outages as witnessed in the 2013 Northeast blackout in Northern America. The ensuing problem of containing future cascading failures by placement of protection or monitoring nodes in the network is complicated by the uncertainty of the failure source and the missing observation of how the cascading might unravel, be it the past cascading failures or the future ones. This paper examines the problem of minimizing the outage when a cascading failure from a single source occurs. A stochastic optimization problem is formulated where a limited number of protection nodes, when placed strategically in the network to mitigate systemic risk, can minimize the expected spread of cascading failure. We propose the vaccine centrality, which is a network centrality based on the partially ordered sets (poset) characteristics of the stochastic program and distributed message-passing, to design efficient approximation algorithms with provable approximation ratio guarantees. In particular, we illustrate how the vaccine centrality and the poset-constrained graph algorithms can be designed to tradeoff between complexity and optimality, as illustrated through a series of numerical experiments. This paper points toward a general framework of network centrality as statistical inference to design rigorous graph analytics for statistical problems in networks.

关键词： Cascading failure viral spreading graph theory and algorithms large-scale stochastic optimization message-passing algorithms approximation algorithm network centrality

来源：评论

学校读者我要写书评

暂无评论

Consensus propagation

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第11期52卷 4753-4766页

作者： Moallemi, Ciamac C. Van Roy, Benjamin Stanford Univ Dept Elect Engn Stanford CA 94305 USA Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

We propose consensus propagation, an asynchronous distributed protocol for averaging numbers across a network. We establish convergence, characterize the convergence rate for regular graphs, and demonstrate that the protocol exhibits better scaling properties than painvise averaging, an alternative that has received much recent attention. Consensus propagation can be viewed as a special case of belief propagation, and our results contribute to the belief propagation literature. In particular, beyond singly-connected graphs, there are very few classes of relevant problems for which belief propagation is known to converge.

关键词： belief propagation distributed averaging distributed consensus distributed signal processing Gaussian Markov random fields max-product algorithm message-passing algorithms min-sum algorithm sum-product algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：