Empirical Comparison of Algorithms for Network Community Detection

Abstract

Detecting clusters or communities in large real-world graphs such as large social or information networks is a problem of considerable interest. In practice, one typically chooses an objective function that captures the intuition of a network cluster as set of nodes with better internal connectivity than external connectivity, and then one applies approximation algorithms or heuristics to extract sets of nodes that are related to the objective function and that "look like" good communities for the application of interest. In this paper, we explore a range of network community detection methods in order to compare them and to understand their relative performance and the systematic biases in the clusters they identify. We evaluate several common objective functions that are used to formalize the notion of a network community, and we examine several different classes of approximation algorithms that aim to optimize such objective functions. In addition, rather than simply fixing an objective and asking for an approximation to the best cluster of any size, we consider a size-resolved version of the optimization problem. Considering community quality as a function of its size provides a much finer lens with which to examine community detection algorithms, since objective functions and approximation algorithms often have non-obvious size-dependent behavior.

References in corpus (12)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Resolution limit in community detection
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Finding local community structure in networks
• Robustness of community structure in networks
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters

Cited by in corpus (46)

• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Community detection in node-attributed social networks: a survey
• Epidemic spreading on complex networks with community structures
• Applying Machine Learning Techniques for Caching in Edge Networks: A Comprehensive Survey
• Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts
• Spatio-Temporal Data Mining: A Survey of Problems and Methods
• Graph-based Anomaly Detection and Description: A Survey
• Accelerating Community Detection by Using K-core Subgraphs
• A testing based extraction algorithm for identifying significant communities in networks
• Ant Colony Optimization with a New Random Walk Model for Community Detection in Complex Networks
• Systems Applications of Social Networks
• On the Permanence of Vertices in Network Communities
• Social Network Fusion and Mining: A Survey
• Discovering Social Circles in Ego Networks
• A Short Introduction to Local Graph Clustering Methods and Software
• What do Vegans do in their Spare Time? Latent Interest Detection in Multi-Community Networks
• Defining and Evaluating Network Communities based on Ground-truth
• A k-core Decomposition Framework for Graph Clustering
• From which world is your graph?
• Community Detection Algorithm Evaluation using Size and Hashtags
• Extending modularity by capturing the similarity attraction feature in the null model
• Implementing regularization implicitly via approximate eigenvector computation
• Approximate Computation and Implicit Regularization for Very Large-scale Data Analysis
• A Local Spectral Method for Graphs: with Applications to Improving Graph Partitions and Exploring Data Graphs Locally
• Compressive Network Analysis
• Efficient Community Detection in Large Networks using Content and Links
• The Small-Community Phenomenon in Networks
• Revisiting Spectral Graph Clustering with Generative Community Models
• Finding compact communities in large graphs
• Community detection algorithm evaluation with ground-truth data
• Triangles as basis to detect communities: an application to Twitter's network
• Leveraging Evolution Dynamics to Generate Benchmark Complex Networks with Community Structures
• Real-Time Community Detection in Large Social Networks on a Laptop
• Understanding Co-evolution in Large Multi-relational Social Networks
• Mutual or Unrequited Love: Identifying Stable Clusters in Social Networks with Uni- and Bi-directional Links
• Terminal-Set-Enhanced Community Detection in Social Networks
• Evaluating community structure in large network with random walks
• People Like Us: Mining Scholarly Data for Comparable Researchers
• Detecting and Characterizing Small Dense Bipartite-like Subgraphs by the Bipartiteness Ratio Measure
• From Community Detection to Community Profiling
• Estimating Mixed-Memberships Using the Symmetric Laplacian Inverse Matrix
• An optimization approach to locally-biased graph algorithms
• On Varying Topology of Complex Networks and Performance Limitations of Community Detection Algorithms
• From the User to the Medium: Neural Profiling Across Web Communities
• From Community Detection to Community Deception
• NEDindex: A new metric for community structure in networks