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 -