Finding Community Structure in Mega-scale Social Networks

Abstract

Community analysis algorithm proposed by Clauset, Newman, and Moore (CNM algorithm) finds community structure in social networks. Unfortunately, CNM algorithm does not scale well and its use is practically limited to networks whose sizes are up to 500,000 nodes. The paper identifies that this inefficiency is caused from merging communities in unbalanced manner. The paper introduces three kinds of metrics (consolidation ratio) to control the process of community analysis trying to balance the sizes of the communities being merged. Three flavors of CNM algorithms are built incorporating those metrics. The proposed techniques are tested using data sets obtained from existing social networking service that hosts 5.5 million users. All the methods exhibit dramatic improvement of execution efficiency in comparison with the original CNM algorithm and shows high scalability. The fastest method processes a network with 1 million nodes in 5 minutes and a network with 4 million nodes in 35 minutes, respectively. Another one processes a network with 500,000 nodes in 50 minutes (7 times faster than the original algorithm), finds community structures that has improved modularity, and scales to a network with 5.5 million.

9 pages, 15 figures

References in corpus (6)

• Emergence of scaling in random networks
• Finding and evaluating community structure in networks
• Finding community structure in very large networks
• Defining and identifying communities in networks
• Finding Communities in Linear Time: A Physics Approach
• A Gap in the Community-Size Distribution of a Large-Scale Social Networking Site

Cited by in corpus (23)

• Community detection in graphs
• Mapping change in large networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Exploring the Free Energy Landscape: From Dynamics to Networks and Back
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Communities, Knowledge Creation, and Information Diffusion
• A Survey of Heterogeneous Information Network Analysis
• A Real-Time Detecting Algorithm for Tracking Community Structure of Dynamic Networks
• Limitation of multi-resolution methods in community detection
• LabelRank: A Stabilized Label Propagation Algorithm for Community Detection in Networks
• Ensemble approaches for improving community detection methods
• Multi-scale Dynamics in a Massive Online Social Network
• Consistent Community Identification in Complex Networks
• Hierarchical community detection by recursive partitioning
• Multi-level algorithms for modularity clustering
• Matching Community Structure Across Online Social Networks
• Extending modularity by capturing the similarity attraction feature in the null model
• Commonsense Reasoning and Large Network Analysis: A Computational Study of ConceptNet 4
• Estimating Network Parameters for Selecting Community Detection Algorithms
• Detecting Communities from Heterogeneous Graphs: A Context Path-based Graph Neural Network Model
• Network Community Detection with A Successive Spectral Relaxation Method
• On Varying Topology of Complex Networks and Performance Limitations of Community Detection Algorithms
• MODULAR: Software for the Autonomous Computation of Modularity in Large Network Sets