Mapping higher-order network flows in memory and multilayer networks with Infomap

Abstract

Comprehending complex systems by simplifying and highlighting important dynamical patterns requires modeling and mapping higher-order network flows. However, complex systems come in many forms and demand a range of representations, including memory and multilayer networks, which in turn call for versatile community-detection algorithms to reveal important modular regularities in the flows. Here we show that various forms of higher-order network flows can be represented in a unified way with networks that distinguish physical nodes for representing a~complex system's objects from state nodes for describing flows between the objects. Moreover, these so-called sparse memory networks allow the information-theoretic community detection method known as the map equation to identify overlapping and nested flow modules in data from a range of~different higher-order interactions such as multistep, multi-source, and temporal data. We derive the map equation applied to sparse memory networks and describe its search algorithm Infomap, which can exploit the flexibility of sparse memory networks. Together they provide a general solution to reveal overlapping modular patterns in higher-order flows through complex systems.

23 pages, 4 figures

References in corpus (21)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Maps of random walks on complex networks reveal community structure
• The architecture of complex weighted networks
• The structure and dynamics of multilayer networks
• Temporal Networks
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Link communities reveal multiscale complexity in networks
• Mathematical Formulation of Multi-Layer Networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Memory in network flows and its effects on spreading dynamics and community detection
• Representing higher-order dependencies in networks
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• Natural human mobility patterns and spatial spread of infectious diseases
• Betweenness Preference: Quantifying Correlations in the Topological Dynamics of Temporal Networks
• Modeling sequences and temporal networks with dynamic community structures
• When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks
• Ranking and clustering of nodes in networks with smart teleportation
• Predictability of conversation partners
• Estimating the resolution limit of the map equation in community detection
• Maps of sparse Markov chains efficiently reveal community structure in network flows with memory

Cited by in corpus (20)

• Mapping flows on hypergraphs
• Multilayer Network Science: from Cells to Societies
• Map Equation Centrality: Community-aware Centrality based on the Map Equation
• The Minimum Description Length Principle for Pattern Mining: A Survey
• Diffusion geometry of multiplex and interdependent systems
• Mapping flows on sparse networks with missing links
• Mapping flows on weighted and directed networks with incomplete observations
• Understanding Complex Systems: From Networks to Optimal Higher-Order Models
• Stratified communities in complex business networks
• Mapping Flows on Bipartite Networks
• Cross-validation of correlation networks using modular structure
• Locating Community Smells in Software Development Processes Using Higher-Order Network Centralities
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Identifying robust features of community structure in complex networks
• Flow-based Community Detection in Hypergraphs
• Single-trajectory map equation
• Identifying macroscopic features in foreign visitor travel pathways
• Representing Big Data as Networks: New Methods and Insights
• Latent geometry emerging from network-driven processes
• Data-driven Clustering in Ad-hoc Networks based on Community Detection