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

DOI10.3390/A10040112MaRDI QIDQ2633170zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Edler, Ludvig Bohlin, Martin Rosvall

Publication date 8 May 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(6)

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

Describes a project that uses

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)