IEEE Transactions on Network Science and Engineering
IEEE Transactions on Network Science and Engineering (TNSE) is now accepting manuscript submissions. To submit your manuscript, please use the ScholarOne Manuscripts manuscript submission site. Read the full scope of TNSE
From the January-June issue
Decoding Binary Node Labels from Censored Edge Measurements: Phase Transition and Efficient Recovery
By Emmanuel Abbe, Afonso S. Bandeira, Annina Bracher, and Amit Singer
We consider the problem of clustering a graph G into two communities by observing a subset of the vertex correlations. Specifically, we consider the inverse problem with observed variables Y = BGx ⊕ Z, where BG is the incidence matrix of a graph G, x is the vector of unknown vertex variables (with a uniform prior), and Z is a noise vector with Bernoulli (ε) i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery (up to global flip) of x is possible if and only the graph G is connected, with a sharp threshold at the edge probability log (n)/n for Erdos-Renyi random graphs. The first goal of this paper is to determine how the edge probabilityp needs to scale to allow exact recovery in the presence of noise. Defining the degree rate of the graph by α = np/log(n), it is shown that exact recovery is possible if and only if α > 2/(1 - 2ε)2 + o(1/(1 - 2ε)2). In other words, 2/(1 - 2ε)2 is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. For a deterministic graph G, defining the degree rate as α = d/log(n), where d is the minimum degree of the graph, it is shown that the proposed method achieves the rate α > 4((1 + λ)/(1 - λ)2/(1 - 2ε)2 + o(1/(1 - 2ε)2), where 1-λ is the spectral gap of the graph G.
Editorials and Announcements
- We are pleased to announce that Ali Jadbabaie, a professor at University of Pennsylvania, Philadephia, has been appointed as the inaugural EIC for the IEEE Transactions on Network Science and Engineering, effective immediately.
- IEEE Transactions on Network Science and Engineering (Jan-June 2014)
- IEEE TNSE Inaugural Issue Editorial (Jan-June 2014)
Call for Papers
General Call for Papers
General TNSE call for papers. View PDF.
TNSE is financially cosponsored by:
TNSE is technically cosponsored by: