An Algorithm to Find Overlapping Community Structure in Networks
An Algorithm to Find Overlapping Community Structure in Networks
复制标题
DOI：
10.1007/978-3-540-74976-9_12
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
Steve Gregory
中科院分区：
文献类型：
--
作者：
Steve Gregory
近年来出现了许多图聚类算法，可以识别网络中的社团结构。这些方法中的绝大多数只能找到不相交的社区，但在许多现实世界的网络中，社区在一定程度上重叠。本文提出了一种新的发现网络中重叠社区的算法，该算法是对Girvan和纽曼基于介数中心性测度的著名算法的扩展.与原始算法一样，我们的算法执行分层聚类-将网络划分为任何所需数量的聚类-但允许它们重叠。实验证实了基于已知重叠社区结构的随机生成网络的良好性能，并且在一系列真实网络上也获得了有趣的结果。
Recent years have seen the development of many graph clustering algorithms, which can identify community structure in networks. The vast majority of these only find disjoint communities, but in many real-world networks communities overlap to some extent. We present a new algorithm for discovering overlapping communities in networks, by extending Girvan and Newman’s well-known algorithm based on thebetweennesscentrality measure. Like the original algorithm, ours performs hierarchical clustering — partitioning a network into any desired number of clusters — but allows them to overlap. Experiments confirm good performance on randomly generated networks based on a known overlapping community structure, and interesting results have also been obtained on a range of real-world networks.