基于核心图增量聚类的复杂网络划分算法

张新猛; 蒋盛益

doi:10.3724/SP.J.1004.2013.01117

基于核心图增量聚类的复杂网络划分算法

doi: 10.3724/SP.J.1004.2013.01117

张新猛^,,
蒋盛益

1.
广东外语外贸大学思科信息学院广州 510006

基金项目:

国家自然科学基金(61070061), 教育部人文社会科学研究青年基金项目(11YJCZH086, 12YJCZH281, 13YJCZH258)资助

详细信息

通讯作者:
张新猛

计量
- 文章访问数: 1854
- HTML全文浏览量: 35
- PDF下载量: 1958
- 被引次数: 0
出版历程
- 收稿日期: 2012-04-16
- 修回日期: 2012-08-12
- 刊出日期: 2013-07-20

Complex Network Community Detection Based on Core Graph Incremental Clustering

ZHANG Xin-Meng^,,
JIANG Sheng-Yi

1.
Cisco School of Informatics, Guangdong University of Foreign Studies, Guangzhou 510006

Funds:

Supported by National Natural Science Foundation of China (61070061), the Youth Project of Humanity and Social Science for Ministry of Education (11YJCZH086, 12YJCZH281, 13YJCZH258)

摘要

摘要: 借鉴基于聚类的无监督入侵检测算法(Clustering-based method for the unsupervised intrusion detection, CBUID)聚类原理, 提出一种基于核心图增量聚类的社区划分算法(Clustering-based method for community detection, CBCD). 本文提出一种社区摘要构建方法, 给出节点与社区相似度的计算公式. 首先,对由少量高度数节点组成的核心网络采用现有算法进行核心社区划分, 然后,采用增量方式依据节点与社区相似度,将剩余节点划分到核心社区中. 算法复杂度主要依赖于网络规模、边的数量及划分的社区个数, 具有线性复杂度. 通过在几个典型真实网络数据集上测试, 所提算法能够有效地进行社区划分.
- 复杂网络 /
- 社区摘要 /
- 相似度 /
- 社区发现
Abstract: This paper references the principle of clustering in clustering-based method for the unsupervised intrusion detection algorithm (CBUID), and proposes a clustering-based method for community detection (CBCD). We propose a method of community summary building, and give the formula of the similarity between node and community. First, it detects communities on the core network composed of a small amount of high-degree core nodes, then partitions the remaining nodes into core community according to the similarity between the node and community incrementally. Its running time mainly depends on the network size, the number of edges and the number of communities, and our algorithm has essentially a linear time complexity. Applications on several common real networks demonstrate that this method is very effective at community detection of networks.
- Complex networks /
- community summary /
- similarity /
- community detection

HTML全文

参考文献(32)

[1]	Zhao Y P, Levina E, Zhu J. Community extraction for social networks. Proceedings of the National Academy of Sciences of the United States of America, 2011, 108(18): 7321-7326
[2]	Kelley S, Goldberg M, Magdon-Ismail M, Mertsalov K, Wallace A. Defining and discovering communities in social networks. Handbook of Optimization in Complex Networks, 2012, 57(2): 139-168
[3]	Angeles S M, Boguñá M, Sagués F. Uncovering the hidden geometry behind metabolic networks. Molecular BioSystems, 2012, 8(3): 843-850
[4]	Ino H, Kudo M, Nakamura A. Partitioning of Web graphs by community topology. In: Proceedings of the 14th International Conference on World Wide Web. New York: ACM, 2005. 661-669
[5]	Farutin V, Robison K, Lightcap E, Dancik V, Ruttenberg A, Letovsky S, Pradines J. Edge-count probabilities for the identification of local protein communities and their organization. Proteins: Structure, Function, and Bioinformatics, 2006, 62(3): 800-818
[6]	Palla G, Derényi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814-818
[7]	Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 026113
[8]	Newman M E J. Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582
[9]	Newman M E J. Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 2006, 74(3): 6104-6126
[10]	Backstrom L, Leskovec J. Supervised random walks: predicting and recommending links in social networks. In: Proceedings of the 4th ACM International Conference on Web search and Data Mining. New York, USA: ACM, 2011. 635-644
[11]	Shiga M, Takigawa I, Mamitsuka H. A spectral approach to clustering numerical vectors as nodes in a network. Pattern Recognition, 2011, 44(2): 236-251
[12]	Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E, 2004, 69(6): 6133-6138
[13]	Reichardt J, Bornholdt S. Statistical mechanics of community detection. Physical Review E, 2006, 74(1): 6110-6122
[14]	He Dong-Xiao, Zhou Xu, Wang Zuo, Zhou Chun-Guang, Wang Zhe, Jin Di. Community mining in complex networks clustering combination based genetic algorithm. Acta Automatica Sinica, 2010, 36(8): 1160-1170 (何东晓, 周栩, 王佐, 周春光, 王喆, 金弟. 复杂网络社区挖掘—基于聚类融合的遗传算法. 自动化学报, 2010, 36(8): 1160-1170)
[15]	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)
[16]	Shen Hua-Wei, Cheng Xue-Qi, Chen Hai-Qiang, Liu Yue. Information bottleneck based community detection in network. Chinese Journal of Computers, 2008, 31(4): 677-686 (沈华伟, 程学旗, 陈海强, 刘悦. 基于信息瓶颈的社区发现. 计算机学报, 2008, 31(4): 677-686)
[17]	Guo Chong-Hui, Zhang Na. Partition methods based on common neighbors matrix for the community structure in complex network. Systems Engineering - Theory & Practice, 2010, 30(6): 1077-1084 (郭崇慧, 张娜. 基于共邻矩阵的复杂网络社区结构划分方法. 系统工程理论与实践, 2010, 30(6): 1077-1084)
[18]	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)
[19]	Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(9): 2658-2663
[20]	Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Physical Review E, 2004, 70(6): 6111-6117
[21]	Jiang S Y, Song X Y, Wang H, Han J J, Li Q H. A clustering-based method for unsupervised intrusion detections. Pattern Recognition Letters, 2006, 27(7): 802-810
[22]	Deng W B, Li W, Cai X, Wang Q P. The exponential degree distribution in complex networks: non-equilibrium network theory, numerical simulation and empirical data. Physica A: Statistical Mechanics and Its Applications, 2011, 390(8): 1481-1485
[23]	Li Hui, Zhao Hai, Xu Jiu-Qiang, Li Bo, Li Peng, Wang Jia-Liang. Research on hierarchy of large-scale software macro-topology base on k-core. Acta Electronica Sinica, 2010, 38(11): 2635-2643 (李辉, 赵海, 徐久强, 李博, 李鹏, 王家亮. 基于k-核的大规模软件宏观拓扑结构层次性研究. 电子学报, 2010, 38(11): 2635-2643)
[24]	Zhang Xin, Zhao Hai, Wang Li-Fei, Li Chao. Analysis on the internet AS-level topology. Journal on Communications, 2008, 29(7): 50-61 (张昕, 赵海, 王莉菲, 李超. AS级Internet拓扑分析. 通信学报, 2008, 29(7): 50-61)
[25]	Zachary W W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977, 33(4): 452-473
[26]	Lusseau D. The emergent properties of a dolphin social network. Proceedings of the Royal Society B: Biological Sciences, 2003, 270(S2): S186-S188
[27]	Adamic L A, Glance N. The political blogosphere and the 2004 U.S. election: divided they blog. In: Proceedings of the 3rd International Workshop on Link Discovery. New York, USA: ACM, 2005. 36-43
[28]	Newman M E J. Scientific collaboration networks, I: Network construction and fundamental results. Physical Review E, 2001, 64(1): 016131
[29]	Guimerà R, Danon L, Díaz-Guilera A, Giralt F, Arenas A. Self-similar community structure in a network of human interactions. Physical Review E, 2003, 8(6): 065103
[30]	Gleiser P M, Danon L. Community structure in jazz. Advances in Complex Systems, 2003, 6(4): 565-573
[31]	Jeong H, Mason S, Barabási A L, Oltvai Z N. Lethality and centrality in protein networks. Nature, 2001, 411(6833): 41-42
[32]	Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007, 76(3): 036106