Randomized Reference Models for Temporal Networks

Laetitia Gauvin, Mathieu Génois, Márton Karsai, Mikko Kivelä, Taro Takaguchi, Eugenie Valdano, Christian L. Vestergaard

Research output: Contribution to journalArticleScientificpeer-review

10 Citations (Scopus)
144 Downloads (Pure)

Abstract

Many dynamical systems can be successfully analyzed by representing them as networks. Empirically measured networks and dynamic processes that take place in these situations show heterogeneous, non-Markovian, and intrinsically correlated topologies and dynamics. This makes their analysis particularly challenging. Randomized reference models (RRMs) have emerged as a general and versatile toolbox for studying such systems. Defined as random networks with given features constrained to match those of an input (empirical) network, they may, for example, be used to identify important features of empirical networks and their effects on dynamical processes unfolding in the network. RRMs are typically implemented as procedures that reshuffle an empirical network, making them very generally applicable. However, the effects of most shuffling procedures on network features remain poorly understood, rendering their use nontrivial and susceptible to misinterpretation. Here we propose a unified framework for classifying and understanding microcanonical RRMs (MRRMs) that sample networks with uniform probability. Focusing on temporal networks, we survey applications of MRRMs found in the literature, and we use this framework to build a taxonomy of MRRMs that proposes a canonical naming convention, classifies them, and deduces their effects on a range of important network features. We furthermore show that certain classes of MRRMs may be applied in sequential composition to generate new MRRMs from the existing ones surveyed in this article. We finally provide a tutorial showing how to apply a series of MRRMs to analyze how different network features affect a dynamic process in an empirical temporal network. Our taxonomy provides a reference for the use of MRRMs, and the theoretical foundations laid here may further serve as a base for the development of a principled and automatized way to generate and apply randomized reference models for the study of networked systems.
Original languageEnglish
Pages (from-to)763-830
JournalSIAM Review
Volume64
Issue number4
DOIs
Publication statusPublished - 3 Nov 2022
MoE publication typeA1 Journal article-refereed

Fingerprint

Dive into the research topics of 'Randomized Reference Models for Temporal Networks'. Together they form a unique fingerprint.

Cite this