Towards real-time community detection in large networks.

By Ian X. Y. Leung, Pan Hui, Pietro Liò, Jon Crowcroft. Physical review. E, Statistical, nonlinear, and soft matter physics, 2008

333 citations recorded by the source corpus.

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(m) 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 x 10(6) nodes and about 58 x 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.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/e8952aa675d2b5f466fac5f7a98191b56e23ba41

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Finding Statistically Significant Communities in Networks (2010, neutral): “[62], which were computed in a recent analysis [48].”
Community detection in graphs (2009, background): “Leung et al. have found that the original algorithm by Raghavan et al., applied on online social networks, often yields partitions with one giant community together with much smaller ones (Leung et al., 2009).”
Local search of communities in large graphs (2014, background): “In recent years, label propagation has attracted wide research interest since it in general can produce high-quality communities with almost linear time [15, 16].”
Community detection in Social Media (2012, methodology): “On the other hand, there are several recent methods (Blondel et al. 2008; Leung et al. 2009; Raghavan et al. 2007; Xu et al. 2007) from the other classes that present linear complexity to the number of network edges.”