基于特征向量局部相似性的社区检测算法

Community Detection Algorithm Based on Local Similarity of Feature Vectors

社区的发现和分析是复杂网络结构和功能研究中的一个热点。目前广泛应用的社区划分算法存在时间复杂度过高、社区核心数量无法准确量化、划分精度不高等问题。文中提出了一种基于特征向量局部相似性的社区检测算法ELSC。该算法首先计算网络中每个节点的特征向量中心性,在此基础上提出了特征向量局部相似性(ELS)和特征向量吸引性(EA)指标。ELS指标表示节点之间的相似性,用来形成初始社区,在同一个社区内部节点之间的相似性较高,在不同社区节点之间的相似性较低;EA指标同时考虑了局部相似性和特征向量中心性的占比,表示节点之间的吸引性,用来优化初始社区,并在此基础上完成网络的社区划分。该算法由最值确定节点,避免了节点数量阈值不确定的问题。在7个真实网络上将所提算法与6种知名算法的模块度和标准化互信息两个指标进行综合比较,结果表明,该算法具有良好的准确性,并且具有较低的时间复杂度。

Community discovery and analysis is a hot topic in the study of complex network structures and functions.At present,the widely used algorithm for community partitioning has some problems,such as high time complexity,inaccurate quantification of the number of community cores,and low partitioning accuracy.Therefore,this paper proposed a community detection algorithm ELSC based on local similarity of feature vectors.The algorithm first calculates the eigenvector centrality of each node in the network.On this basis,the eigenvector local similarity(ELS)and eigenvector attractiveness(EA)indicators were proposed.The ELS index indicates the similarity between nodes.To form the initial community,the similarity between the nodes within the same community is higher,and the similarity between different community nodes is lower.The EA index considers the local similarity and the eigenvector centrality ratio,indicating the node.The attraction is used to optimize the initial community and complete the community division of the network.The algorithm determines the node by the most value,avoiding the problem that the threshold number of nodes is uncertain.The modularity and standardized mutual information between the proposed algorithm and six well-known algorithms were compared on seven real networks.Numerical simulation results show that the algorithm has high accuracy and low time complexity.