Estimating the resolution limit of the map equation in community detection

Abstract

A community detection algorithm is considered to have a resolution limit if the scale of the smallest modules that can be resolved depends on the size of the analyzed subnetwork. The resolution limit is known to prevent some community detection algorithms from accurately identifying the modular structure of a network. In fact, any global objective function for measuring the quality of a two-level assignment of nodes into modules must have some sort of resolution limit or an external resolution parameter. However, it is yet unknown how the resolution limit affects the so-called map equation, which is known to be an efficient objective function for community detection. We derive an analytical estimate and conclude that the resolution limit of the map equation is set by the total number of links between modules instead of the total number of links in the full network as for modularity. This mechanism makes the resolution limit much less restrictive for the map equation than for modularity, and in practice orders of magnitudes smaller. Furthermore, we argue that the effect of the resolution limit often results from shoehorning multi-level modular structures into two-level descriptions. As we show, the hierarchical map equation effectively eliminates the resolution limit for networks with nested multi-level modular structures.

arXiv comment12 pages, 7 figures

References in corpus (24)

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Resolution limit in community detection
• Community detection algorithms: a comparative analysis
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• The performance of modularity maximization in practical contexts
• Limits of modularity maximization in community detection
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Narrow scope for resolution-limit-free community detection
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Local resolution-limit-free Potts model for community detection
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• Limited resolution in complex network community detection with Potts model approach
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Significant Scales in Community Structure
• Ranking and clustering of nodes in networks with smart teleportation
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Exploring the limits of community detection strategies in complex networks

Cited by in corpus (18)

• Increasing trend of scientists to switch between topics
• Mapping higher-order network flows in memory and multilayer networks with Infomap
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Community detection in networks using graph embeddings
• Hierarchical communities in the walnut structure of the Japanese production network
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Extracting Complements and Substitutes from Sales Data: A Network Perspective
• Comparative analysis on the selection of number of clusters in community detection
• Link community detection through global optimization and the inverse resolution limit of partition density
• Distributed Graph Clustering using Modularity and Map Equation
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• Community detection in weighted brain connectivity networks beyond the resolution limit
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Single-trajectory map equation
• Router-level community structure of the Internet Autonomous Systems
• Community Structure and Its Stability on a Face-to-Face Interaction Network in Kyoto City
• Hyperbolic Multiplex Network Embedding with Maps of Random Walk