基于共享最近邻探测社团结构的算法  

Detecting community structure based on shared nearest neighbor

作　　者：高学东[1] 王立敏[1,2] 马红权 武森[1] 

机构地区：[1]北京科技大学经济管理学院,北京100083 [2]北京科技大学中国教育经济信息网管理中心,北京100083 [3]中国钢研集团,北京100081

出　　处：《系统工程理论与实践》2009年第10期102-109,共8页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70771007);2005年度新世纪优秀人才支持计划(NECT-05-0097).

摘　　要：针对经典重叠社团结构发现的派系过滤算法中派系定义过于严格、算法缺乏实用性、时间复杂度高等问题,提出了一种基于共享最近邻的社团结构发现算法.该算法不仅可以对网络进行社团结构的划分,而且可以很好地把网络中的桥点找出,算法的时间复杂度约为O(nhk),其中n为网络中的节点数,h为核心社团的数目,k为网络中节点的最大节点度.为了验证该算法的正确率和性能,把该算法应用到计算机生成网络和真实网络中,并与著名的社团探测算法—GN算法和NF快速算法进行了比较.实验的结果表明所提出的算法是有效可行的.K-clique algorithm deals with overlapping communities, but it is not practical and the time complexity is higher. A method based on shared nearest neighbor was proposed, which not only divided the community structure but also found the bridge vertex in network. The algorithm ran in time O（nhk） when n is the number of vertices in network, h is the number of the core community and k is the maximal degree of vertex in network. The method was applied to different well-know instances of community-structured networks, including synthetic and real-world networks. In order to determine the precise and performance of the method, it was compared with the two most popular community identification approach, narnely GN and NF algorithm. Experiment results show the feasibility and effectiveness of the proposed approach.

关 键 词：复杂网络 共享最近邻 社团结构 

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