Towards real-time community detection in large networks

The recent boom of large-scale online social networks (OSNs) both enables and necessitates the use of parallelizable and scalable computational techniques for their analysis. We examine the problem of real-time community detection and a recently proposed linear time—$O\left(m\right)$ on a network with $m$ edges—label propagation, or “epidemic” community detection algorithm. We identify characteristics and drawbacks of the algorithm and extend it by incorporating different heuristics to facilitate reliable and multifunctional real-time community detection. With limited computational resources, we employ the algorithm on OSN data with $1\times {10}^6$ nodes and about $58\times {10}^6$ directed edges. Experiments and benchmarks reveal that the extended algorithm is not only faster but its community detection accuracy compares favorably over popular modularity-gain optimization algorithms known to suffer from their resolution limits.

Figure 1

Snapshot of a subgraph of an OSN (500 nodes).

Figure 2

Each node is looked at in a certain order and a new label is selected. The above shows how nodes in a 4-clique self-organize into one single community in one iteration.

Figure 3

The above plots show the number of iterations required before convergence for both the synchronous and asynchronous implementations on a random graph of size $N$ with probability of pairwise connection $p$. All values here are averaged over 100 realizations.

Figure 4

This substructure is constructed on an $N$-clique, $N=25$, by attaching each new node, labeled $l$, $N<l<2N$, to existing nodes $l-1,\dots ,2\left(l-N\right)$, thus contains 49 $\left(2N-1\right)$ nodes and 600 $\left[N\left(N-1\right)\right]$ edges.

Figure 5

The relationships between the number of iterations required before convergence, $k$, of both implementations to the size, $N$, of the aforementioned structure. All values here are averaged over 100 realizations.

Figure 6

Average performances of asynchronous and synchronous LPA. Values are averaged over five runs. Shaded area denotes the range of the performances of asynchronous implementation.

Figure 7

The community-size distribution of communities uncovered by the algorithm, which follows a two-part power law.

Figure 8

Average performance comparisons of the synchronous and asynchronous implementations with varying $\delta$ and $m$ over five runs.

Figure 9

(Color online) Community detection in the OSN $\left(\text{n}=3000\right)$ by gradually decreasing hop attenuation ($\delta =0.5$ at the top with $Q=0.64$ and $\delta =0$ at the bottom with $Q=0.78$). Nodes with three or less neighbors are filtered to ease the visualization [21].

Figure 10

The difference in percent modularity and speed of the optimized modifications with the original.

Figure 11

Average performance comparisons between the three algorithms in the benchmark graphs with size $N$ and average degree $\overline{d}$. Both versions of LPA here are asynchronous; LPA-$\delta$ implements a gradually decreasing $\delta$ as discussed in Sec. 4B. All benchmark graphs have power-law degree and cluster-size distributions with exponents 3 and 2. For $N=1000$, the results are the average over 100 realizations; for $N=5000$, over 10 realizations.