“自底向上”合并社群结构探测策略中的顺序效应  

Order Affection in Bottom-up Merging Community Detection Strategies Based on Modularity

作　　者：陈盈晖[1,2] 杜海峰[3] 李树茁[2] 

机构地区：[1]西安交通大学管理学院,西安710049 [2]西安交通大学人口与发展研究所,西安710049 [3]西安交通大学公共管理与复杂性科学研究中心,西安710049

出　　处：《系统管理学报》2010年第4期476-480,共5页Journal of Systems & Management

基　　金：教育部"新世纪优秀人才支持计划"(NCET-07-0668;NCET-08-0451);"长江学者"奖励计划;教育部长江学者和创新团队发展计划(IRT0855);国家自然科学基金资助项目(70671083);美国Santa Fe Institute国际项目基金;斯坦福大学联合资助项目

摘　　要：基于模块性"自底向上"合并社群结构探测策略是目前复杂网络研究的热点问题之一,但是在依据模块性值变化对相应社群对进行合并时,往往出现顺序效应,即同一模块性值变化对应的社群合并可能不惟一,从而导致合并顺序不同而影响社群结构的最终探测结果。首先总结"自底向上"合并社群结构探测策略的一般算法框架,然后基于标准Ucinet和Pajek网络的社群结构探测结果,揭示Newman等提出的社群结构探测算法存在顺序效应,接着依据网络社群结构和社群密度的定义,提出用于克服顺序效应的基于社群密度的改进社群结构探测策略;最后,通过标准Ucinet和Pajek网络的社群结构探测结果,验证算法的有效性。Based on the modularity,＂bottom-up＂ agglomerative detecting strategy is the hot spot in the field of the community structure,which is the main characteristic of the complexity network.When two small communities are combined to form a big one based on the changing of the modularity,there are more than one pair of communities.And choosing different pair of communities will deduce different community structure,which is defined order affection.In this paper,we illustrate the basic flowchart of a ＂bottom-up merging＂ community detection strategy based on modularity,and we explore the order affection by Newman＇s fast community detection algorithm,and then we give a modified algorithm for Newman＇s according to the density of community.The results of community detection for some networks,such as computer-generated Network,Ucinet and Pajek networks, indicate that the modified algorithm achieves higher modularity and avoiding the order affection to some extend.

关 键 词：复杂网络 社群结构 模块性 

分 类 号：N94[自然科学总论—系统科学]