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

DOI10.3390/A10040112zbMATH Open1462.90027arXiv1706.04792OpenAlexW2626759838WikidataQ57270514 ScholiaQ57270514MaRDI QIDQ2633170FDOQ2633170

Authors: Daniel Edler, Ludvig Bohlin, Martin Rosvall 

Publication date: 8 May 2019

Published in: Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1706.04792

Recommendations

• Flow-Based Community Detection in Hypergraphs
• Information dynamics algorithm for detecting communities in networks
• Characterizing flows by complex network methods
• Detecting network communities: a new systematic and efficient algorithm
• Fast unfolding of communities in large networks

zbMATH Keywords

community detectionmultilayer networksoverlapping communitiesmemory networkshigher-order network flowsInfomap

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Applications of graph theory (05C90) Deterministic network models in operations research (90B10) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• A Mathematical Theory of Communication
• Complex networks: structure and dynamics
• Emergence of Scaling in Random Networks
• Fast unfolding of communities in large networks
• Structure of triadic relations in multiplex networks
• Limits of Predictability in Human Mobility
• Human mobility and time spent at destination: impact on spatial epidemic spreading
• On multiaspect graphs

Cited In (6)

• The minimum description length principle for pattern mining: a survey
• The why, how, and when of representations for complex systems
• Adapting infomap to absorbing random walks using absorption-scaled graphs
• Information Networks With In-Block Memory
• Flow-Based Community Detection in Hypergraphs
• An analytic strategy for data processing of multimode networks

Uses Software

• GenLouvain
• GossipMap

This page was built for publication: Mapping higher-order network flows in memory and multilayer networks with Infomap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2633170)