TY - GEN

T1 - Recovering a Hidden Community in a Preferential Attachment Graph

AU - Hajek, Bruce

AU - Sankagiri, Suryanarayana

N1 - Funding Information:
ACKNOWLEDGMENT This work was supported by NSF Grant CCF 14-09106.
Funding Information:
This work was supported by NSF Grant CCF 14-09106
Publisher Copyright:
© 2018 IEEE.

PY - 2018/8/15

Y1 - 2018/8/15

N2 - A message passing algorithm is derived for recovering a dense subgraph within a graph generated by a variation of the Barabasi-Albert preferential attachment model. The estimator is assumed to know the order of attachment, of the vertices. The derivation of the algorithm is based on belief propagation under an independence assumption. Two precursors to the message passing algorithm are analyzed: the first is a degree thresholding (DT) algorithm and the second is an algorithm based on the arrival times of the children (C) of a given vertex, where the children of a given vertex are the vertices that attached to it. Algorithm C significantly outperforms DT, showing it is beneficial to know the arrival times of the children, beyond simply knowing the number of them. For fixed fraction of vertices in the community, fixed number of new edges per arriving vertex, and fixed affinity between vertices in the community, the probability of error for recovering the label of a vertex is found as a function of the time of attachment, for either algorithm DT or C, in the large graph limit. By averaging over the time of attachment, the limit in probability of the fraction of label errors made over all vertices is identified, for either of the algorithms DT or C. An extended version of this paper is at arXiv 1801.06818, which also includes message passing for two symmetric communities.

AB - A message passing algorithm is derived for recovering a dense subgraph within a graph generated by a variation of the Barabasi-Albert preferential attachment model. The estimator is assumed to know the order of attachment, of the vertices. The derivation of the algorithm is based on belief propagation under an independence assumption. Two precursors to the message passing algorithm are analyzed: the first is a degree thresholding (DT) algorithm and the second is an algorithm based on the arrival times of the children (C) of a given vertex, where the children of a given vertex are the vertices that attached to it. Algorithm C significantly outperforms DT, showing it is beneficial to know the arrival times of the children, beyond simply knowing the number of them. For fixed fraction of vertices in the community, fixed number of new edges per arriving vertex, and fixed affinity between vertices in the community, the probability of error for recovering the label of a vertex is found as a function of the time of attachment, for either algorithm DT or C, in the large graph limit. By averaging over the time of attachment, the limit in probability of the fraction of label errors made over all vertices is identified, for either of the algorithms DT or C. An extended version of this paper is at arXiv 1801.06818, which also includes message passing for two symmetric communities.

UR - http://www.scopus.com/inward/record.url?scp=85052464561&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052464561&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2018.8437450

DO - 10.1109/ISIT.2018.8437450

M3 - Conference contribution

AN - SCOPUS:85052464561

SN - 9781538647806

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2097

EP - 2101

BT - 2018 IEEE International Symposium on Information Theory, ISIT 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 IEEE International Symposium on Information Theory, ISIT 2018

Y2 - 17 June 2018 through 22 June 2018

ER -