Recovering a Hidden Community in a Preferential Attachment Graph
share
A message passing algorithm (MP) is derived for recovering a dense subgraph within a graph generated by a variation of the Barabási-Albert preferential attachment model. The estimator is assumed to know the arrival times, or 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. C significantly outperforms DT, showing it is beneficial to know the arrival times of the children, beyond simply knowing the number of them. It is shown that for a fixed fraction of vertices in the community ρ, fixed number of new edges per arriving vertex m, and fixed affinity between vertices in the community β, the fraction of label errors for either of the algorithms DT or C, or converges as T→∞.
READ FULL TEXT