基于信息扩散的多尺度重叠社团快速探测算法

Fast Algorithm for Detecting Multi-scale Overlapping Community Structure Based on Information Spreading

现有的社团分析方法由于需要网络的全局信息,并且只能在单一的尺度上划分社团,因此不利于分析大规模的科技社会网络。提出了一种新颖的多尺度社团结构快速探测算法,其只利用网络的局域信息就可以模拟复杂网络中的多尺度的社团结构。该方法通过优化表示网络统计显著性的拓扑熵,来寻找有最佳统计意义的社团结构。为了得到具体的社团归属,算法只需利用局部信息的扩散来更新归属向量便能够收敛到局部极小值,因此具有较低的计算复杂性。它不需要指定具体的社团数量,便能够找到每个节点与具体社团的归属关系,从而能够自然地支持模糊社团的划分。理论分析和实验验证共同表明,该算法可以快速而准确地发现社会网络和生物网络中的各种功能社团。

Most existing community detection methods require the complete graph information, thus is impractical for large-scale technological and social networks. This paper proposed a novel algorithm for the fast detection of multi-scale overlapping community structure. It does not embrace the universal approach but instead tries to focus on local ties and model multi-scale interactions in these networks. It identifies leaders and modules around these leaders using local information. It naturally supports overlapping information by associating each node with a membership vector that describes its involvement of each community. Our method for the first time optimizes the topological entropy of a network and uncovers communities through a novel dynamic system converging to a local minimum by simply updating the membership vector with very low computational complexity. Both theoretical analysis and experiment show that the algorithm can detect communities in social and biological networks fast and accurately.