Community structure detection based on node similarity in complex networks

doi:10.11772/j.issn.1001-9081.2015.05.1213

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (5): 1213-1217.DOI: 10.11772/j.issn.1001-9081.2015.05.1213

Previous Articles Next Articles

Community structure detection based on node similarity in complex networks

LIANG Zongwen^1,2, YANG Fan¹, LI Jianping¹

1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China;
2. Department of Electrical and Computer Engineering, Rutgers, The State University of New Jersey, Piscataway New Jersey 08854, USA

Received:2014-12-08 Revised:2014-12-29 Online:2015-05-10 Published:2015-05-14

基于节点相似性度量的社团结构划分方法

梁宗文^1,2, 杨帆¹, 李建平¹

1. 电子科技大学计算机科学与工程学院, 成都 611731;
2. Department of Electrical and Computer Engineering, Rutgers, The State University of New Jersey, Piscataway 08854, USA

通讯作者: 梁宗文
作者简介:梁宗文(1985-),男,四川广元人,博士研究生,主要研究方向:网络信息流控制、大数据、网络安全; 杨帆(1987-),男,四川简阳人,博士研究生,主要研究方向:生物特征识别、图像处理; 李建平(1964-),男,湖南祁阳人,教授,博士,主要研究方向:小波分析、生物特征识别、信息安全.
基金资助:
国家自然科学基金资助项目(61370073);国家建设高水平大学留学项目(201306070037).

Abstract

Abstract:

Concerning the problem that finding community structure in complex network is very complex, a community discovery algorithm based on node similarity was proposed. The basic idea of this algorithm was that node pairs with higher similarity had more posibility to be grouped into the same community. Integrating local and global similarity, it constructed a similarity matrix which each element represents the similarity of a pair of nodes, then merged nodes which have the most similarity to the same community. The experimental results show that the proposed algorithm can get the correct community structure of networks, and achieve better performance than Label Propagation Algorithm (LPA), GN (Girvan-Newman) and CNM (Clauset-Newman-Moore) algorithms in community detection.

Key words: node similarity, community detection, community structure, complex network

摘要：

针对复杂网络结构划分过程复杂、准确性差的问题,定义了节点全局和局部相似性衡量指标,并构建节点的相似性矩阵,提出一种基于节点相似性度量的社团结构划分算法.其基本思路是将节点(或社团)按相似性合并条件划分到同一个社团中,如果合并后的节点(或社团)仍然满足相似性合并条件,则继续合并,直到所有节点都得到准确的社团划分.实验结果表明,所提算法能成功正确地划分出真实网络中的社团结构, 性能比标签传播算法(LPA)、GN(Girvan-Newman)、CNM(Clauset-Newman-Moore)等算法优秀,能有效提高结果的准确性和鲁棒性.

关键词: 节点相似性, 社团划分, 社团结构, 复杂网络

CLC Number:

TP393
N945.1

LIANG Zongwen, YANG Fan, LI Jianping. Community structure detection based on node similarity in complex networks[J]. Journal of Computer Applications, 2015, 35(5): 1213-1217.

梁宗文, 杨帆, 李建平. 基于节点相似性度量的社团结构划分方法[J]. 计算机应用, 2015, 35(5): 1213-1217.

References

[1] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.
[2] ZHANG C,SHEN H. Modularity for community structure in complex networks based on spectral method[J]. Systems Engineering Theory and Practice,2013, 33(5): 1231-1239.(张聪, 沈惠璋. 基于谱方法的复杂网络中社团结构的模块度[J]. 系统工程理论与实践, 2013, 33(5): 1231-1239.)
[3] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3): 036106.
[4] YUAN C, CHAI Y. Group similarity based algorithm for network community structure detection[J]. Acta Physica Sinica, 2012, 61(21): 218901.
[5] WANG X, ZHAO Z.Partitioning community structure in complex networks based on node dependent degree[J]. Acta Physica Sinica, 2014,63(17): 178901.(王兴元,赵仲祥.基于节点间依赖度的社团结构划分方法[J].物理学报,2014,63(17): 178901.)
[6] LYU T,XIE W,ZHENG W, et al. Analysis of community evaluation criterion and discovery algorithm of weighted complex network[J]. Acta Physica Sinica, 2012, 61(21): 210511.(吕天阳, 谢文艳, 郑纬民, 等. 加权复杂网络社团的评价指标及其发现算法分析[J]. 物理学报, 2012, 61(21): 210511.)
[7] LIANG Z, LI J, YANG F, et al. Detecting community structure using label propagation with consensus weight in complex network[J]. Chinese Physics B, 2014, 23(9): 098902.
[8] LIANG Z, PETROPULU A, YANG F, et al. Constant community discovery in network based on consensus clustering[J]. International Journal of Modern Physics B, 2014, 28(19): 1450126.
[9] PAN Y, LI D, LIU J, et al. Detecting community structure in complex networks via node similarity[J]. Physica A: Statistical Mechanics and its Applications, 2010, 389(14): 2849-2857.
[10] CHEN J, GEYER W, DUGAN C, et al. Make new friends, but keep the old: recommending people on social networking sites[C]// Proceedings of the 2009 SIGCHI Conference on Human Factors in Computing Systems. New York: ACM, 2009: 201-210.
[11] ZHANG Y, WANG J, WANG Y, et al. Parallel community detection on large networks with propinquity dynamics[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 997-1006.
[12] LOU H, LI S, ZHAO Y. Detecting community structure using label propagation with weighted coherent neighborhood propinquity[J]. Physica A: Statistical Mechanics and its Applications, 2013, 392(14): 3095-3105.
[13] SYMEONIDIS P, TIAKAS E, MANOLOPOULOS Y. Transitive node similarity for link prediction in social networks with positive and negative links[C]// Proceedings of the 4th ACM Conference on Recommender Systems. New York: ACM, 2010: 183-190.
[14] PAN J, YANG H, FALOUTSOS C, et al. Automatic multimedia cross-modal correlation discovery[C]// Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2004: 653-658.
[15] JEH G, WIDOM J. SimRank: a measure of structural-context similarity[C]// Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2002: 538-543.
[16] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[17] DANON L, DIAZ-GUILERA A, DUCH J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005(9): P09008.
[18] JOHNSON D B. A note on Dijkstra's shortest path algorithm[J]. Journal of the ACM, 1973, 20(3): 385-388.
[19] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4): 046110.
[20] LIU X, MURATA T. Evaluating community structure in bipartite networks[C]// Proceedings of the 2010 IEEE 2nd International Conference on Social Computing. Piscataway: IEEE, 2010: 576-581.
[21] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[22] LUSSEAU D. The emergent properties of a dolphin social network[J]. Proceedings of the Royal Society of London, Series B: Biological Sciences, 2003, 270(S2): 186-188.
[23] LUSSEAU D, NEWMAN M E J. Identifying the role that animals play in their social networks[J]. Proceedings of the Royal Society of London,Series B: Biological Sciences, 2004, 271(S6): 477-481.
[24] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.
[25] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582.
[26] CAFIERI S, HANSEN P, LIBERTI L. Locally optimal heuristic for modularity maximization of networks[J]. Physical Review E, 2011, 83(5): 056105.
[27] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111.
[28] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008.

Community structure detection based on node similarity in complex networks

基于节点相似性度量的社团结构划分方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	CAI Biao, LI Ruicen, WU Yuanyuan. Impact and enhancement of similarity features on link prediction [J]. Journal of Computer Applications, 2021, 41(9): 2569-2577.
[2]	LI Yafang, LIANG Ye, FENG Weiwei, ZU Baokai, KANG Yujian. Deep network embedding method based on community optimization [J]. Journal of Computer Applications, 2021, 41(7): 1956-1963.
[3]	LI Ping, WANG Fen, CHEN Qidong, SUN Jun. Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem [J]. Journal of Computer Applications, 2021, 41(3): 803-811.
[4]	Jicheng CHEN, Hongchang CHEN. Community detection method based on tensor modeling and evolutionary K-means clustering [J]. Journal of Computer Applications, 2021, 41(11): 3120-3126.
[5]	LI Chunying, TANG Yong, XIAO Zhenghong, LI Tiansong. Influential scholar recommendation model in academic social network [J]. Journal of Computer Applications, 2020, 40(9): 2594-2599.
[6]	LUO Xiangyu, LI Jianan, LUO Xiaoxia, WANG Jia. Improved community evolution relationship analysis method for dynamic graphs [J]. Journal of Computer Applications, 2020, 40(8): 2313-2318.
[7]	ZHENG Wenping, YUE Xiangdou, YANG Gui. Improved label propagation algorithm based on random walk [J]. Journal of Computer Applications, 2020, 40(12): 3423-3429.
[8]	LI Shasha, LIANG Dongyang, YU Jie, JI Bin, MA Jun, TAN Yusong, WU Qingbo. Research team mining algorithm based on teacher-student relationship [J]. Journal of Computer Applications, 2020, 40(11): 3198-3202.
[9]	CHENG Qiwei, CHEN Qimai, HE Chaobo, LIU Hai. Overlapping community detection method based on improved symmetric binary nonnegative matrix factorization [J]. Journal of Computer Applications, 2020, 40(11): 3203-3210.
[10]	LIU Yuyang, LI Longjie, SHAN Na, CHEN Xiaoyun. Link prediction method fusing clustering coefficients [J]. Journal of Computer Applications, 2020, 40(1): 28-35.
[11]	XIE Lixia, WEI Ruixin. Dynamic trust evaluation method for IoT nodes [J]. Journal of Computer Applications, 2019, 39(9): 2597-2603.
[12]	WANG Xilong, WANG Jicheng, LUO Cheng, TIAN Xiuxia. Evolutionary game model under synergistic effect of time scale and selection preference [J]. Journal of Computer Applications, 2019, 39(6): 1824-1828.
[13]	ZHANG Xi, ZHU Li, LIU Luhui, ZHAN Hanglong, LU Yanmin. Intelligent risk contagion mechanism of interbank market credit lending based on multi-layer network [J]. Journal of Computer Applications, 2019, 39(5): 1507-1511.
[14]	YANG Xiong, YAO Rong, YANG Pengfei, WANG Zhe, LI Haifang. Brain network analysis method based on feature vector of electroencephalograph subsequence [J]. Journal of Computer Applications, 2019, 39(4): 1224-1228.
[15]	LIU Zhengming, MA Hong, LIU Shuxin, LI Haitao, CHANG Sheng. Network representation learning algorithm incorporated with node profile attribute information [J]. Journal of Computer Applications, 2019, 39(4): 1012-1020.