基于桥系数的分裂社区检测算法研究  

A Community Detection Algorithm Based on Bridgeness

作　　者：冀庆斌[1] 康茜[1] 李德玉[1] 王素格[1] 

机构地区：[1]山西大学计算机与信息技术学院,山西太原030051

出　　处：《中文信息学报》2017年第3期205-212,共8页Journal of Chinese Information Processing

基　　金：国家自然科学基金(61175067;61272095;61432011;61573231);山西省科技基础条件平台计划项目(2015091001-0102);山西省回国留学人员科研项目(2013-014)

摘　　要：研究社区结构有助于揭示网络结构和功能之间的关系,而社区检测是社区结构研究的基础和核心。该文定义了一种聚集度桥系数,将其应用到社区检测中,设计出一种分裂社区检测方法,包括分裂和合并两个算法。分裂算法使用桥系数识别社区间边,通过迭代删除社区间边分解网络,从而发现网络中的社区结构;合并算法根据社区连接强度合并社区,可以揭示社区结构中的分层嵌套的现象。在六个社会网络数据集上的实验表明,本文算法可以有效的将网络分裂为有意义的社区,并且准确性接近或超过经典的社区检测算法。Study of community structure is of help to reveal the relationship between network structure and function, and cbmmunity detection is essential to the community structure research. A bridgeness index based on clustering degree is defined in this paper, and applied to the community detection. The proposed algorithm includes two parts splitting and merging. The splitting algorithm identifies inter-community by bridgeness, and decomposes network by iterative removing inter-community edges until the community structure is discovered; The merging algorithm merges communities according to the community connection strength, so that the hierarchical nesting in community is revealed. Experiments on six social networks show that the proposed algorithm can effectively detect interesting communities for the whole network, and the accuracy is close to or even better than the classical algorithms.

关 键 词：社区检测 分裂算法 桥系数 

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