Finding and evaluating community structure in networks
Finding and evaluating community structure in networks
复制标题
DOI：
10.1103/physreve.69.026113
复制
发表时间：
2004-02-01
影响因子：
2.4
通讯作者：
Girvan, M
中科院分区：
文献类型：
--
作者：
Newman, MEJ;Girvan, M
我们提出并研究了一套算法发现社区结构的网络自然划分的网络节点到密集连接的子群。我们的算法都有两个明确的特征：第一，它们涉及从网络中迭代删除边，将其分成社区，删除的边使用许多可能的“介数”度量中的任何一个来识别，第二，至关重要的是，这些度量在每次删除后都要重新计算。我们还提出了一个衡量我们的算法发现的社区结构的强度，这给了我们一个客观的度量来选择一个网络应该被划分成的社区的数量。我们证明了我们的算法是非常有效的发现社区结构在计算机生成的和现实世界的网络数据，并显示它们如何可以用来阐明有时令人生畏的复杂结构的网络系统。
We propose and study a set of algorithms for discovering community structure in networks-natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using any one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.