Detecting community structure in networks
Detecting community structure in networks
复制标题
DOI：
10.1140/epjb/e2004-00124-y
复制
发表时间：
2004-03-01
影响因子：
1.6
通讯作者：
Newman, MEJ
中科院分区：
文献类型：
--
作者：
Newman, MEJ
最近，人们对网络中社区的算法产生了相当大的兴趣，社区是指一组顶点，其中的连接是密集的，但它们之间的连接是稀疏的。在此，我们回顾了在这方面取得的进展。开始，我们描述了一些传统的社区检测方法，如光谱平分，Kernighan-Lin算法和基于相似性度量的层次聚类。然而，这些方法中没有一种对于当前研究所关注的真实世界网络数据类型是理想的，例如互联网和web数据以及生物和社交网络。我们描述了一些最近的算法，似乎与这些数据，包括算法的基础上边缘介数分数，在网络中的短循环和电阻网络中的电压差。
There has been considerable recent interest in algorithms for finding communities in networks--groups of vertices within which connections are dense, but between which connections are sparser. Here we review the progress that has been made towards this end. We begin by describing some traditional methods of community detection, such as spectral bisection, the Kernighan-Lin algorithm and hierarchical clustering based on similarity measures. None of these methods, however, is ideal for the types of real-world network data with which current research is concerned, such as Internet and web data and biological and social networks. We describe a number of more recent algorithms that appear to work well with these data, including algorithms based on edge betweenness scores, on counts of short loops in networks and on voltage differences in resistor networks.