复杂网络的局部社团结构挖掘算法

袁超; 柴毅

doi:10.3724/SP.J.1004.2014.00921

复杂网络的局部社团结构挖掘算法

doi: 10.3724/SP.J.1004.2014.00921

袁超¹,
柴毅^1,2

1.
重庆大学自动化学院重庆 400044;
2.
重庆大学输配电装备及系统安全与新技术国家重点实验室重庆 400044

基金项目:

国家自然科学基金（61374135）资助

详细信息

作者简介:
袁超重庆大学自动化学院博士研究生. 主要研究方向为复杂网络，数据挖掘.E-mail：yuan home@163.com

计量
- 文章访问数: 2290
- HTML全文浏览量: 71
- PDF下载量: 1365
- 被引次数: 0
出版历程
- 收稿日期: 2013-03-26
- 修回日期: 2013-08-13
- 刊出日期: 2014-05-20

Method for Local Community Mining in the Complex Networks

YUAN Chao¹,
CHAI Yi^1,2

1.
School of Automation, Chongqing University, Chongqing 400044;
2.
State Key Laboratory of Power Transmission Equipment and System Security and New Technology, Chongqing University, Chongqing 400044

Funds:

Supported by National Natural Science Foundation of China (61374135)

摘要

摘要: 挖掘复杂网络的社团结构对研究复杂系统具有重要的理论和实践意义.其中，相较于全局社团，局部社团的挖掘难度更大，相关文献更少.现有的局部社团挖掘算法大都精度较低、稳定性较差.本文提出了一个有效的局部社团挖掘算法，称为内外夹推法（Shell interception and core expansion，SICE）.算法有两个创新之处：1）将节点相似度模型引入到局部社团挖掘算法中（节点相似度模型在局部社团挖掘中较难应用），并提出了“一次一个子图”的社团扩展模式；2）提出了一种“内外夹推”的思想.这两个创新使SICE算法摆脱了缺乏网络全局信息的困扰，并解决了以往算法的一个致命缺陷，从而使算法具有很高的精度和稳定性.通过理论分析和实验比较，证明SICE算法要远好于当前的同类算法，甚至不逊色于性能较好的全局社团挖掘算法.
- 复杂网络 /
- 局部社团 /
- 数据挖掘 /
- 聚类
Abstract: Community structure detection bears both theoretical and practical significance for the study of complex systems. Generally speaking, the local community detection is relatively a more difficult problem than the global community detection. So up to now, the related researches are still slow progress. And there are many defects existing in the previous local community detection algorithms, such as low precision and poor stability. In this paper, a local community detection algorithm, which is called shell interception and core expansion (SICE), has been proposed. There are two innovations in this algorithm: 1) A node similarity model is introduced into this algorithm, and a community expansion mode "one subgraph at a time" is proposed; 2) An effective method which is named "shell interception and core expansion" is proposed. By these two innovations, the SICE algorithm has solved the problem of missing global network information, and avoided a fatal weakness of the previous algorithms. Theoretical analysis and experiments all illustrate that the SICE algorithm has high precision and stability, and it outperforms the previous algorithms.
- Complex network /
- local community structure /
- data mining /
- clustering

HTML全文

参考文献(31)

[1]	Jin Di, Liu Jie, Yang Bo, He Dong-Xiao, Liu Da-You. Genetic algorithm with local search for community detection in large-scale complex networks. Acta Automatica Sinica, 2011, 37(7): 873-882(金弟, 刘杰, 杨博, 何东晓, 刘大有. 局部搜索与遗传算法结合的大规模复杂网络社区探测. 自动化学报, 2011, 37(7): 873-882)
[2]	Panagiotakis C, Papadakis H, Grinias E, Komodakis N, Fragopoulou P, Tziritas G. Interactive image segmentation based on synthetic graph coordinates. Pattern Recognition, 2013, 46(11): 2940-2952
[3]	Hu D D, Ronhovde P, Nussinov Z. Replica inference approach to unsupervised multiscale image segmentation. Physical Review E, 2012, 85(1): 016101
[4]	Zhang Z F, Li Q D, Zeng D, Gao H. User community discovery from multi-relational networks. Decision Support Systems, 2013, 54(2): 870-879
[5]	Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826
[6]	Zhang Z Y. Community structure detection in complex networks with partial background information. Europhysics Letters, 2013, 101(4): 48005
[7]	Yang Bo, Liu Jie, Liu Da-You. A random network ensemble model based generalized network community mining algorithm. Acta Automatica Sinica, 2012, 38(5): 812-822(杨博, 刘杰, 刘大有. 基于随机网络集成模型的广义网络社区挖掘算法. 自动化学报, 2012, 38(5): 812-822)
[8]	Yuan Chao, Chai Yi. Group similarity based algorithm for network community structure detection. Acta Physica Sinica, 2012, 61(21): 539-547(袁超, 柴毅. 基于簇相似度的网络社团结构探测算法. 物理学报, 2012, 61(21): 539-547)
[9]	Liu Xu, Yi Dong-Yun. Complex network community detection by local similarity. Acta Automatica Sinica, 2011, 37(12): 1520-1529(刘旭, 易东云. 基于局部相似性的复杂网络社区发现方法. 自动化学报, 2011, 37(12): 1520-1529)
[10]	Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814-818
[11]	Huang Fa-Liang, Xiao Nan-Feng. Discovering overlapping communities based on line graph and PSO. Acta Automatica Sinica, 2011, 37(9): 1140-1144(黄发良, 肖南峰. 基于线图与PSO的网络重叠社区发现. 自动化学报, 2011, 37(9): 1140-1144)
[12]	Bassett D S, Porter M A, Wymbs N F, Grafton S T, Carlson J M, Mucha P J. Robust detection of dynamic community structure in networks. Chaos, 2013, 23(1): 013142
[13]	Chen Z Z, Hendrix W, Samatova N F. Community-based anomaly detection in evolutionary networks. Journal of Intelligent Information Systems, 2012, 39(1): 59-85
[14]	Clauset A. Finding local community structure in networks. Physical Review E, 2005, 72(2): 026132
[15]	Bagrow J P, Bollt E M. Local method for detecting communities. Physical Review E, 2005, 72(4): 046108
[16]	Luo F, Wang J Z, Promislow E. Exploring local community structures in large networks. Web Intelligence and Agent Systems, 2008, 6(4): 387-400
[17]	Chen J Y, Zaiane O R, Goebel R. Local community identification in social networks. In: Proceedings of the 2009 International Conference on Advances in Social Network Analysis and Mining. Athens, Greek: IEEE, 2009. 237-242
[18]	Chen Q, Wu T T, Fang M. Detecting local community structures in complex networks based on local degree central nodes. Physica A: Statistical Mechanics and Its Applications, 2013, 392(3): 529-537
[19]	Lü L Y, Zhou T. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and Its Applications, 2011, 390(6): 1150-1170
[20]	Salton G, McGill M J. Introduction to Modern Information Retrieval. New York: McGraw-Hill, 1983
[21]	Yuan C, Chai Y, Wei S B. Feature analysis and modeling of the network community structure. Communications in Theoretical Physics, 2012, 58(4): 604-612
[22]	Katz L. A new status index derived from sociometric analysis. Psychometrika, 1953, 18(1): 39-43
[23]	Brin S, Page L. The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 1998, 30(1-7): 107-117
[24]	Lü L Y, Jin C H, Zhou T. Similarity index based on local paths for link prediction of complex networks. Physical Review E, 2009, 80(4): 046122
[25]	Liu W P, Lü L Y. Link prediction based on local random walk. Europhysics Letters, 2010, 89(5): 58007
[26]	Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Physical Review E, 2004, 70(6): 066111
[27]	Zachary W W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977, 33(4): 452-473
[28]	Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405
[29]	Newman M E J. Modularity and community structure in networks. Proceedings of National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582
[30]	Newman M E J. Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 2006, 74(3): 036104
[31]	Strehl A, Ghosh J. Cluster ensembles——a knowledge reuse framework for combining multiple partitions. Journal on Machine Learning Research, 2002, 3: 583-617