Randomized reference models for complex networks

Christian Lyngby Vestergaard, PhD

March 25th, 2022, 11am
Room : 26-00/332

Video: https://nuage.lip6.fr/s/db5bsrFMssEAoQD

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 non-trivial and susceptible to misinterpretation. I will describe a unified framework for the important class of RRMs generated by uniform shuffling procedures, which we by analogy to statistical physics will name microcanonical RRMs (MRRMs). MRRMs constrain chosen features to take exactly the same value as in the empirical network but are otherwise maximally random. Our framework lets us build a taxonomy of MRRMs that orders them and deduces their effects on important network features. It additionally tells us how we may generate new MRRMs by composition of existing ones. I will show examples of how the framework can be applied to unravel the influence of different features of an empirical network of mobile-phone calls on the spread of information and to characterize structural circuit motifs in the brain wiring diagrams (connectomes) of small animals. If time permits, I will finally discuss how we may use graph compression techniques to alleviate the statistical problems associated to classical null hypothesis testing for network motif discovery.
Reference: hal.archives-ouvertes.fr/hal-01817633v4