基于节点相似性和网络嵌入的复杂网络社区发现算法  

Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding

作　　者：杨旭华[1] 王磊[1] 叶蕾[1] 张端 周艳波 龙海霞 YANG Xu-hua;WANG Lei;YE Lei;ZHANG Duan;ZHOU Yan-bo;LONG Hai-xia(College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)

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

出　　处：《计算机科学》2022年第3期121-128,共8页Computer Science

基　　金：国家自然科学基金(61773348)。

摘　　要：社区发现算法对分析复杂网络的拓扑和层次结构、预测复杂网络的演化趋势等具有十分重要的意义。传统的社区发现算法划分精度不高,忽略了网络嵌入的重要性。针对这样的问题,提出了基于节点相似性和网络嵌入Node2Vec方法的无参数社区发现算法。首先,使用网络嵌入Node2Vec方法将网络节点映射成欧氏空间中低维向量表示的数据点,计算低维向量表示的数据点之间的余弦相似性,根据相应节点间的最大相似性构建偏好网络,得到初始社区划分,把每个初始社区的最大度节点作为备选节点;然后根据网络平均度和平均最短路径找出备选节点中的中心节点;最后将中心节点对应的数据点及其数量作为初始质心和聚类数,用K-Means算法对低维向量表示的数据点进行聚类,从而对相应的网络节点完成社区划分。该算法为无参数社区划分方法,可以自主地从网络中提取参数,无须根据网络的不同设定不同的超参数,从而可以自动地快速识别复杂网络的社区结构。在8个真实网络和人工网络上,将其与其他5个知名社区发现算法相比较,数值仿真实验表明所提算法具有很好的社区发现效果。The community detection algorithm is very important for analyzing the topology and hierarchical structure of complex networks and predicting the evolution trend of complex networks.Traditional community detection algorithm does not have high accuracy and ignores the importance of network embedding.Aiming at such problems,a parameter-free community detection algorithm based on node similarity and network embedding Node2Vec method is proposed.First,we use the network embedding Node2Vec method to map network nodes into data points represented by low-dimensional vectors in Euclidean space,calculate the cosine similarity between the data points represented by the low-dimensional vector,construct a preference network according to the maximum similarity between the corresponding nodes,obtain the initial community detection,and use the maximum degree node of each initial community as a candidate node.Then we find the central node among the candidate nodes according to the average degree of the network and the average shortest path.Finally,the data points and their numbers corresponding to the central node are used as the initial centroid and cluster number,and the data represented by the low-dimensional vector are calculated by K-Means algorithm.The points are clustered,and the corresponding network nodes are divided into communities.This algorithm is a method of community division without parameters,which can independently extract parameters from the network without setting different hyper-parameters according to different networks,so that it can automatically and quickly identify the community structure of complex networks.In 8 real networks and artificial networks above,by comparing with other 5 well-known community discovery algorithms,numerical simulation experiments show that the proposed algorithm has good community discovery effect.

关 键 词：无参数社区发现 节点相似性 偏好网络 网络嵌入 K-MEANS聚类 

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