Efficient and principled method for detecting communities in networks
Efficient and principled method for detecting communities in networks
复制标题
DOI：
10.1103/physreve.84.036103
复制
发表时间：
2011-09-08
影响因子：
2.4
通讯作者：
Newman, M. E. J.
中科院分区：
文献类型：
--
作者：
Ball, Brian;Karrer, Brian;Newman, M. E. J.
网络数据分析中的一个基本问题是检测网络社区，即密集互连的节点群，这些节点可能重叠或不相交。在这里，我们描述了一种基于生成网络模型的原则统计方法来寻找重叠社区的方法。我们展示了如何使用快速、封闭形式的期望最大化算法来实现该方法，该算法允许我们在合理的运行时间内分析数百万个节点的网络。我们在现实世界的网络和综合基准测试中测试了该方法，发现它的结果与以前的方法相比具有竞争力。我们还证明了同样的方法可以用于通过松弛方法提取非重叠的社区划分，并证明了该算法对于非重叠问题具有竞争力的快速和准确。
A fundamental problem in the analysis of network data is the detection of network communities, groups of densely interconnected nodes, which may be overlapping or disjoint. Here we describe a method for finding overlapping communities based on a principled statistical approach using generative network models. We show how the method can be implemented using a fast, closed-form expectation-maximization algorithm that allows us to analyze networks of millions of nodes in reasonable running times. We test the method both on real-world networks and on synthetic benchmarks and find that it gives results competitive with previous methods. We also show that the same approach can be used to extract nonoverlapping community divisions via a relaxation method, and demonstrate that the algorithm is competitively fast and accurate for the nonoverlapping problem.