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.

12 pages, 7 figures

References in corpus (10)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• 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
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Narrow scope for resolution-limit-free community detection
• Parsimonious module inference in large networks
• Limited resolution in complex network community detection with Potts model approach

Cited by in corpus (17)

• 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
• Community detection in weighted brain connectivity networks beyond the resolution limit
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Router-level community structure of the Internet Autonomous Systems
• Single-trajectory map equation
• Community Structure and Its Stability on a Face-to-Face Interaction Network in Kyoto City
• Hyperbolic Multiplex Network Embedding with Maps of Random Walk