Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems

Abstract

To comprehend the hierarchical organization of large integrated systems, we introduce the hierarchical map equation, which reveals multilevel structures in networks. In this information-theoretic approach, we exploit the duality between compression and pattern detection; by compressing a description of a random walker as a proxy for real flow on a network, we find regularities in the network that induce this system-wide flow. Finding the shortest multilevel description of the random walker therefore gives us the best hierarchical clustering of the network, the optimal number of levels and modular partition at each level, with respect to the dynamics on the network. With a novel search algorithm, we extract and illustrate the rich multilevel organization of several large social and biological networks. For example, from the global air traffic network we uncover countries and continents, and from the pattern of scientific communication we reveal more than 100 scientific fields organized in four major disciplines: life sciences, physical sciences, ecology and earth sciences, and social sciences. In general, we find shallow hierarchical structures in globally interconnected systems, such as neural networks, and rich multilevel organizations in systems with highly separated regions, such as road networks.

11 pages, 5 figures. For associated code, see http://www.tp.umu.se/~rosvall/code.html

References in corpus (20)

• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Community detection in graphs
• Finding community structure in very large networks
• Maps of random walks on complex networks reveal community structure
• Comparing community structure identification
• Community detection algorithms: a comparative analysis
• Hierarchical structure and the prediction of missing links in networks
• Hierarchical Organization in Complex Networks
• Link communities reveal multiscale complexity in networks
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• The map equation
• Mapping change in large networks
• Extracting the hierarchical organization of complex systems
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Multiresolution community detection for megascale networks by information-based replica correlations
• Networks and Cities: An Information Perspective
• Finding Community Structure in Mega-scale Social Networks

Cited by in corpus (90)

• Community detection in networks: A user guide
• Finding statistically significant communities in networks
• The role of gender in scholarly authorship
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Random walks and diffusion on networks
• Narrow scope for resolution-limit-free community detection
• Men Set Their Own Cites High: Gender and Self-citation across Fields and over Time
• Beyond similarity: A network approach for identifying and delimiting biogeographical regions
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Community detection in networks: Structural communities versus ground truth
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• Evaluating Overfit and Underfit in Models of Network Community Structure
• 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
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Faster unfolding of communities: speeding up the Louvain algorithm
• Structural transition in social networks: The role of homophily
• Mapping higher-order network flows in memory and multilayer networks with Infomap
• Ranking and clustering of nodes in networks with smart teleportation
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Z-score-based modularity for community detection in networks
• Subgraph-based filterbanks for graph signals
• Map equation for link community
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Estimating the resolution limit of the map equation in community detection
• Interest communities and flow roles in directed networks: the Twitter network of the UK riots
• Efficient community detection of network flows for varying Markov times and bipartite networks
• Mapping flows on hypergraphs
• Exploring the solution landscape enables more reliable network community detection
• Hierarchical communities in the walnut structure of the Japanese production network
• Perspective: network-guided pattern formation of neural dynamics
• Compression of Flow Can Reveal Overlapping-Module Organization in Networks
• Mesoscopic analysis of online social networks - The role of negative ties
• Static Ranking of Scholarly Papers using Article-Level Eigenfactor (ALEF)
• CGC: Contrastive Graph Clustering for Community Detection and Tracking
• Community Detection in Quantum Complex Networks
• Granularity of algorithmically constructed publication-level classifications of research publications: Identification of topics
• In a World That Counts: Clustering and Detecting Fake Social Engagement at Scale
• Cross-validation estimate of the number of clusters in a network
• Different approaches to community detection
• Mechanistic Models in Computational Social Science
• The inherent community structure of hyperbolic networks
• Hierarchical community structure in networks
• A divisive spectral method for network community detection
• Uncovering the Small Community Structure in Large Networks: A Local Spectral Approach
• Hierarchical networks of scientific journals
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Flow stability for dynamic community detection
• The Minimum Description Length Principle for Pattern Mining: A Survey
• Mapping flows on sparse networks with missing links
• Universal productivity patterns in research careers
• Characterization of the community structure in a large-scale production network in Japan
• Comparative analysis on the selection of number of clusters in community detection
• Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
• Diffusion on hierarchical systems of weakly-coupled networks
• Multifractal cross-correlation effects in two-variable time series of complex network vertex observables
• Global disorder transition in the community structure of large-q Potts systems
• Modular decomposition of protein structure using community detection
• Convex skeletons of complex networks
• Modular hierarchical and power-law small-world networks bear structural optima for minimal first passage times and cover time
• Criterions for locally dense subgraphs
• Iterative embedding and reweighting of complex networks reveals community structure
• Overlapping Community Detection via Local Spectral Clustering
• Benchmarking community detection methods on social media data
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Local multiresolution order in community detection
• Location Prediction: Communities Speak Louder than Friends
• Towards a generalization of information theory for hierarchical partitions
• Comparison and Benchmark of Graph Clustering Algorithms
• Efficient Personalized Community Detection via Genetic Evolution
• The Atlas for the Aspiring Network Scientist
• Flow-based Community Detection in Hypergraphs
• Single-trajectory map equation
• Latent Geometry Inspired Graph Dissimilarities Enhance Affinity Propagation Community Detection in Complex Networks
• Router-level community structure of the Internet Autonomous Systems
• Stochastic graph Voronoi tessellation reveals community structure
• Identifying macroscopic features in foreign visitor travel pathways
• Community detection and tracking on networks from a data fusion perspective
• Overcoming Bias in Community Detection Evaluation
• On role extraction for digraphs via neighbourhood pattern similarity
• A new methodology for constructing a publication-level classification system of science
• A multilevel network approach to revealing patterns of online political selective exposure
• Guided Machine Learning for power grid segmentation
• Improving Community Detection by Mining Social Interactions
• Multilayer Network Analysis of the Drug Pipeline in the Global Pharmaceutical Industry
• Application of a cognitive-inspired algorithm for detecting communities in mobility networks
• Mapping Inter-City Trade Networks to Maximum Entropy Models using Electronic Invoice Data
• Measuring inter-cluster similarities with Alpha Shape TRIangulation in loCal Subspaces (ASTRICS) facilitates visualization and clustering of high-dimensional data
• Hierarchical Latent Semantic Mapping for Automated Topic Generation
• Report on the Poblacion Flotante of Bogota (D.C.)