Tolerating the Community Detection Resolution Limit with Edge Weighting

Abstract

Communities of vertices within a giant network such as the World-Wide Web are likely to be vastly smaller than the network itself. However, Fortunato and Barthélemy have proved that modularity maximization algorithms for community detection may fail to resolve communities with fewer than $\sqrt{L/2}$ edges, where $L$ is the number of edges in the entire network. This resolution limit leads modularity maximization algorithms to have notoriously poor accuracy on many real networks. Fortunato and Barthélemy's argument can be extended to networks with weighted edges as well, and we derive this corollary argument. We conclude that weighted modularity algorithms may fail to resolve communities with fewer than $\sqrt{W\epsilon /2}$ total edge weight, where $W$ is the total edge weight in the network and $\epsilon$ is the maximum weight of an inter-community edge. If $\epsilon$ is small, then small communities can be resolved. Given a weighted or unweighted network, we describe how to derive new edge weights in order to achieve a low $\epsilon$, we modify the ``CNM'' community detection algorithm to maximize weighted modularity, and show that the resulting algorithm has greatly improved accuracy. In experiments with an emerging community standard benchmark, we find that our simple CNM variant is competitive with the most accurate community detection methods yet proposed.

revision with 8 pages 3 figures 2 tables

References in corpus (14)

• Modularity and community structure in networks
• Community detection in graphs
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Analysis of the structure of complex networks at different resolution levels
• Entropy measures for complex networks: Toward an information theory of complex topologies
• The entropy of network ensembles
• Assessing the relevance of node features for network structure
• Identifying network communities with a high resolution
• Statistical significance of communities in networks
• Accuracy and Precision of Methods for Community Identification in Weighted Networks

Cited by in corpus (42)

• Community detection in graphs
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Community Detection via Maximization of Modularity and Its Variants
• Engineering Parallel Algorithms for Community Detection in Massive Networks
• Mixing local and global information for community detection in large networks
• Enhancing community detection using a network weighting strategy
• Estimating the resolution limit of the map equation in community detection
• Hierarchical multiresolution method to overcome the resolution limit in complex networks
• The Input/Output Complexity of Triangle Enumeration
• A New Metric for Quality of Network Community Structure
• Using Triangles to Improve Community Detection in Directed Networks
• The Power of Pivoting for Exact Clique Counting
• Limitation of multi-resolution methods in community detection
• Degree Relations of Triangles in Real-world Networks and Models
• Identifying communities by influence dynamics in social networks
• Adaptive Modularity Maximization via Edge Weighting Scheme
• Approximately Counting Triangles in Sublinear Time
• Ensemble Clustering for Graphs
• Walk modularity and community structure in networks
• Enhancing community detection by local structural information
• Triangle counting in dynamic graph streams
• Network clustering and community detection using modulus of families of loops
• A simpler sublinear algorithm for approximating the triangle count
• An ensemble based on a bi-objective evolutionary spectral algorithm for graph clustering
• Mathematical and Algorithmic Analysis of Network and Biological Data
• On Large-Scale Graph Generation with Validation of Diverse Triangle Statistics at Edges and Vertices
• Evolution of Directed Triangle Motifs in the Google+ OSN
• Interplay between Topology and Edge Weights in Real-World Graphs: Concepts, Patterns, and an Algorithm
• Why do simple algorithms for triangle enumeration work in the real world?
• A New Community Definition For MultiLayer Networks And A Novel Approach For Its Efficient Computation
• On Approximating the Number of $k$-cliques in Sublinear Time
• Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE
• Structure-Preserving Community In A Multilayer Network: Definition, Detection, And Analysis
• Parallel Heuristics for Scalable Community Detection
• Bad Communities with High Modularity
• On Counting Triangles through Edge Sampling in Large Dynamic Graphs
• AOT: Pushing the Efficiency Boundary of Main-memory Triangle Listing
• Permanence and Community Structure in Complex Networks
• DegreeSketch: Distributed Cardinality Sketches on Massive Graphs with Applications
• An Efficient Framework for Computing Structure- And Semantics-Preserving Community in a Heterogeneous Multilayer Network
• REPT: A Streaming Algorithm of Approximating Global and Local Triangle Counts in Parallel
• Detectability threshold in weighted modular networks