基于网络嵌入与局部合力的复杂网络社区划分算法

doi:10.11896/jsjkx.200200102

摘要/Abstract

摘要： 社区划分可以揭示复杂网络中的内在结构和行为动态特点,是当前的研究热点。文中提出了一种基于网络嵌入和局部合力的社区划分算法。该算法将网络的拓扑空间转化成欧氏空间,把网络节点转换成向量表示的数据点,首先基于重力模型和网络拓扑结构,提出局部合力和局部合力余弦中心性指标(Local Resultant Force Cosine Centrality,LFC),通过节点的LFC和节点间的距离来确定各个初始小社区的中心节点,然后将网络中其他的非中心节点划入与其最近的中心节点所在的初始小社区内,最后通过优化模块度的方法来合并初始小社区并找到最优的网络社区结构。在6个现实世界网络和可调参数人工网络上与6种知名社区划分方法进行比较,比较结果表明了新算法良好的社区划分的性能。

关键词: 局部合力, 局部合力余弦中心性, 社区划分, 网络嵌入, 引力模型

Abstract: Community detection can reveal the inherent structure dynamic behavior in complex networks and it is the current research hotspot.In this paper,we propose a community detection algorithm based on network embedding and local resultant force.The network topological space is transformed into euclidean space,and network nodes are converted into vector data points.First,based on the gravity model and the network topology,a local resultant force and a local resultant force cosine centrality index(LFC) are proposed.The center node of each initial small community is determined by the LFC of the node and the distance between nodes.Then the rest of the non-central nodes are classified to the nearest central node to form the initial small community.Finally,communities are merged by optimizing the modularity to find the optimal network community structure.Compared with 6 well-known community detection algorithms on 6 real-world networks and artificial networks with adjustable parameters,the new proposed algorithm shows good performance in the community detection.

Key words: Community detection, Gravity model, Local resultant force, Local resultant force cosine centrality, Network embedding

中图分类号:

TP391

杨旭华, 王晨. 基于网络嵌入与局部合力的复杂网络社区划分算法[J]. 计算机科学, 2021, 48(4): 229-236. https://doi.org/10.11896/jsjkx.200200102

YANG Xu-hua, WANG Chen. Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force[J]. Computer Science, 2021, 48(4): 229-236. https://doi.org/10.11896/jsjkx.200200102

参考文献

[1]MAHMOOD A,SMALL M.Subspace Based Network Community Detection Using Sparse Linear Coding[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(3):801-812.
[2]LEBERKNIGHT C,INALTEKIN H,CHIANG M,et al.TheEvolution of Online Social Networks:A tutorial survey[J].IEEE Signal Processing Magazine,2012,29(2):41-52.
[3]PAGANI G A,AIELLO M.The Power Grid as a complex network:A survey[J].Physica A:Statistical Mechanics and its Applications,2013,392(11):2688-2700.
[4]CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(6 Pt 2):066111.
[5]NEWMAN M E J,GIRVAN M.Finding and Evaluating Community Structure in Networks[J].Physical Review E,2004,69(2 Pt 2):26-113.
[6]GUI C,ZHANG R,ZHAO Z,et al.LPA-CBD an improved label propagation algorithm based on community belonging degree for community detection[J].International Journal of Modern Physics C,2018,29(3):1850011.
[7]MOHOTTI W A,NAYAK R.Corpus-based Augmented Media Posts with Density-based Clustering for Community Detection[C]//IEEE International Conference on Tools with Artificial Intelligence.IEEE Computer Society,2018:379-386.
[8]ZARANDI F D,RAFSANJANI M K.Community detection in complex networks using structural similarity[J].Physica A:Statistical Mechanics and Its Applications,2018,503:882-891.
[9]SAOUD B,ABEDLOUAHAB M.Node similarity and modularity for finding communities in networks[J].Physica A:Statistical Mechanics and its Applications,2018,429:1958-1966.
[10]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[11]NEWMAN M E J.Fast algorithm for detecting communitystructure in networks[J].Physical Review E,2003,69(6 Pt 2):66-133.
[12]WEN X,CHEN W N,LIN Y,et al.A Maximal Clique BasedMultiobjective Evolutionary Algorithm for Overlapping Community Detection[J].IEEE Transactions on Evolutionary Computation,2016,PP(99):1.
[13]AMIRI B,HOSSAIN L,CRAWFORD J W.An efficient mul-tiobjective evolutionary algorithm for community detection in social networks[C]//Proceedings of the IEEE Congress on Evolutionary Computation(CEC 2011).IEEE,2011:2193-2199.
[14]LI W,JIANG S,JIN Q.Overlap community detection usingspectral algorithm based on node convergence degree[J].Future Generation Computer Systems,2017,79(1):408-416.
[15]IMANE M,NADIET K.Community Detection Using Fireworks Optimization Algorithm[J].International Journal of Artificial Intelligence Tools,2019,28(3):1950010.
[16]NIU X Z,SI W Y,SHE K.Evolutionary Community Detection in Dynamic Networks[J].Journal of Software,2017,28(7):1773-1789.
[17]LV L Y,ZHOU T.Link prediction in complex networks:A survey[J].Physica A:Statistical Mechanics and its Applications,2011,390(6):1150-1170.
[18]LEYDESDORFF L.On the normalization and visualization ofauthor co-citation data:Salton’s Cosine versus the Jaccard index[J].Journal of the American Society for Information Science and Technology,2008,59(1):77-85.
[19]RAVASZ E,SOMERA A L,MONGRU D A,et al.Hierarchical organization of modularity in metabolic networks[J].Science,2002,297(5586):1551-1555.
[20]ZHANG H,WU Y K,YANG Z Z,et al.Community Detection Method Based on Multi-layer Node Similarity[J].Computer Science,2018,45(1):216-222.
[21]PEROZZI B,AL-RFOU R,SKIENA S.DeepWalk:OnlineLearning of Social Representations[C]//The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York City,USA,2014.
[22]TANG J,QU M,WANG M,et al.LINE:Large-scale information network embedding[C]//The 24th International Confe-rence on World Wide Web.Florence,Italy,2015:1167-1177.
[23]GROVER A,LESKOVEC J.node2vec:Scalable Feature Lear-ning for Networks[C]//The 22nd ACM SIGKDD International Conference.San Francisco,USA,2016:855-864.
[24]WANG D,CUI P,ZHU W.Structural Deep Network Embed-ding[C]//The 22nd ACM SIGKDD International Conference.ACM,2016:1225-1234.
[25]HUANG J B,SUN H L,LIU Y G,et al.Towards Online Multiresolution Community Detection in Large-Scale Networks[J].PLoS ONE,2011,6(8):e23829.
[26]LANCICHINETTI A,FORTUNATO S.Detecting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):033015.
[27]REICHARDT J,BORNHOLDT S.Statistical mechanics of community detection[J].Physical Review E,2006,74(1):016110.
[28]RONHOVDE P,NUSSINOV Z.Local resolution-limit-freePotts model for community detection[J].Physical Review E,2010,81(4):46-114.
[29]MARTELOT E L,HANKIN C.Multi-scale Community Detection using Stability Optimisation within Greedy Algorithms[J].Eprint Arxiv,2012,9(3):323-348.
[30]DANON L,DUCH J,DIAZ-GUILERA A,et al.Comparingcommunity structure identification[J].Journal of Statistical Mechanics,2005,2005(9):P09008.
[31]TASGIN M,BINGOL H O.Community detection using prefe-rence networks[J].Physica A Statistical Mechanics and its Applications,2017,495:126-136.
[32]HU F,WANG M,WANG Y,et al.An algorithm J-SC of detecting communities in complex networks [J].Physics Letters A,2017,381(42):3604-3612.
[33]LI Y F,JIA C Y,YU J.A parameter-free community detection method based on centrality and dispersion of nodes in complex networks[J].Physica A:Statistical Mechanics and its Applications,2015,438:321-334.
[34]CHENG F,CUI T,SU Y,et al.A Local Information basedMulti-objective Evolutionary Algorithm for Community Detection in Complex Networks[J].Applied Soft Computing,2018,69:357-367.
[35]CHEN L G,WANG Y R,HUANG X M,et al.SA-SOM algorithm for detecting communities in complex networks[J].Physics Letters B,2017,31(29):1750262.
[36]GLEISER P M,DANON L.Community structure in Jazz[J].Advances in Complex Systems,2003,6(4):565-573.
[37]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E Statistical Nonlinear and Soft Matter Phy-sics,2008,78(4 Pt 2):046-110.

相关文章 15

[1]	陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[2]	郭磊, 马廷淮. 基于好友亲密度的用户匹配 Friend Closeness Based User Matching 计算机科学, 2022, 49(3): 113-120. https://doi.org/10.11896/jsjkx.210200137
[3]	杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009
[4]	郑苏苏, 关东海, 袁伟伟. 融合不完整多视图的异质信息网络嵌入方法 Heterogeneous Information Network Embedding with Incomplete Multi-view Fusion 计算机科学, 2021, 48(9): 68-76. https://doi.org/10.11896/jsjkx.210500203
[5]	胡昕彤, 沙朝锋, 刘艳君. 基于随机投影和主成分分析的网络嵌入后处理算法 Post-processing Network Embedding Algorithm with Random Projection and Principal Component Analysis 计算机科学, 2021, 48(5): 124-129. https://doi.org/10.11896/jsjkx.200500058
[6]	张健雄, 宋坤, 何鹏, 李兵. 基于图神经网络的软件系统中关键类的识别 Identification of Key Classes in Software Systems Based on Graph Neural Networks 计算机科学, 2021, 48(12): 149-158. https://doi.org/10.11896/jsjkx.210100200
[7]	徐新黎, 肖云月, 龙海霞, 杨旭华, 毛剑飞. 基于矩阵分解的属性网络嵌入和社区发现算法 Attributed Network Embedding Based on Matrix Factorization and Community Detection 计算机科学, 2021, 48(12): 204-211. https://doi.org/10.11896/jsjkx.210300060
[8]	丁钰, 魏浩, 潘志松, 刘鑫. 网络表示学习算法综述 Survey of Network Representation Learning 计算机科学, 2020, 47(9): 52-59. https://doi.org/10.11896/jsjkx.190300004
[9]	吴勇, 王斌君, 翟一鸣, 仝鑫. 共引增强有向网络嵌入研究 Study on Co-citation Enhancing Directed Network Embedding 计算机科学, 2020, 47(12): 279-284. https://doi.org/10.11896/jsjkx.191000199
[10]	赵霞, 李娴, 张泽华, 张晨威. 结合社区嵌入和节点嵌入的社区发现算法 Community Detection Algorithm Combing Community Embedding and Node Embedding 计算机科学, 2020, 47(10): 121-125. https://doi.org/10.11896/jsjkx.191000099
[11]	张晓琴, 安晓丹, 曹付元. 基于谱聚类的二分网络社区发现算法 Detecting Community from Bipartite Network Based on Spectral Clustering 计算机科学, 2019, 46(4): 216-221. https://doi.org/10.11896/j.issn.1002-137X.2019.04.034
[12]	冶忠林, 赵海兴, 张科, 朱宇. 基于多视图集成的网络表示学习算法 Network Representation Learning Based on Multi-view Ensemble Algorithm 计算机科学, 2019, 46(1): 117-125. https://doi.org/10.11896／j.issn.1002-137X.2019.01.018
[13]	胡庆成, 张勇, 邢春晓. 基于有重叠社区划分的社会网络影响最大化方法研究 K-clique Heuristic Algorithm for Influence Maximization in Social Network 计算机科学, 2018, 45(6): 32-35. https://doi.org/10.11896/j.issn.1002-137X.2018.06.005
[14]	邹凌君,陈崚,戴彩艳. 基于广义后缀树的二分网络社区挖掘算法 Detecting Community from Bipartite Network Based on Generalized Suffix Tree 计算机科学, 2017, 44(7): 221-226. https://doi.org/10.11896/j.issn.1002-137X.2017.07.039
[15]	高秀娥,李克秋. 基于改进多属性判决的异构网络接入选择算法 Research on Heterogeneous Network Access Selection Algorithm Based on Improved Multiple Attribute 计算机科学, 2017, 44(6): 97-101. https://doi.org/10.11896/j.issn.1002-137X.2017.06.017

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed