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

摘要

研究社区结构有助于揭示网络结构和功能之间的关系,而社区检测是社区结构研究的基础和核心.该文定义了一种聚集度桥系数,将其应用到社区检测中,设计出一种分裂社区检测方法,包括分裂和合并两个算法.分裂算法使用桥系数识别社区间边,通过迭代删除社区间边分解网络,从而发现网络中的社区结构;合并算法根据社区连接强度合并社区,可以揭示社区结构中的分层嵌套的现象.在六个社会网络数据集上的实验表明,本文算法可以有效的将网络分裂为有意义的社区,并且准确性接近或超过经典的社区检测算法.%Study of community structure is of help to reveal the relationship between network structure and function,and community 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.