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

doi:10.11896/j.issn.1002-137X.2014.09.024

摘要/Abstract

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

关键词: 社团结构,复杂网络,重叠性,信息扩散,多尺度

Abstract: 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.

Key words: Community structure,Complex network,Overlapping,Information spreading,Multi-scale

李慧嘉. 基于信息扩散的多尺度重叠社团快速探测算法[J]. 计算机科学, 2014, 41(9): 125-131. https://doi.org/10.11896/j.issn.1002-137X.2014.09.024

LI Hui-jia. Fast Algorithm for Detecting Multi-scale Overlapping Community Structure Based on Information Spreading[J]. Computer Science, 2014, 41(9): 125-131. https://doi.org/10.11896/j.issn.1002-137X.2014.09.024

参考文献

[1] Barabasi A L,Albert R．Emergence of scaling in random net-works[J]．Science,1999,286(5439):509-512
[2] Newman M E J．Fast algorithm for detecting community structure in networks[J]．Phys．Rev．E,2004,69:066133
[3] Girvan M,Newman M E J．Community structure in social and biological networks[J]．Proc．Natl．Acad．Sci,2002,99(12):7821-7826
[4] Newman M E J,Girvan M．Finding and evaluating communitystructure in networks[J]．Phys．Rev．E,2004,69:026113
[5] Li H J,Zhang X S．Analysis of stability of community structure across multiple hierarchical levels[J].Europhys．Lett.,2013,103:58002
[6] Li H J,Wang Y,Wu L Y,et al．Community structure detection based on potts model and spectral characterization[J]．Europhys．Lett.,2012,97:48005
[7] Li H J,Wang Y,Wu L Y,et al.Potts model based on a Markov process computation solves the community structure problem effectively[J]．Phys．Rev．E,2012,86:016109
[8] Muff S,Rao F,Caflisch A．Local modularity measure for net-work clusterizations[J]．Phys．Rev．E,2005,72(5):056107
[9] Gregory S．Finding Overlapping Communities Using DisjointCommunity Detection Algorithms[M]∥Complex Networks．Springer Berlin Heidelberg,2009:47-61
[10] Palla G,Derenyi I,Farkas I,et al．Uncovering the overlapping community structure of complex networks in nature and society[J]．Nature,2005,435:814-818
[11] 沈华伟,程学旗,陈海强,等．基于信息瓶颈的社区发现[J]．计算机学报,2008,31(4):677-686
[12] Raghavan U,Albert R,Kumara S．Near linear time algorithm to detect community structures in large-scale networks[J]．Phys．Rev．E,2007,76(3):036106
[13] Pujol J M,Bejar J,Delgado J．Clustering algorithm for determining community structure in large networks[J]．Phys．Rev．E,2006,74(1):016107
[14] 王观玉．基于聚类的复杂网络社团发现算法[J]．计算机工程,2011,37(10):58-60
[15] 杨博,刘大有,金弟,等．复杂网络聚类方法[J]．软件学报,2009,20(1):54-66
[16] Noh J,Rieger H．Random walks on complex networks[J]．Phys．Rev．Lett.,2004,92(11):118701
[17] Lai D,Lu H,Nardini C．Enhanced modularity-based community detection by random walk network preprocessing[J]．Phys．Rev．E,2010,81(6):066118
[18] Ravasz E,Barabasi A L．Hierarchical organization in complexnetworks[J]．Phys．Rev．E,2003,67:026112
[19] Baras J S,Hovareshti P．Efficient and robust communication to-pologies for distributed decision making in networked systems[C]∥Proceedings of 47^th IEEE Conference on Decision and Control．2008:2973-2978
[20] Danon L,Duch J,Guilera D,et al.Comparing community structure identification[J]．J．Stat．Mech.,2005,29:09008
[21] Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large networks[J]．J．Stat．Mech.,2008,10:10008
[22] Rosvall M,Bergstrom C T．Maps of random walks on complex networks reveal community structure[J]．Proc．Natl．Acad．Sci.,2008,105(4):1118-1123
[23] Zachary W W．An information flow model for conflict and fission in small groups[J]．Journal of Anthropological Research,1977,33:452-473
[24] Huh W,et al．Global analysis of protein localization in budding yeast[J]．Nature,2003,425:686-691
[25] Jansen R,Gerstein M．Analyzing protein function on a genomic scale:the importance of gold-standard positives and negatives for network prediction[J]．Current Opinion in Microbiology,2004,7:535-545
[26] Ruepp A,et al．The FunCat,a functional annotation scheme for systematic classification of proteins from whole genome[J]．Nucleic Acids Res,2004,32:5539-5545

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed