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.

Combining physics with machine learning is a rapidly growing field of research. Thereby, most work focuses on leveraging machine learning methods to solve problems in physics. Here, however, we focus on the reverse direction of leveraging structure of physical systems (e.g. dynamical systems modeled by ODEs or PDEs) to construct novel machine learning algorithms, where the existence of highly desirable properties of the underlying method can be rigorously proved. In particular, we propose several physics-inspired deep learning architectures for sequence modelling as well as for graph representation learning. The proposed architectures mitigate central problems in each corresponding domain, such as the vanishing and exploding gradients problem for recurrent neural networks or the oversmoothing problem for graph neural networks. Finally, we show that this leads to state-of-the-art performance on several widely used benchmark problems.

Chimera states have attracted significant attention as symmetry-broken states exhibiting the coexistence of coherence and incoherence. Despite the valuable insights gained by analyzing specific systems, the understanding of the physical mechanism underlying the emergence of chimeras has been incomplete. In this presentation, I will argue that an important class of stable chimeras arise because coherence in part of the system is sustained by incoherence in the rest of the system. This mechanism may be regarded as a deterministic analog of noise-induced synchronization and is shown to underlie the emergence of so-called strong chimeras. These are chimera states whose coherent domain is formed by identically synchronized oscillators. The link between coherence and incoherence revealed by this mechanism also offers insights into the dynamics of a broader class of states, including switching chimera states and incoherence-mediated remote synchronization.

Synchronization, epidemic processes and information spreading are natural processes that emerge from the interaction between people. Mathematically, all of them can be described by models that, despite their simplicity, they can predict collective behaviors. In addition, they have in common a very interesting feature: a phase transition from an active state to an absorbing state. For example, the spread of an epidemic is characterized by the infection rate, the control parameter, which basically determines whether the epidemic will spread in the network or, if this rate is very low, few people become infected and the system falls into an absorbing state where there are no more infected people. In this presentation we will present the analytical and computational approaches used to investigate these classical models of statistical physics that present phase transitions and we will also show how the network topology influences such dynamical processes. The behavior of such dynamics can be much richer than we imagine.

Co-occurrence networks formed by bipartite projection are widely studied in many contexts, including politics (bill co-sponsorship), bibliometrics (paper co-authorship), ecology (species co-habitation), and genetics (protein co-expression). It is often useful to focus on the backbone, a binary representation that includes only the most important edges, however many different backbone extraction models exist. In this talk, I will demonstrate the "backbone" package for R, which implements many such models. I will also use it to compare two promising null models: the fixed degree sequence model (FDSM) that imposes hard constraints, and the stochastic degree sequence model (SDSM) that imposes soft constraints, on the bipartite degree sequences. While FDSM is more statistically powerful, SDSM is more efficient and offers a close approximation.

In this talk I will present network-theoretic tools [1-2] to filter information in large-scale datasets and I will show that these are powerful tools to study complex datasets. In particular I will introduce correlation-based information filtering networks and the planar filtered graphs (PMFG) and I will show that applications to financial data-sets can meaningfully identify industrial activities and structural market changes [3-4].

It has been shown that by making use of the 3-clique structure of the PMFG a clustering can be extracted allowing dimensionality reduction that keeps both local information and global hierarchy in a deterministic manner without the use of any prior information [5-6]. However, the algorithm so far proposed to construct the PMFG is numerically costly with O(N3) computational complexity and cannot be applied to large-scale data. There is therefore scope to search for novel algorithms that can provide, in a numerically efficient way, such a reduction to planar filtered graphs. I will introduce a new algorithm, the TMFG (Triangulated Maximally Filtered Graph), that efficiently extracts a planar subgraph which optimizes an objective function. The method is scalable to very large datasets and it can take advantage of parallel and GPUs computing [7]. Filtered graphs are valuable tools for risk management and portfolio optimization too [8-9] and they allow to construct probabilistic sparse modeling for financial systems that can be used for forecasting, stress testing and risk allocation [10].

Filtered graphs can be used not only to extract relevant and significant information but more importantly to extract knowledge from an overwhelming quantity of unstructured and structured data. I will provide a practitioner example by a successful Silicon Valley start-up, Yewno. The key idea underlying Yewno’s products is the concept of the Knowledge Graph, a framework based on filtered graph research, whose goal is to extract signals from evolving corpus of data. The common principle is that a methodology leveraging on developments in Computational linguistics and graph theory is used to build a graph representation of knowledge [11], which can be automatically analysed to discover hidden relations between components in many different complex systems. This Knowledge Graph based framework and inference engine has a wide range of applications, including finance, economics, biotech, law, education, marketing and general research.

[1] T. Aste, T. Di Matteo, S. T. Hyde, Physica A 346 (2005) 20.

[2] T. Aste, Ruggero Gramatica, T. Di Matteo, Physical Review E 86 (2012) 036109.

[3] M. Tumminello, T. Aste, T. Di Matteo, R. N. Mantegna, PNAS 102, n. 30 (2005) 10421.

[4] N. Musmeci, Tomaso Aste, T. Di Matteo, Journal of Network Theory in Finance 1(1) (2015) 1-22.

[5] W.-M. Song, T. Di Matteo, and T. Aste, PLoS ONE 7 (2012) e31929.

[6] N. Musmeci, T. Aste, T. Di Matteo, PLoS ONE 10(3): e0116201 (2015).

[7] Guido Previde Massara, T. Di Matteo, T. Aste, Journal of Complex networks 5 (2), 161 (2016).

[8] F. Pozzi, T. Di Matteo and T. Aste, Scientific Reports 3 (2013) 1665.

[9] N. Musmeci, T. Aste and T. Di Matteo, Scientific Reports 6 (2016) 36320.

[10] Wolfram Barfuss, Guido Previde Massara, T. Di Matteo, T. Aste, Phys.Rev. E 94 (2016) 062306.

[11] Ruggero Gramatica, T. Di Matteo, Stefano Giorgetti, Massimo Barbiani, Dorian Bevec and Tomaso Aste, PLoS One (2014) PLoS ONE 9(1): e84912.

Pair combination repurposing of drugs is a common challenge faced by researchers in the pharmaceutical industry. Network biology and molecular machine learning based drug pair scoring techniques offer computation tools to predict the interaction, polypharmacy side effects and synergy of drugs. In this talk we overview of three things: (a) the theory and unified model of drug pair scoring (b) a relational machine learning model that can solve the pair scoring task (c) the design of large-scale machine learning systems needed to tackle the pair scoring task.

ArXiv links: https://arxiv.org/abs/2111.02916, https://arxiv.org/abs/2110.15087, https://arxiv.org/abs/2202.05240.

ML library: https://github.com/AstraZeneca/chemicalx

Random walks are a common model for the exploration and discovery of complex networks. While numerous algorithms have been proposed to map out an unknown network, a complementary question arises: in a known network, which nodes and edges are most likely to be discovered by a random walker in finite time? In this talk we introduce exposure theory, a statistical mechanics framework that predicts the learning of nodes and edges across several types of networks, including weighted and temporal, and show that edge learning follows a universal trajectory. While the learning of individual nodes and edges is noisy, exposure theory produces a highly accurate prediction of aggregate exploration statistics. As a specific application, we extend exposure theory to better understand human learning with its typical mental errors, and thus account for distortions of learned networks.

This talk is based on https://arxiv.org/abs/2202.11262

In this talk we will look at the different ways to define city boundaries, and the relevance to consider socio-demographic and spatial connectivity in urban systems, in particular if interventions are to be considered.

Data that have an intrinsic network structure are becoming increasingly common in various scientific applications. Compressing such data for storage or transmission is an important problem, especially since networks are increasingly large. From an information theoretic perspective, the limit to compression of a random graph is given by the Shannon entropy of its distribution. A relevant question is how much of the information content of a random graph pertains to its structure (i.e., the unlabelled version of the graph), and how much of it is contained in the labels attached to the structure. Furthermore, in applications in which one is interested only in structural properties of a graph (e.g., node degrees, connectedness, frequency of occurrence of certain motifs), the node labels are irrelevant, such that only the structure of the graph needs to be compressed, leading to a more compact representation. In this talk, I will consider the random geometric graph (RGG), where pairs of nodes are connected based on the distance between them in some latent space. This model captures well important characteristics of biological systems, information networks, social networks, or economic networks. Since determination of the entropy is extremely difficult for this model, I will present upper bounds we obtained for the entropy of the labelled RGG. Then, we will focus on the structural information in the one-dimensional RGG. I will show our latest results in terms of the number of structures in the considered model and bounds on the structural entropy, together with the asymptotic behaviour of the bounds for different regimes of the connection range. Finally, I will also present a simple encoding scheme for one-dimensional RGG structures that asymptotically achieves the obtained upper limit on the structural entropy.

arXiv link: https://arxiv.org/abs/2107.13495

The non-backtracking matrix and its eigenvalues have many applications in network science and graph mining. For example, in network epidemiology, the reciprocal of the largest eigenvalue of the non-backtracking matrix is a good approximation for the epidemic threshold of certain network dynamics. In this work, we develop techniques that identify which nodes have the largest impact on the leading non-backtracking eigenvalue. We do so by studying the behavior of the spectrum of the non-backtracking matrix after a node is removed from the graph, which can be thought of as immunizing a node against the spread of disease. From this analysis we derive a centrality measure which we call X-degree, which is then used to predict which nodes have a large influence in the epidemic threshold. Finally, we discuss work currently in progress on connections with eigenvector localization and percolation theory.

Measures of discrete curvature are a recent addition to the toolkit of network analysts and data scientists. At the basis lies the idea that networks and other discrete objects exhibit distinct geometric properties that resemble those of smooth objects like surfaces and manifolds, and that we can thus find inspiration in the tools of differential geometry to study these discrete objects. In this talk, I will introduce how this has lead to the development of notions of discrete curvature, and what they are good for. Furthermore, I will discuss our latest results on a new notion of curvature on graphs, based on the effective resistance. These new "resistance curvatures" are related to other well-known notions of discrete curvature (Ollivier, Forman, combinatorial curvature), we find evidence for convergence to continuous curvature in the case of Euclidean random graphs and there is a naturally associated discrete Ricci flow.

A preprint on this work is available on arXiv: https://arxiv.org/abs/2201.06385

A metapopulation model, composed of subpopulations and pairwise connections, is a particle-network framework for epidemic dynamics study. Individuals are well-mixed within each subpopulation and migrate from one subpopulation to another, obeying a given mobility rule. While different mobility rules in metapopulation models have been studied, few efforts have been made to compare the effects of simple (i.e., unbiased) random walks and more complex mobility rules. In this talk, we study susceptible-infectious-susceptible (SIS) dynamics in a metapopulation model, in which individuals obey a second-order parametric random-walk mobility rule called the node2vec. We transform the node2vec mobility rule to a first-order Markov chain whose state space is composed of the directed edges and then derive the epidemic threshold. We find that the epidemic threshold is larger for various networks when individuals avoid frequent backtracking or visiting a neighbor of the previously visited subpopulation than when individuals obey the simple random walk. The amount of change in the epidemic threshold induced by the node2vec mobility is generally not as significant as, but is sometimes comparable with, the one induced by the change in the diffusion rate for individuals.

arXiv links: https://arxiv.org/abs/2006.04904 and https://arxiv.org/abs/2106.08080

In this talk we will show the application of (multilayer) network science to a wide spectrum of problems related to the ongoing COVID-19 pandemic, ranging from the molecular to the societal scale. Specifically, we will discuss our recent results about how network analysis: i) has been successfully applied to virus-host protein-protein interactions to unravel the systemic nature of SARS-CoV-2 infection; ii) has been used to gain insights about the potential role of non-compliant behavior in spreading of COVID-19; iii) has been crucial to assess the infodemic risk related to the simultaneous circulation of reliable and unreliable information about COVID-19.

References:

Assessing the risks of "infodemics" in response to COVID-19 epidemics
R. Gallotti, F. Valle, N. Castaldo, P. Sacco, M. De Domenico, Nature Human Behavior 4, 1285-1293 (2020)

CovMulNet19, Integrating Proteins, Diseases, Drugs, and Symptoms: A Network Medicine Approach to COVID-19
N. Verstraete, G. Jurman, G. Bertagnolli, A. Ghavasieh, V. Pancaldi, M. De Domenico, Network and Systems Medicine 3, 130 (2020)

Multiscale statistical physics of the pan-viral interactome unravels the systemic nature of SARS-CoV-2 infections
A. Ghavasieh, S. Bontorin, O. Artime, N. Verstraete, M. De Domenico, Communications Physics 4, 83 (2021)

Individual risk perception and empirical social structures shape the dynamics of infectious disease outbreaks
V. D'Andrea, R. Gallotti, N. Castaldo, M. De Domenico, To appear in PLOS Computational Biology (2022)

In the first part of the seminar I will introduce shallow neural-networks from a statistical-mechanics perspective, focusing on simple cases and on a naive scenario where information to be learnt is structureless. Then, inspired by biological information processing, I will enrich this framework by accounting for structured datasets and by making the network able to perform challenging tasks like generalization or even "taking a nap”. Results presented are both analytical and numerical.

Identifying novel drug-target interactions (DTI) is a critical and rate limiting step in drug discovery. While deep learning models have been proposed to accelerate the identification process, we show that state-of-the-art models fail to generalize to novel (i.e., never-before-seen) structures. We first unveil the mechanisms responsible for this shortcoming, demonstrating how models rely on shortcuts that leverage the topology of the protein-ligand bipartite network, rather than learning the node features. Then, we introduce AI-Bind, a pipeline that combines network-based sampling strategies with unsupervised pre-training, allowing us to limit the annotation imbalance and improve binding predictions for novel proteins and ligands. We illustrate the value of AI-Bind by predicting drugs and natural compounds with binding affinity to SARS-CoV-2 viral proteins and the associated human proteins. We also validate these predictions via auto-docking simulations and comparison with recent experimental evidence. Overall, AI-Bind offers a powerful high-throughput approach to identify drug-target combinations, with the potential of becoming a powerful tool in drug discovery.

arXiv link: https://arxiv.org/abs/2112.13168

We consider spectral methods that uncover hidden structures in directed networks. We establish and exploit connections between node reordering via (a) minimizing an objective function and (b) maximizing the likelihood of a random graph model. We focus on two existing spectral approaches that build and analyse Laplacian-style matrices via the minimization of frustration and trophic incoherence. These algorithms aim to reveal directed periodic and linear hierarchies, respectively. We show that reordering nodes using the two algorithms, or mapping them onto a specified lattice, is associated with new classes of directed random graph models. Using this random graph setting, we are able to compare the two algorithms on a given network and quantify which structure is more likely to be present. We illustrate the approach on synthetic and real networks, and discuss practical implementation issues. This talk is based on a joint work with Desmond Higham and Konstantinos Zygalakis. 

Article link: https://royalsocietypublishing.org/doi/10.1098/rsos.211144

Trophic coherence, a measure of a graph’s hierarchical organisation, has been shown to be linked to a graph’s structural and dynamical aspects such as cyclicity, stability and normality. Trophic levels of vertices can reveal their functional properties, partition and rank the vertices accordingly. Trophic levels and hence trophic coherence can only be defined on graphs with basal vertices, i.e. vertices with zero in-degree. Consequently, trophic analysis of graphs had been restricted until now. In this talk I will introduce a novel  framework which can be defined on any simple graph. Within this general framework, I'll illustrate several new metrics: hierarchical levels, a generalisation of the notion of trophic levels, influence centrality, a measure of a vertex’s ability to influence dynamics, and democracy coefficient, a measure of overall feedback in the system. I will then discuss what new insights are illuminated on the topological and dynamical aspects of graphs. Finally, I will show how the hierarchical structure of a network relates to the incidence rate in a SIS epidemic model and the economic insights we can gain through it.

Article link: https://www.nature.com/articles/s41598-021-93161-4

We are confronted with signals defined on the nodes of a graph in many applications.  Think for instance of a sensor network measuring temperature; or a social network, in which each person (node) has an opinion about a specific issue.  Graph signal processing (GSP) tries to device appropriate tools to process such data by generalizing classical methods from signal processing of time-series and images -- such as smoothing, filtering and interpolation -- to signals defined on graphs.  Typically, this involves leveraging the structure of the graph as encoded in the spectral properties of the graph Laplacian.

In other applications such as traffic network analysis, however, the signals of interest are naturally defined on the edges of a graph, rather than on the nodes. After a very brief recap of the central ideas of GSP, we examine why the standard tools from GSP may not be suitable for the analysis of such edge signals.  More specifically, we discuss how the underlying notion of a 'smooth signal' inherited from (the typically considered variants of) the graph Laplacian are not suitable when dealing with edge signals that encode flows.  To overcome this limitation we devise signal processing tools based on the Hodge-Laplacian and the associated discrete Hodge Theory for simplicial (and cellular) complexes.  We discuss applications of these ideas for signal smoothing, semi-supervised and active learning for edge-flows on discrete (or discretized) spaces.

TBA

In the event of food-borne disease outbreaks, conventional epidemiological approaches to identify the causative food product are time-intensive and often inconclusive. Data-driven tools could help to reduce the number of products under suspicion by efficiently generating food-source hypotheses. We frame the problem of generating hypotheses about the food-source as one of identifying the source network from a set of food supply networks (e.g. vegetables, eggs) that most likely gave rise to the illness outbreak distribution over consumers at the terminal stage of the supply network. We introduce an information-theoretic measure that quantifies the degree to which an outbreak distribution can be explained by a supply network’s structure and allows comparison across networks. The method leverages a previously-developed food-borne contamination diffusion model and probability distribution for the source location in the supply chain, quantifying the amount of information in the probability distribution produced by a particular network-outbreak combination. We illustrate the method using supply network models from Germany and demonstrate its application potential for outbreak investigations through simulated outbreak scenarios and a retrospective analysis of a real-world outbreak.

Many real world graphs have edges correlated to the distance between them, but, in an inhomogeneous manner. While the Chung-Lu model and geometric random graph models both are elegant in their simplicity, they are insufficient to capture the complexity of these networks. For instance, the Chung-Lu model captures the inhomogeneity of the nodes but does not address the geometric nature of the nodes and simple geometric models treat names homogeneously.

In this talk, we develop a generalized geometric random graph model that preserves many graph-theoretic aspects of these models. Notably, each node is assigned a weight based on its desired expected degree; nodes are then adjacent based on a function of their weight and geometric distance. We will discuss the mathematical properties of this model. We also test the validity of this model on a graphical representation of the Drosophila Medulla connectome, a natural real-world inhomogeneous graph where spatial information is known.

This is joint work with Susama Agarwala, Johns Hopkins, Applied Physics Lab.

arXiv link: https://arxiv.org/abs/2109.00061

We propose a decentralised “local2global" approach to graph representation learning, that one can a-priori use to scale any embedding technique. Our local2global approach proceeds by first dividing the input graph into overlapping subgraphs (or “patches") and training local representations for each patch independently. In a second step, we combine the local representations into a globally consistent representation by estimating the set of rigid motions that best align the local representations using information from the patch overlaps, via group synchronization.  A key distinguishing feature of local2global relative to existing work is that patches are trained independently without the need for the often costly parameter synchronisation during distributed training. This allows local2global to scale to large-scale industrial applications, where the input graph may not even fit into memory and may be stored in a distributed manner.

arXiv link: https://arxiv.org/abs/2107.12224v1

Model reduction is one of the most used tools to characterize real-world complex systems. A large realistic model is approximated by a simpler model on a smaller state space, capturing what is considered by the user as the most important features of the larger model. In this talk we will introduce a new information-theoretic criterion, called "autoinformation", that aggregates states of a Markov chain and provide a reduced model as Markovian (small memory of the past) and as predictable (small level of noise) as possible. We will discuss the connection of autoinformation to widely accepted model reduction techniques in network science such as modularity or degree-corrected stochastic block model inference. In addition to our theoretical results, we will validate such technique with didactic and real-life examples. When applied to the ocean surface currents, our technique, which is entirely data-driven, is able to identify the main global structures of the oceanic system when focusing on the appropriate time-scale of around 6 months.
arXiv link: https://arxiv.org/abs/2005.00337

“The Royal Swedish Academy of Sciences has today decided to award the 2021 Nobel Prize in Physics for ground-breaking contributions to our understanding of complex physical systems”

Last Tuesday this announcement got many in our community very excited: never before had the Nobel prize been awarded to a topic so closely related to Network Science. We will try to understand the contributions that have led to this Nobel Prize announcement and their ties with networks science. The presentation will be held by Erik Hörmann, who has been lucky enough to have had the honour and pleasure of studying and working with one of the awardees, Professor Giorgio Parisi, before joining the Mathematical Institute.