Community Recovery in a Preferential Attachment Graph
Community Recovery in a Preferential Attachment Graph
复制标题
DOI：
10.1109/tit.2019.2927624
复制
发表时间：
2019-11-01
影响因子：
2.5
通讯作者：
Sankagiri, Suryanarayana
中科院分区：
文献类型：
--
作者：
Hajek, Bruce;Sankagiri, Suryanarayana
一个消息传递算法的Barabsi-Albert偏好连接模型的变化所产生的图中恢复社区。假设估计器知道顶点的到达时间或附着顺序。该算法的推导是基于独立性假设下的置信传播。分析了消息传递算法的两个前身：一个是度阈值（DT）算法，另一个是基于给定顶点的子节点（C）到达时间的算法，其中给定顶点的子节点是与该顶点相连的顶点，通过对这两种算法性能的比较，发现知道子节点的到达时间而不仅仅是知道子节点的数目是有益的.一个顶点的正确分类概率由在它之前到达的顶点所占的比例渐近地确定.给出了算法C的两个扩展：第一个扩展是基于固定顶点集合的子节点的联合似然，它有时可以用来作为消息传递算法的种子.二是消息传递算法。给出了仿真结果。
A message passing algorithm is derived for recovering communities within a graph generated by a variation of the Barabsi-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. Comparison of the performance of the algorithms shows it is beneficial to know the arrival times, not just the number, of the children. The probability of correct classification of a vertex is asymptotically determined by the fraction of vertices arriving before it. Two extensions of Algorithm C are given: the first is based on joint likelihood of the children of a fixed set of vertices; it can sometimes be used to seed the message passing algorithm. The second is the message passing algorithm. Simulation results are given.