Towards real-time community detection in large networks

Abstract

The recent boom of large-scale Online Social Networks (OSNs) both enables and necessitates the use of parallelisable 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 million nodes and about 58 million directed edges. Experiments and benchmarks reveal that the extended algorithm is not only faster but its community detection accuracy is compared favourably over popular modularity-gain optimization algorithms known to suffer from their resolution limits.

10 pages, 11 figures

References in corpus (13)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• Finding and evaluating community structure in networks
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Hierarchical organization of modularity in metabolic networks
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Identifying the role that individual animals play in their social network

Cited by in corpus (33)

• Community detection in graphs
• Finding statistically significant communities in networks
• Finding overlapping communities in networks by label propagation
• Detecting network communities by propagating labels under constraints
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Characterizing the community structure of complex networks
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Robust network community detection using balanced propagation
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• A Large-Scale Community Structure Analysis In Facebook
• Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering
• Large network community detection by fast label propagation
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• LabelRank: A Stabilized Label Propagation Algorithm for Community Detection in Networks
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Community detection by label propagation with compression of flow
• Label propagation for clustering
• Unfolding network communities by combining defensive and offensive label propagation
• Sequential Changepoint Approach for Online Community Detection
• Community Detection in Partially Observable Social Networks
• Fast Complex Network Clustering Algorithm Using Agents
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Secure Friend Discovery via Privacy-Preserving and Decentralized Community Detection
• Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm
• Role-based Label Propagation Algorithm for Community Detection
• Localized Algorithm of Community Detection on Large-Scale Decentralized Social Networks
• DANI: A Fast Diffusion Aware Network Inference Algorithm
• DynComm R Package -- Dynamic Community Detection for Evolving Networks
• Controlled Label Propagation: Preventing Over-Propagation through Gradual Expansion
• An Empirical Study of Community Detection Algorithms on Social and Road Networks
• Local Core Members Aided Community Structure Detection
• On the Analysis of a Label Propagation Algorithm for Community Detection