Near linear time algorithm to detect community structures in large-scale networks

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.

This article appears in the following collection:

Figure 1

An illustration of a dendrogram which is a tree representation of the order in which nodes are segregated into different groups or communities.

Figure 2

Nodes are updated one by one as we move from left to right. Due to a high density of edges (highest possible in this case), all nodes acquire the same label.

Figure 3

An example of a bi-partite network in which the label sets of the two parts are disjoint. In this case, due to the choices made by the nodes at step $t$, the labels on the nodes oscillate between $a$ and $b$.

Figure 4

(a)–(c) are three different community structures identified by the algorithm on Zachary’s karate club network. The communities can be identified by their shades of gray colors.

Figure 5

The grouping of U.S. college football teams into conferences are shown in (a) and (b). Each solution [(a) and (b)] is an aggregate of five different solutions obtained by applying the algorithm on the college football network.

Figure 6

Similarities between five different solutions obtained for each network is tabulated. An entry in the $i\text{th}$ row and $j\text{th}$ column in the lower triangle of each of the tables is the Jaccard’s similarity index for solutions $i$ and $j$ of the corresponding network. Entries in the $i\text{th}$ row and $j\text{th}$ column in the upper triangle of the tables are the values of the measure $f_{\text{same}}$ for solutions $i$ and $j$ in the respective networks. The range of modularity values $Q$ obtained for the five different solutions is also given for each network.

Figure 7

An example of aggregating two community structure solutions. $t_1$, $t_2$, $t_3$, and $t_4$ are labels on the nodes in a network obtained from solution 1 and denoted as $C^1$. The network is partitioned into groups of nodes having the same labels. $s_1$, $s_2$, and $s_3$ are labels on the nodes in the same network obtained from solution 2 and denoted as $C^2$. All nodes that had label $t_1$ in solution 1 are split into two groups with each group having labels $s_1$ and $s_2$, respectively, while all nodes with labels $t_3$, $t_4$, or $t_5$ in solution 1 have labels $s_3$ in solution 2. $C$ represents the new labels defined from $C^1$ and $C^2$.

Figure 8

Similarities between aggregate solutions obtained for each network. An entry in the $i\text{th}$ row and $j\text{th}$ column in the tables is Jaccard’s similarity index between the aggregate of the first $5i$ and the first $5j$ solutions. While similarities between solutions for the karate club friendship network and the protein-protein interaction network are represented in the lower triangles of the first two tables, the entries in the upper triangle of these two tables are for the U.S. college football network and the coauthorship network, respectively. The similarities between aggregate solutions for the WWW is given in the lower triangle of the third table.

Figure 9

The cumulative probability distributions of community sizes $\left(s\right)$ are shown for the WWW, coauthorship and actor collaboration networks. They approximately follow power laws with the exponents as shown.