基于马尔可夫相似性增强和网络嵌入的社区发现

doi:10.11896/jsjkx.220100155

摘要/Abstract

摘要： 社区结构普遍存在于自然界的各种复杂网络中,是网络结构的重要特征之一。社区发现算法可以识别网络中的有用信息,有助于分析网络的结构和功能,被广泛应用于社交网络、生物和医学等领域。文中针对目前基于局部相似性的复杂网络社区发现算法精确度不高的问题,提出了一种基于马尔可夫相似性增强和网络嵌入的社区发现算法。首先,受马尔可夫链思想启发,提出了一种马尔可夫相似性增强方法,通过对初始网络的马尔可夫迭代状态进行转移,来获取稳态的马尔可夫相似性增强矩阵,根据马尔可夫相似性指标对网络进行初始的社区划分。然后结合网络的拓扑结构和网络嵌入,提出了一种新的社区相似性指标,将初始社区结构中的小社区与其连接紧密的社区合并,得到网络社区结构。在7个真实网络和可变参数的人工网络上,通过与其他5个知名社区发现算法的比较,证明了所提算法具有良好的社区发现效果。

关键词: 社区发现, 复杂网络, 马尔可夫相似性, 网络嵌入, 社区相似性

Abstract: Community structure is ubiquitous in various complex networks in nature and is one of the important characteristics of network structure.Community detection can identify useful information in the network,and help to analyze the structure and function of the network.It is widely used in social networks,biology,medicine and other fields.Aiming at the low accuracy of the current community detection algorithm based on local similarity in complex networks,a community detection algorithm based on Markov similarity enhancement and network embedding is proposed.Firstly,inspired by the idea of Markov chain,a Markov similarity enhancement method is proposed,which obtains the steady-state Markov similarity enhancement matrix through the Mar-kov iterative state transition of the initial network.According to the Markov similarity index,the network is divided into initial community structure.Then,a new community similarity index is proposed by combining the network topology and network embedding.The small community in the initial community structure is merged with its closely connected community to obtain the network community structure.On 7 real networks and artificial networks with variable parameters,compared with other 5 well-known community detection algorithms,it is proved that the proposed algorithm has a good community detection effect.

Key words: Community detection, Complex network, Markov similarity, Network embedding, Community similarity

中图分类号:

TP391

曾祥宇, 龙海霞, 杨旭华. 基于马尔可夫相似性增强和网络嵌入的社区发现[J]. 计算机科学, 2023, 50(4): 56-62. https://doi.org/10.11896/jsjkx.220100155

ZENG Xiangyu, LONG Haixia, YANG Xuhua. Community Detection Based on Markov Similarity Enhancement and Network Embedding[J]. Computer Science, 2023, 50(4): 56-62. https://doi.org/10.11896/jsjkx.220100155

参考文献

[1]LI M,LU S,ZHANG L,et al.A Community Detection Method for Social Network Based on Community Embedding[J].IEEE Transactions on Computational Social Systems,2021,8(2):308-318.
[2]ZHANG W,SHANG R,JIAO L.Complex Network Graph Embedding Method Based on Shortest Path and MOEA/D for Community Detection[J].Applied Soft Computing,2020,97:106764.
[3]ACMAN M,DORP L V,SANTINI J M,et al.Large-scale Network Analysis Captures Biological Features of Bacterial Plasmids[J].Nature Communications,2020,11(1):1-11.
[4]HAN N,QIAO S J,YUAN C A,et al.Fast Community Parallel Detection Algorithm in Mobile Social Networks[J].Journal of Chongqing University of Technology:Natural Science,2020,34(1):94-102.
[5]IMANE M,NADJET K.Community Detection UsingFireworks Optimization Algorithm[J].International Journal of Artificial Intelligence Tools,2019,28(3):1950010.
[6]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.
[7]CLAUSET A,NEWMAN M E J,MOORE C.Finding Commu-nity Structure in Very Large Networks[J].Physical Review E,2004,70(6):066111.
[8]HU F,ZHU Y,SHI Y,et al.An Algorithm Walktrap-SPM forDetecting Overlapping Community Structure[J].International Journal of Modern Physics B,2017,31(15):1750121.
[9]NEWMAN M E J,GIRVAN M.Finding and Evaluating Community Structure in Networks[J].Physical Review E,2004,69(2):026113.
[10]GIRVAN M,NEWMAN M E J.Community Structure in Social and Biological Networks[J].Proceedings of the National Aca-demy of Sciences of the United States of America,2002,99(12):7821-7826.
[11]ROSVALL M,BERGSTROM C T.Maps of RandomWalks on Complex Networks Reveal Community Structure[J].Procee-dings of the National Academy of Sciences,2008,105(4):1118-1123.
[12]EUSTACE J,WANG X,CUI Y.Community Detection UsingLocal Neighborhood in Complex Networks[J].Physica A:Statistical Mechanics and its Applications,2015,436:665-667.
[13]LIU J L,WANG D L,ZHANG Y F,et al.Local Community DetectionApproach Based on Fuzzy Similarity Relation[J].Journal of Software,2020,31(11):3481-3491.
[14]KUMAR S,PANDA B S,AGGARWAL D.Community Detection in Complex Networks Using Network Embedding and Gravitational Search Algorithm[J].Journal of Intelligent Information Systems,2020,57(1):51-72.
[15]ZHAO X,LI X,ZHANG Z H,et al.Community Detection Algorithm Combining Community Embedding and Node Embedding[J].Computer Science,2020,47(10):121-125.
[16]HE D,WANG Y,CAO J,et al.A Network Embedding-en-hanced Bayesian Model for Generalized Community Detection in Complex Networks[J].Information Sciences,2021,575:306-322.
[17]WANG D,CUI P,ZHU W.Structural Deep Network Embed-ding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2016:1225-1234.
[18]WANG T,YIN L Y,WANG X X.A community DetectionMethod Based on Local Similarity and Degree Clustering Information[J].Physica A,2018,490:1344-1354.
[19]ZHANG J,DING X,YANG J.Revealing the Role of Node Similarity and Community Merging in Community Detection[J].Knowledge-Based Systems,2018,165:407-419.
[20]VERMA P,GOYAL R.Influence Propagation Based Community Detection in Complex Networks[J].Machine Learning with Applications,2020,12:100019.
[21]YOU X,MA Y,LIU Z.A Three-stage Algorithm on Communi-ty Detection in Social Networks[J].Knowledge-Based Systems,2020,187:104822.
[22]PEROZZI B,AL-RFOU R,SKIENA S.Deepwalk:OnlineLearning of Social Representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.2014:701-710.
[23]MIKOLOV T,CHEN K,CORRADO G,et al.Efficient Estimation of Word Representations in Vector Space[J].arXiv:1301.3781,2013.
[24]GROVER A,LESKOVEC J.Node2vec:Scalable Feature Lear-ning for Networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2016:855-864.
[25]TANG J,QU M,WANG M,et al.Line:Large-scale Information Network Embedding[C]//Proceedings of the 24th International Conference on World Wide Web.2015:1067-1077.
[26]NEWMAN M E J.Fast Algorithm for Detecting CommunityStructure in Networks[J].Physical Review E,2004,69(6):066133.
[27]NEWMAN M E J.Finding Community Structure in Networks Using the Eigenvectors of Matrices[J].Physical Review E,2006,74(3):036104.
[28]CLAUSET A,NEWMAN M E J,MOORE C.Finding Community Structure in Very Large Networks[J].Physical Review E,2004,70(6):066111.
[29]HESAMIPOUR S,BALAFAR M A.A New Method for Detecting Communities and their Centers Using the Adamic/Adar Index and Game Theory[J].Physica A:Statistical Mechanics and its Applications,2019,535:122354.
[30]SU Y S,LIU C L,NIU Y Y,et al.A Community Structure Enhancement-based Community Detection Algorithm for Complex Networks[J].IEEE Transactions on Systems Man Cybernetics-Systems,2021,51(5):2833-2846.
[31]SUN Z J,SUN Y N,CHANG X F,et al.Community Detection Based on the Matthew Effect[J].Knowledge-Based Systems,2020,205:106256.
[32]ZHANG L,PAN H B,SU Y S,et al.A Mixed RepresentationBased Multiobjective Evolutionary Algorithm for Overlapping Community Detection[J].IEEE Transactions on Cybernetics,2017,47(9):2703-2716.
[33]JIANG H,LIU Z,LIU C,et al.Community Detection in Complex Networks with an Ambiguous Structure Using Central Node Based Link Prediction[J].Knowledge-Based Systems,2020,195:105626.
[34]LIU H J,MA H F,ZHAO Q Q,et al.Target Community Detection with User Interest Preferences and Influence[J].Journal of Computer Research and Development,2021,58(1):70-82.
[35]LU H,SHEN Z,SANG X S,et al.Community Detection Me-thod Using Improved Density Peak Clustering and Nonnegative Matrix Factorization[J].Neorocomputing,2020,415:247-257.
[36]CHEN Y Z,SHI S,ZHU W P,et al.An Incremental Community Detection Algorithm Based on Neighborhood Following Relationship[J].Chinese Journal of Computers,2017,40(3):570-583.
[37]NATH K,SHANMUGAM R,VARADARANJAN V.Ma-CODE:A Multi-phase Approach on Community Detection in Evolving Networks[J].Information Sciences,2021,569:326-343.
[38]SAID A,ABBASI R A,MAQBOOL O,et al.CC-GA:A Clustering Coefficient Based Genetic Algorithm for Detecting Communities in Social Networks[J].Applied Soft Computing,2018,63:59-70.

相关文章 15

[1]	段顺然, 尹美娟, 刘粉林, 焦隆隆, 于岚岚. 一种基于影响力预测的节点排序模型 Nodes’ Ranking Model Based on Influence Prediction 计算机科学, 2023, 50(3): 155-163. https://doi.org/10.11896/jsjkx.211200261
[2]	郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[3]	何亦琛, 毛宜军, 谢贤芬, 古万荣. 基于点割集图分割的矩阵变换与分解的推荐算法 Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation 计算机科学, 2022, 49(6A): 272-279. https://doi.org/10.11896/jsjkx.210600159
[4]	何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[5]	杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[6]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[7]	唐春阳, 肖玉芝, 赵海兴, 冶忠林, 张娜. 面向双层网络的EWCC社区发现算法 EWCC Community Discovery Algorithm for Two-Layer Network 计算机科学, 2022, 49(4): 49-55. https://doi.org/10.11896/jsjkx.210800275
[8]	陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[9]	郭磊, 马廷淮. 基于好友亲密度的用户匹配 Friend Closeness Based User Matching 计算机科学, 2022, 49(3): 113-120. https://doi.org/10.11896/jsjkx.210200137
[10]	杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009
[11]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[12]	汤启友, 张凤荔, 王瑞锦, 王雪婷, 周志远, 韩英军. 融合多特征的属性异质网络嵌入方法 Method of Attributed Heterogeneous Network Embedding with Multiple Features 计算机科学, 2022, 49(12): 146-154. https://doi.org/10.11896/jsjkx.211200082
[13]	郑文萍, 王宁, 杨贵. 一种基于局部路径信息的重叠社区发现算法 Overlapping Community Detection Algorithm Based on Local Path Information 计算机科学, 2022, 49(12): 155-162. https://doi.org/10.11896/jsjkx.220500190
[14]	段小虎, 曹付元. 基于节点局部相似性的两阶段密度峰值重叠社区发现方法 Node Local Similarity Based Two-stage Density Peaks Algorithm for Overlapping Community Detection 计算机科学, 2022, 49(12): 170-177. https://doi.org/10.11896/jsjkx.211000025
[15]	潘雨, 王帅辉, 张磊, 胡谷雨, 邹军华, 王田丰, 潘志松. 复杂网络社团发现综述 Survey of Community Detection in Complex Network 计算机科学, 2022, 49(11A): 210800144-11. https://doi.org/10.11896/jsjkx.210800144

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed