基于边密度的复杂网络社区结构划分方法  

PARTITION METHOD FOR COMMUNITY STRUCTURE IN COMPLEX NETWORKS BASED ON EDGE DENSITY

作　　者：周林[1] 晏立[1] 沈项军[1] 

机构地区：[1]江苏大学计算机科学与通信工程学院,江苏镇江212013

出　　处：《计算机应用与软件》2013年第12期8-11,共4页Computer Applications and Software

基　　金：国家自然科学基金项目(61005017);江苏省高校自然科学基金项目(10KJB520005)

摘　　要：针对基于模块度最优的社区结构探测算法会产生分辨率限制、时间复杂度高等问题,提出一种基于边密度的社区结构探测算法。该算法不仅可以对网络进行社区结构的划分,而且不会产生分辨率限制的问题,算法的运行复杂度是O(k·m),其中m为网络中的边数,k为网络中节点的最大节点度。为了验证该算法的正确性和性能,与著名的社团探测算法——GN算法和NF算法进行比较,结果表明所提出的算法是有效可行的。The community structure detection algorithm based on optimal module degree will have the problems of resolution limit and high time complexity, etc. In light of this, we propose an edge density-based community structure detection algorithm. The algorithm can partition the network in regard to community structure but will not form the problem of resolution limit. The algorithm has the operation complexity of 0（ k m）, where m is the number of edges in the network and k is the maximum degree of node in the network. In order to verify the correctness and performance of the algorithm, we compare it with two of the famous community detection approaches, namely GN and NF algorithms. Experi- ment results show that the proposed algorithm is feasible and effective.

关 键 词：复杂网络 社区结构 分辨率限制 边密度 自动探测 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]