Near linear time algorithm to detect community structures in large-scale networks
Near linear time algorithm to detect community structures in large-scale networks
复制标题
DOI：
10.1103/physreve.76.036106
复制
发表时间：
2007-09-01
影响因子：
2.4
通讯作者：
Kumara, Soundar
中科院分区：
文献类型：
--
作者：
Raghavan, Usha Nandini;Albert, Reka;Kumara, Soundar
社区检测和分析是了解各种现实世界网络的组织的重要方法，并在社会社区中的共识形成或生物化学网络中功能模块的识别等各种问题中应用。当前使用的算法可以识别大型现实世界网络中社区结构需要先验信息，例如社区的数量和大小或计算上昂贵的信息。在本文中，我们研究了一种简单的标签传播算法，该算法仅使用网络结构作为指南，并且既不需要优化预定义的目标函数，也不需要有关社区的先验信息。在我们的算法中，每个节点都使用唯一标签初始化，并且在每个步骤中，每个节点都采用了大多数邻居当前具有的标签。在这种迭代过程中，在唯一标签上形成了社区的共识。我们通过将其应用于已知社区结构的网络来验证该算法。我们还证明，该算法几乎需要线性时间，因此计算在计算上比迄今为止可能还要便宜。
Community detection and analysis is an important methodology for understanding the organization of various real-world networks and has applications in problems as diverse as consensus formation in social communities or the identification of functional modules in biochemical networks. Currently used algorithms that identify the community structures in large-scale real-world networks require a priori information such as the number and sizes of communities or are computationally expensive. In this paper we investigate a simple label propagation algorithm that uses the network structure alone as its guide and requires neither optimization of a predefined objective function nor prior information about the communities. In our algorithm every node is initialized with a unique label and at every step each node adopts the label that most of its neighbors currently have. In this iterative process densely connected groups of nodes form a consensus on a unique label to form communities. We validate the algorithm by applying it to networks whose community structures are known. We also demonstrate that the algorithm takes an almost linear time and hence it is computationally less expensive than what was possible so far.