优化稳定性的多层次社团快速探测算法

Fast Multi-scale Community Detection Algorithm Based on Stability Optimization

由于现有的社团探测算法大多只能在单一的尺度上划分社团,而且运算速度比较差,因此不利于分析大规模的科技社会网络.本文提出一种新颖的多尺度社团结构快速探测算法.该方法通过优化表示社团结构统计显著性的稳定性指标函数,来寻找多个层次上具有最佳统计意义的社团结构.为了得到具体的社团归属,开发了一种只需利用马尔科夫迭代就能更新归属向量的动力学系统,使得社团归属便能够快速地收敛到最优值,因此具有较低的计算复杂性.它不需要指定具体的社团数量,便能够找到每个节点与具体社团的归属关系,因此能够自然地支持重叠社团的划分.理论分析和实验验证共同表明,该算法可以快速而准确的发现社会网络和生物网络中的各种功能社团.

Most existing community detection methods require the complete graph information, which is impractical for large-scale technological and social networks. In this paper, we propose a novel algorithm which does not embrace the universal approach but in- stead tries to focus on local ties and model multi-scale interactions in these networks. Our method optimizes the stability measure of a network and uncovers communities through a novel dynamic system converging to a local minimum by simply updating the member- ship vector with very low computational complexity. It naturally supports overlapping information by associating each node with a membership vector that describes its involvement of each community. The effectiveness and efficiency of the algorithm has been theo- retically analyzed as well as experimentaUv validated.