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

Featured articleWe 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.

download PDF View the PDF of this article       csdl View this issue in the digital library


Editorials and Announcements

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.

Editorials



Call for Papers

General Call for Papers

General TNSE call for papers. View PDF.


TNSE is financially cosponsored by:

IEEE Computer SocietyIEEE Circuits and Systems Society IEEE Comunications Society

 

TNSE is technically cosponsored by:

IEEE Control Systems SocietyIEEE Signal Processing Society