Past Networks Seminar

The discrete Hodge Laplacian offers a way to extract network topology and geometry from higher-ordered networks. The operator is inspired by concepts from algebraic topology and differential geometry and generalises the graph Laplacian. In particular, it allows to relate global structure of networks to the local properties of nodes. In my talk, I will talk about some general behaviour of the Hodge Laplacian and then continue to show how to use the extracted information to a) to use trajectory data infer the topology of the underlying network while simultaneously classifying the trajectories and b) to extract cell differentiation trees from single-cell data, an exciting new application in computational genomics.    

Networks provide a powerful language to model interacting systems by representing their units as nodes and the interactions between them as links. Interactions can be connotated in several ways, such as binary/weighted, undirected/directed, etc. In the present talk, we focus on the positive/negative connotation - modelling trust/distrust, alliance/enmity, friendship/conflict, etc. - by considering the so-called signed networks. Rooted in the psychological framework of the balance theory, the study of signed networks has found application in fields as different as biology, ecology, economics. Here, we approach it from the perspective of statistical physics by extending the framework of Exponential Random Graph Models to the class of binary un/directed signed networks and employing it to assess the significance of frustrated patterns in real-world networks. As our results reveal, it critically depends on i) the considered system and ii) the employed benchmark. For what concerns binary directed networks, instead, we explore the relationship between frustration and reciprocity and suggest an alternative interpretation of balance in the light of directionality. Finally,  leveraging the ERGMs framework, we propose an unsupervised algorithm to obtain statistically validated projections of bipartite signed networks, according to which any, two nodes sharing a statistically significant number of concordant (discordant) motifs are connected by a positive (negative) edge, and we investigate signed structures at the mesoscopic scale by evaluating the tendency of a configuration to be either `traditionally' or `relaxedly' balanced.

Our Random Walkers Induced temporal Graphs (RWIG) model generates temporal graph sequences based on M independent, random walkers that traverse an underlying graph as a function of time. Co-location of walkers at a given node and time defines an individual-level contact. RWIG is shown to be a realistic model for temporal human contact graphs.   

A key idea is that a random walk on a Markov graph executes the Markov process. Each of the M walkers traverses the same set of nodes (= states in the Markov graph), but with own transition probabilities (in discrete time) or rates (in continuous time). Hence, the Markov transition probability matrix P_j reflects the policy of motion of walker w_j. RWIG is analytically feasible: we derive closed form solutions for the probability distribution of contact graphs.

Usually, human mobility networks are inferred through measurements of timeseries of contacts between individuals. We also discuss this “inverse RWIG problem”, which aims to determine the parameters in RWIG (i.e. the set of probability transfer matrices P₁, P₂, ..., P_M and the initial probability state vectors s₁[0], ...,s_M[0] of walkers w₁,w₂, ...,w_M in discrete time), given a timeseries of contact graphs.

This talk is based on the article:
Almasan, A.-D., Shvydun, S., Scholtes, I. and P. Van Mieghem, 2025, "Generating Temporal Contact Graphs Using Random Walkers", IEEE Transactions on Network Science and Engineering, to appear.

While the brain has long been conceptualized as a network of neurons connected by synapses, attempts to describe the connectome using established models in network science have yielded conflicting outcomes, leaving the architecture of neural networks unresolved. Here, we analyze eight experimentally mapped connectomes, finding that the degree and the strength distribution of the underlying networks cannot be described by random nor scale-free models. Rather, the node degrees and strengths are well approximated by lognormal distributions, whose emergence lacks a mechanistic model in the context of networks. Acknowledging the fact that the brain is a physical network, whose architecture is driven by the spatially extended nature of its neurons, we analytically derive the multiplicative process responsible for the lognormal neuron length distribution, arriving to a series of empirically falsifiable predictions and testable relationships that govern the degree and the strength of individual neurons. The lognormal network characterizing the connectome represents a novel architecture for network science, that bridges critical gaps between neural structure and function, with unique implications for brain dynamics, robustness, and synchronization.

Real-world networks have a complex topology with many interconnected elements often organized into communities. Identifying these communities helps reveal the system’s organizational and functional structure. However, network data can be noisy, with incomplete link observations, making it difficult to detect significant community structures as missing data weakens the evidence for specific solutions. Recent research shows that flow-based community detection methods can highlight spurious communities in sparse networks with incomplete link observations. To address this issue, these methods require regularization. In this talk, I will show how a Bayesian approach can be used to regularize flows in networks, reducing overfitting in the flow-based community detection method known as the map equation.

Topically, my goal is to provide a fun and instructive introduction to graph cumulants: a hierarchical set of subgraph statistics that extend the classical cumulants (mean, (co)variance, skew, kurtosis, etc) to relational data.  

Intuitively, graph cumulants quantify the propensity (if positive) or aversion (if negative) for the appearance of any particular subgraph in a larger network.  

Concretely, they are derived from the “bare” subgraph densities via a Möbius inversion over the poset of edge partitions.  

Practically, they offer a systematic way to measure similarity between graph distributions, with a notable increase in statistical power compared to subgraph densities.  

Algebraically, they share the defining properties of cumulants, providing clever shortcuts for certain computations.  

Generally, their definition extends naturally to networks with additional features, such as edge weights, directed edges, and node attributes.  

Finally, I will discuss how this entire procedure of “cumulantification” suggests a promising framework for a motif-centric statistical analysis of general structured data, including temporal and higher-order networks, leaving ample room for exploration. 

Networks provide a powerful language to model and analyse interconnected systems. Their building blocks are  edges, which can  then be combined to form walks and paths, and thus define indirect relations between distant nodes and model flows across the system. In a traditional setting, network models are first-order, in the sense that flow across nodes is made of independent sequences of transitions. However, real-world systems often exhibit higher-order dependencies, requiring more sophisticated models. Here, we propose a variable-order network model that captures memory effects by interpolating between first- and second-order representations. Our method identifies latent modes that explain second-order behaviors, avoiding overfitting through a Bayesian prior. We introduce an interpretable measure to balance model size and description quality, allowing for efficient, scalable processing of large sequence data. We demonstrate that our model captures key memory effects with minimal state nodes, providing new insights beyond traditional first-order models and avoiding the computational costs of existing higher-order models.

All atmospheric phenomena, from daily weather patterns to the global climate system, are invariably influenced by atmospheric flow. Despite its importance, its complex behaviour makes extracting informative features from its dynamics challenging. In this talk, I will present a network-based approach to explore relationships between different flow structures. Using three phenomenon- and model-independent methods, we will investigate coherence patterns, vortical interactions, and Lagrangian coherent structures in an idealised model of the Northern Hemisphere stratospheric polar vortex. I will argue that networks built from fluid data retain essential information about the system's dynamics, allowing us to reveal the underlying interaction patterns straightforwardly and offering a fresh perspective on atmospheric behaviour.

Kirchhoff's celebrated matrix tree theorem expresses the number of spanning trees of a graph as the maximal minor of the Laplacian matrix of the graph. In modern language, this determinantal counting formula reflects the fact that spanning trees form a regular matroid. In this talk, I will give a short historical overview of the tree-counting problem and a related quantity from electrical circuit theory: the effective resistance. I will describe a characterization of effective resistances in terms of a certain polytope and discuss some recent applications to discrete notions of curvature on graphs. More details can be found in the recent preprint: https://arxiv.org/abs/2410.07756

Creating networks of statistical dependencies between brain regions is a powerful tool in neuroscience that has resulted in many new insights and clinical applications. However, recent interest in higher-order interactions has highlighted the need to address beyond-pairwise dependencies in brain activity. Multivariate information theory is one tool for identifying these interactions and is unique in its ability to distinguish between two qualitatively different modes of higher-order interactions: synergy and redundancy. I will present results from applying the O-information, the partial entropy decomposition, and the local O-information to resting state fMRI data. Each of these metrics indicate that higher-order interactions are widespread in the cortex, and further that they reveal different patterns of statistical dependencies than those accessible through pairwise methods alone. We find that highly synergistic subsystems typically sit between canonical functional networks and incorporate brain regions from several of these systems. Additionally, canonical networks as well as the interactions captured by pairwise functional connectivity analyses, are strongly redundancy-dominated. Finally, redundancy/synergy dominance varies in both space and time throughout an fMRI scan with notable recurrence of sets of brain regions engaging synergistically. As a whole, I will argue that higher-order interactions in the brain are an under-explored space that, made accessible with the tools of multivariate information theory, may offer novel insights.

Population structure substantially affects evolutionary dynamics. Networks that promote the spreading of fitter mutants are called amplifiers of selection, and those that suppress the spreading of fitter mutants are called suppressors of selection. It has been discovered that most networks are amplifiers under the so-called birth-death updating combined with uniform initialization, which is a common condition. We discuss constant-selection evolutionary dynamics with binary node states (which is equivalent to the biased voter model with two opinions in statistical physics research community) on higher-order networks, i.e., hypergraphs, temporal networks, and multilayer networks. In contrast to the case of conventional networks, we show that a vast majority of these higher-order networks are suppressors of selection, which we show by random-walk and Martingale analyses as well as by numerical simulations. Our results suggest that the modeling framework for structured populations in addition to the specific network structure is an important determinant of evolutionary dynamics.
 

The talk introduces an analytical framework for examining socio-spatial segregation across various spatial scales. This framework considers regional connectivity and population distribution, using an information theoretic approach to measure changes in socio-spatial segregation patterns across scales. It identifies scales where both high segregation and low connectivity occur, offering a topological and spatial perspective on segregation. Illustrated through a case study in Ecuador, the method is demonstrated to identify disconnected and segregated regions at different scales, providing valuable insights for planning and policy interventions.

Complex networks have become the main paradigm for modeling the dynamics of interacting systems. However, networks are intrinsically limited to describing pairwise interactions, whereas real-world systems are often characterized by interactions involving groups of three or more units. In this talk, I will consider social systems as a natural testing ground for higher-order network approaches (hypergraphs and simplicial complexes). I will briefly introduce models of social contagion and norm evolution on hypergraphs to show how the inclusion of higher-order mechanisms can lead to the emergence of novel phenomena such as discontinuous transitions and critical mass effects. I will then present some recent results on the role that structural features play on the emergent dynamics, and introduce a measure of hyper-coreness to characterize the centrality of nodes and inform seeding strategies. Finally, I will delve into the microscopic dynamics of empirical higher-order structures. I will study the mechanisms governing their temporal dynamics both at the node and group level, characterizing how individuals navigate groups and how groups form and dismantle. I will conclude by proposing a dynamical hypergraph model that closely reproduces the empirical observations.
 

TBA

Complex networks usually exhibit a rich architecture organized over multiple intertwined scales. Information pathways are expected to pervade these scales reflecting structural insights that are not manifest from analyses of the network topology. Moreover, small-world effects correlate with the different network hierarchies complicating identifying coexisting mesoscopic structures and functional cores. We present a communicability analysis of effective information pathways throughout complex networks based on information diffusion to shed further light on these issues. This leads us to formulate a new renormalization group scheme for heterogeneous networks. The Renormalization Group is the cornerstone of the modern theory of universality and phase transitions, a powerful tool to scrutinize symmetries and organizational scales in dynamical systems. However, its network counterpart is particularly challenging due to correlations between intertwined scales. The Laplacian RG picture for complex networks defines both the supernodes concept à la Kadanoff, and the equivalent momentum space procedure à la Wilson for graphs.

What do football passes and financial transactions have in common? Both are observable events in some real-world walk process that is happening over some network that is, however, not directly observable. In both cases, the basis for record-keeping is that these events move something tangible from one node to another. Here we explore process-driven approaches towards analyzing such data, with the goal of answering domain-specific research questions. First, we consider transaction data from a digital community currency recorded over 16 months. Because these are records of a real-world walk process, we know that the time-aggregated network is a flow network. Flow-based network analysis techniques let us concisely describe where and among whom this community currency was circulating. Second, we use a technique called trajectory extraction to transform football match event data into passing sequence data. This allows us to replicate classic results from sports science about possessions and uncover intriguing dynamics of play in five first-tier domestic leagues in Europe during the 2017-18 club season. Taken together, these two applied examples demonstrate the interpretability of process-driven approaches as opposed to, e.g., temporal network analysis, when the data are records of a real-world walk processes.

Understanding the stability of ecological communities is a matter of increasing importance in the context of global environmental change. Yet it has proved to be a challenging task. Different metrics are used to assess the stability of ecological systems, and the choice of one metric over another may result in conflicting conclusions. While the need to consider this multitude of stability metrics has been clearly stated in the ecological literature for decades, little is known about how different stability metrics relate to each other. I’ll present results of dynamical simulations of ecological communities investigating the correlations between frequently used stability metrics, and I will discuss how these results may contribute to make progress in the quantification of stability in theory and in practice.

Zoom Link: https://zoom.us/j/93174968155?pwd=TUJ3WVl1UGNMV0FxQTJQMFY0cjJNdz09

Meeting ID: 931 7496 8155

Passcode: 502784

Many networks exhibit some community structure. There exists a wide variety of approaches to detect communities in networks, each offering different interpretations and associated algorithms. For large networks, there is the additional requirement of speed. In this context, the so-called label propagation algorithm (LPA) was proposed, which runs in near linear time. In partitions uncovered by LPA, each node is ensured to have most links to its assigned community. We here propose a fast variant of LPA (FLPA) that is based on processing a queue of nodes whose neighbourhood recently changed. We test FLPA exhaustively on benchmark networks and empirical networks, finding that it runs up to 700 times faster than LPA. In partitions found by FLPA, we prove that each node is again guaranteed to have most links to its assigned community. Our results show that FLPA is generally preferable to LPA.

Spectral methods offer a tractable, global framework for clustering in graphs via eigenvector computations on graph matrices. Hypergraph data, in which entities interact on edges of arbitrary size, poses challenges for matrix representations and therefore for spectral clustering. We study spectral clustering for arbitrary hypergraphs based on the hypergraph nonbacktracking operator. After reviewing the definition of this operator and its basic properties, we prove a theorem of Ihara-Bass type which allows eigenpair computations to take place on a smaller matrix, often enabling faster computation. We then propose an alternating algorithm for inference in a hypergraph stochastic blockmodel via linearized belief-propagation which involves a spectral clustering step, again using nonbacktracking operators. We provide proofs related to this algorithm that both formalize and extend several previous results. We pose several conjectures about the limits of spectral methods and detectability in hypergraph stochastic blockmodels in general, supporting these with in-expectation analysis of the eigeinpairs of our studied operators. We perform experiments with real and synthetic data that demonstrate the benefits of hypergraph methods over graph-based ones when interactions of different sizes carry different information about cluster structure.

Joint work with Nicole Eikmeier (Grinnell) and Jamie Haddock (Harvey Mudd).

Identifying the hidden organizational principles and relevant structures of complex networks is fundamental to understand their properties. To this end, uncovering the structures involving the prominent nodes in a network is an effective approach. In temporal networks, the simultaneity of connections is crucial for temporally stable structures to arise. In this work, we propose a measure to quantitatively investigate the tendency of well-connected nodes to form simultaneous and stable structures in a temporal network. We refer to this tendency as the temporal rich club phenomenon, characterized by a coefficient defined as the maximal value of the density of links between nodes with a minimal required degree, which remain stable for a certain duration. We illustrate the use of this concept by analysing diverse data sets and their temporal properties, from the role of cohesive structures in relation to processes unfolding on top of the network to the study of specific moments of interest in the evolution of the network.

Article link: https://www.nature.com/articles/s41567-022-01634-8

The structure of complex networks can be characterized by counting and analyzing network motifs, which are small graph structures that occur repeatedly in a network, such as triangles or chains. Recent work has generalized motifs to temporal and dynamic network data. However, existing techniques do not generalize to sequential or trajectory data, which represents entities walking through the nodes of a network, such as passengers moving through transportation networks. The unit of observation in these data is fundamentally different, since we analyze observations of walks (e.g., a trip from airport A to airport C through airport B), rather than independent observations of edges or snapshots of graphs over time. In this work, we define sequential motifs in trajectory data, which are small, directed, and sequenced-ordered graphs corresponding to patterns in observed sequences. We draw a connection between counting and analysis of sequential motifs and Higher-Order Network (HON) models. We show that by mapping edges of a HON, specifically a kth-order DeBruijn graph, to sequential motifs, we can count and evaluate their importance in observed data, and we test our proposed methodology with two datasets: (1) passengers navigating an airport network and (2) people navigating the Wikipedia article network. We find that the most prevalent and important sequential motifs correspond to intuitive patterns of traversal in the real systems, and show empirically that the heterogeneity of edge weights in an observed higher-order DeBruijn graph has implications for the distributions of sequential motifs we expect to see across our null models.

ArXiv link: https://arxiv.org/abs/2112.05642

Social, biological and physical systems are widely studied through the modeling of dynamical processes over networks, and one commonly investigates the interplay between structure and dynamics. I will discuss how cyclic patterns in networks can influence models for collective and diffusive processes, including generalized models in which dynamics are defined over simplicial complexes and multiplex networks. Our approach relies on homology theory, which is the subfield of mathematics that formally studies cycles (and more generally, k-dimensional holes). We will make use of techniques including persistent homology and Hodge theory to examine the role of cycles in helping organize dynamics onto low-dimensional manifolds. This pursuit represents an emerging interface between the fields of network-coupled dynamical systems and topological data analysis.