Past Networks Seminar

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.

The SI model is the most basic of all compartmental models used to describe the spreading of information through a population. In this talk we will present a mathematical formalism to solve the SI model on generic networks. Our methods rely on a tensor product formulation of the dynamical spreading process, inspired by many-body quantum systems. Here we will focus on time-dependent expectation values for the state of individual nodes, which can be obtained from contributions of subgraphs of the network. We show how to compute these contributions systematically and derive a set of symmetry relations among subgraphs of differing topologies. We conclude by comparing our results for small sample networks to Monte-Carlo simulations and mean-field approximations.

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

We present a probabilistic generative model and efficient algorithm to model reciprocity in directed networks. Unlike other methods that address this problem such as exponential random graphs, it assigns latent variables as community memberships to nodes and a reciprocity parameter to the whole network rather than fitting order statistics. It formalizes the assumption that a directed interaction is more likely to occur if an individual has already observed an interaction towards her. It provides a natural framework for relaxing the common assumption in network generative models of conditional independence between edges, and it can be used to perform inference tasks such as predicting the existence of an edge given the observation of an edge in the reverse direction. Inference is performed using an efficient expectation-maximization algorithm that exploits the sparsity of the network, leading to an efficient and scalable implementation. We illustrate these findings by analyzing synthetic and real data, including social networks, academic citations and the Erasmus student exchange program. Our method outperforms others in both predicting edges and generating networks that reflect the reciprocity values observed in real data, while at the same time inferring an underlying community structure. We provide an open-source implementation of the code online.

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

We consider the problem of clustering in two important families of networks: signed and directed, both relatively less well explored compared to their unsigned and undirected counterparts. Both problems share an important common feature: they can be solved by exploiting the spectrum of certain graph Laplacian matrices or derivations thereof. In signed networks, the edge weights between the nodes may take either positive or negative values, encoding a measure of similarity or dissimilarity. We consider a generalized eigenvalue problem involving graph Laplacians, with performance guarantees under the setting of a signed stochastic block model. The second problem concerns directed graphs. Imagine a (social) network in which you spot two subsets of accounts, X and Y, for which the overwhelming majority of messages (or friend requests, endorsements, etc) flow from X to Y, and very few flow from Y to X; would you get suspicious? To this end, we also discuss a spectral clustering algorithm for directed graphs based on a complex-valued representation of the adjacency matrix, which is able to capture the underlying cluster structures, for which the information encoded in the direction of the edges is crucial. We evaluate the proposed algorithm in terms of a cut flow imbalance-based objective function, which, for a pair of given clusters, it captures the propensity of the edges to flow in a given direction. Experiments on a directed stochastic block model and real-world networks showcase the robustness and accuracy of the method, when compared to other state-of-the-art methods. Time permitting, we briefly discuss potential extensions to the sparse setting and regularization, applications to lead-lag detection in time series and ranking from pairwise comparisons.

Online social networks such asTwitter, Facebook, Instagram and TikTokserve as mediafor the spread of information between their users.We areinterested in developing models forthis information diffusion to gain a greater understanding of its drivers. Some models forthe spread ofonlinebehaviour and informationassume that the information behaves similarly to a virus, where infection is equally likely after each exposure, these dynamics are known as a simple contagion. In a simple contagion, the exposures are independent of each other.However,online adoption of some behaviour and content has been empirically observed to be more likely after multiple exposures from their network neighbours, the exposures are not independent of each other, we refer to this as a complex contagion.Analytically tractable descriptions of complex contagions havebeendeveloped for continuous-time dynamics. These extend mean-field and pair approximation methods to account for clustering in the network topologies; however, no such analogous treatments for discrete-time cascade processes exist using branching processes. We describe a novel definition of complex contagion adoption dynamics and show how to construct multi-type branching processeswhichaccount for clustering on networks. We achieve this by tracking the evolution of a cascade via different classes of clique motifs whichaccount for the different numbers of active, inactive and removed nodes. This description allows for extensive MonteCarlo simulations (which are faster than network-based simulations), accurate analytical calculation of cascade sizes, determination of critical behaviour and other quantities of interest

Many systems exhibit complex temporal dynamics due to the presence of different processes taking place simultaneously. Temporal networks provide a framework to describe the time-resolve interactions between components of a system. An important task when investigating such systems is to extract a simplified view of the temporal network, which can be done via dynamic community detection or clustering. Several works have generalized existing community detection methods for static networks to temporal networks, but they usually rely on temporal aggregation over time windows, the assumption of an underlying stationary process, or sequences of different stationary epochs. Here, we derive a method based on a dynamical process evolving on the temporal network and restricted by its activation pattern that allows to consider the full temporal information of the system. Our method allows dynamics that do not necessarily reach a steady state, or follow a sequence of stationary states. Our framework encompasses several well-known heuristics as special cases. We show that our method provides a natural way to disentangle the different natural dynamical scales present in a system. We demonstrate our method abilities on synthetic and real-world examples.

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

Networks are a widely-used tool to investigate the large-scale connectivity structure in complex systems and graphons have been proposed as an infinite size limit of dense networks. The detection of communities or other meso-scale structures is a prominent topic in network science as it allows the identification of functional building blocks in complex systems. When such building blocks may be present in graphons is an open question. In this paper, we define a graphon-modularity and demonstrate that it can be maximised to detect communities in graphons. We then investigate specific synthetic graphons and show that they may show a wide range of different community structures. We also reformulate the graphon-modularity maximisation as a continuous optimisation problem and so prove the optimal community structure or lack thereof for some graphons, something that is usually not possible for networks. Furthermore, we demonstrate that estimating a graphon from network data as an intermediate step can improve the detection of communities, in comparison with exclusively maximising the modularity of the network. While the choice of graphon-estimator may strongly influence the accord between the community structure of a network and its estimated graphon, we find that there is a substantial overlap if an appropriate estimator is used. Our study demonstrates that community detection for graphons is possible and may serve as a privacy-preserving way to cluster network data.

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

The problem of identifying geometric structure in heterogeneous, high-dimensional data is a cornerstone of representation learning. In this talk, we study the problem of data geometry from the perspective of Discrete Geometry. We focus specifically on the analysis of relational data, i.e., data that is given as a graph or can be represented as such.

We start by reviewing discrete notions of curvature, where we focus especially on discrete Ricci curvature. Then we discuss the problem of embeddability: For downstream machine learning and data science applications, it is often beneficial to represent data in a continuous space, i.e., Euclidean, Hyperbolic or Spherical space. How can we decide on a suitable representation space? While there exists a large body of literature on the embeddability of canonical graphs, such as lattices or trees, the heterogeneity of real-world data limits the applicability of these classical methods. We discuss a combinatorial approach for evaluating embeddability, where we analyze nearest-neighbor structures and local neighborhood growth rates to identify the geometric priors of suitable embedding spaces. For canonical graphs, the algorithm’s prediction provably matches classical results. As for large, heterogeneous graphs, we introduce an efficiently computable statistic that approximates the algorithm’s decision rule. We validate our method over a range of benchmark data sets and compare with recently published optimization-based embeddability methods. 

The complementarity and substitutability between products are essential concepts in retail and marketing. Qualitatively, two products are said to be substitutable if a customer can replace one product by the other, while they are complementary if they tend to be bought together. In this article, we take a network perspective to help automatically identify complements and substitutes from sales transaction data. Starting from a bipartite product-purchase network representation, with both transaction nodes and product nodes, we develop appropriate null models to infer significant relations, either complements or substitutes, between products, and design measures based on random walks to quantify their importance. The resulting unipartite networks between products are then analysed with community detection methods, in order to find groups of similar products for the different types of relationships. The results are validated by combining observations from a real-world basket dataset with the existing product hierarchy, as well as a large-scale flavour compound and recipe dataset.

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

Homophily can put minority groups at a disadvantage by restricting their ability to establish connections with majority groups or to access novel information. In this talk, I show how this phenomenon is manifested in a variety of online and face-to-face social networks and what societal consequences it has on the visibility and ranking of minorities. I propose a network model with tunable homophily and group sizes and demonstrate how the ranking of nodes is affected by homophilic
behavior. I will discuss the implications of this research on algorithms and perception biases.

We consider a nonlinear flow on simplicial complexes related to the simplicial Laplacian, and show that it is a generalization of various consensus and synchronization models commonly studied on networks. In particular, our model allows us to formulate flows on simplices of any dimension, so that it includes edge flows, triangle flows, etc. We show that the system can be represented as the gradient flow of an energy functional, and use this to deduce the stability of various steady states of the model. Finally, we demonstrate that our model contains higher-dimensional analogues of structures seen in related network models.

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

How can a random walker on a network be helpful for patients suffering from amyotrophic lateral sclerosis (ALS)? Clinical trials in ALS continue to rely on survival or clinical functional scales as endpoints, since anatomical patterns of disease spread in ALS are poorly characterized in vivo. In this study, we generated individual brain networks of patients and controls based on cerebral magnetic resonance imaging (MRI) data. Then, we applied a computational model with a random walker to the brain MRI scan of patients to simulate this progressive network degeneration. We observe that computer‐simulated aggregation levels of the random walker mimic true disease patterns in ALS patients. Our results demonstrate the utility of computational network models in ALS to predict disease progression and underscore their potential as a prognostic biomarker.

After presenting this study on characterizing the structural changes in neurodegenerative diseases with network science, I will give an outlook on my new work on characterizing the dynamic changes in brain networks for Parkinson’s disease and counteracting these with (simulated) deep brain stimulation using the neuroinformatics platform The Virtual Brain (www.thevirtualbrain.org) .

Article link: https://onlinelibrary.wiley.com/doi/full/10.1002/ana.25706

The study of motifs in networks can help researchers uncover links between structure and function of networks in biology, the sociology, economics, and many other areas. Empirical studies of networks have identified feedback loops, feedforward loops, and several other small structures as "motifs" that occur frequently in real-world networks and may contribute by various mechanisms to important functions these systems. However, the mechanisms are unknown for many of these motifs. We propose to distinguish between "structure motifs" (i.e., graphlets) in networks and "process motifs" (which we define as structured sets of walks) on networks and consider process motifs as building blocks of processes on networks. Using the covariances and correlations in a multivariate Ornstein--Uhlenbeck process on a network as examples, we demonstrate that the distinction between structure motifs and process motifs makes it possible to gain quantitative insights into mechanisms that contribute to important functions of dynamical systems on networks.