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

Community Detection Based on Markov Similarity Enhancement and Network Embedding

作　　者：曾祥宇 龙海霞 杨旭华[1] ZENG Xiangyu;LONG Haixia;YANG Xuhua(College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)

机构地区：[1]浙江工业大学计算机科学与技术学院,杭州310023

出　　处：《计算机科学》2023年第4期56-62,共7页Computer Science

基　　金：国家自然科学基金(62176236,62106225)。

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]