Past Networks Seminar

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.

Successful navigation of the Covid-19 pandemic is predicated on public cooperation with safety measures and appropriate perception of risk, in which emotion and attention play important roles. Signatures of public emotion and attention are present in social media data, thus natural language analysis of this text enables near-to-real-time monitoring of indicators of public risk perception. We compare key epidemiological indicators of the progression of the pandemic with indicators of the public perception of the pandemic constructed from ∼20 million unique Covid-19-related tweets from 12 countries posted between 10th March and 14th June 2020. We find evidence of psychophysical numbing: Twitter users increasingly fixate on mortality, but in a decreasingly emotional and increasingly analytic tone. Semantic network analysis based on word co-occurrences reveals changes in the emotional framing of Covid-19 casualties that are consistent with this hypothesis. We also find that the average attention afforded to national Covid-19 mortality rates is modelled accurately with the Weber–Fechner and power law functions of sensory perception. Our parameter estimates for these models are consistent with estimates from psychological experiments, and indicate that users in this dataset exhibit differential sensitivity by country to the national Covid-19 death rates. Our work illustrates the potential utility of social media for monitoring public risk perception and guiding public communication during crisis scenarios.

The science of cities seeks to understand and explain regularities observed in the world's major urban systems. Modelling the population evolution of cities is at the core of this science and of all urban studies. Quantitatively, the most fundamental problem is to understand the hierarchical organization of cities and the statistical occurrence of megacities, first thought to be described by a universal law due to Zipf, but whose validity has been challenged by recent empirical studies. A theoretical model must also be able to explain the relatively frequent rises and falls of cities and civilizations, and despite many attempts these fundamental questions have not been satisfactorily answered yet. Here we fill this gap by introducing a new kind of stochastic equation for modelling population growth in cities, which we construct from an empirical analysis of recent datasets (for Canada, France, UK and USA) that reveals how rare but large interurban migratory shocks dominate city growth. This equation predicts a complex shape for the city distribution and shows that Zipf's law does not hold in general due to finite-time effects, implying a more complex organization of cities. It also predicts the existence of multiple temporal variations in the city hierarchy, in agreement with observations. Our result underlines the importance of rare events in the evolution of complex systems and at a more practical level in urban planning.

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

Many complex networks depend upon biological entities for their preservation. Such entities, from human cognition to evolution, must first encode and then replicate those networks under marked resource constraints. Networks that survive are those that are amenable to constrained encoding, or, in other words, are compressible. But how compressible is a network? And what features make one network more compressible than another? Here we answer these questions by modeling networks as information sources before compressing them using rate-distortion theory. Each network yields a unique rate-distortion curve, which specifies the minimal amount of information that remains at a given scale of description. A natural definition then emerges for the compressibility of a network: the amount of information that can be removed via compression, averaged across all scales. Analyzing an array of real and model networks, we demonstrate that compressibility increases with two common network properties: transitivity (or clustering) and degree heterogeneity. These results indicate that hierarchical organization -- which is characterized by modular structure and heavy-tailed degrees -- facilitates compression in complex networks. Generally, our framework sheds light on the interplay between a network's structure and its capacity to be compressed, enabling investigations into the role of compression in shaping real-world networks.

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

Empirical networks often exhibit different meso-scale structures, such as community and core-periphery structure. Core-periphery typically consists of a well-connected core, and a periphery that is well-connected to the core but sparsely connected internally. Most core-periphery studies focus on undirected networks. In this talk we discuss  a generalisation of core-periphery to directed networks which  yields a family of core-periphery blockmodel formulations in which, contrary to many existing approaches, core and periphery sets are edge-direction dependent. Then we shall  focus on a particular structure consisting of two core sets and two periphery sets, and we introduce  two measures to assess the statistical significance and quality of this  structure in empirical data, where one often has no ground truth. The idea will be illustrated on three empirical networks --  faculty hiring, a world trade data-set, and political blogs.

This is based on joint work with Andrew Elliott, Angus Chiu, Marya Bazzi and Mihai Cucuringu, available at https://royalsocietypublishing.org/doi/pdf/10.1098/rspa.2019.0783

Networks are an imperfect representation of a dataset, yet often there is little consideration for how these imperfections may affect network evolution and structure.

In this talk, I want to discuss a simple set of generative network models in which the mechanism of network growth is decomposed into two layers. The first layer represents the “observed” network, corresponding to our conventional understanding of a network. Here I want to consider the scenario in which the network you observe is not self-contained, but is driven by a second hidden network, comprised of the same nodes but different edge structure. I will show how a range of different network growth models can be constructed such that the observed and hidden networks can be causally decoupled, coupled only in one direction, or coupled in both directions.

One consequence of such models is the emergence of abrupt transitions in observed network topology – one example results in scale-free degree distributions which are robust up to an arbitrarily long threshold time, but which naturally break down as the network grows larger. I will argue that such examples illustrate why we should be wary of an overreliance on static networks (measured at only one point in time), and will discuss other possible implications for prediction on networks.

Multibody interactions can reveal higher-order dynamical effects that are not captured by traditional two-body network models. We derive and analyze models for consensus dynamics on hypergraphs, where nodes interact in groups rather than in pairs. Our work reveals that multibody dynamical effects that go beyond rescaled pairwise interactions can appear only if the interaction function is nonlinear, regardless of the underlying multibody structure. As a practical application, we introduce a specific nonlinear function to model three-body consensus, which incorporates reinforcing group effects such as peer pressure. Unlike consensus processes on networks, we find that the resulting dynamics can cause shifts away from the average system state. The nature of these shifts depends on a complex interplay between the distribution of the initial states, the underlying structure, and the form of the interaction function. By considering modular hypergraphs, we discover state-dependent, asymmetric dynamics between polarized clusters where multibody interactions make one cluster dominate the other.

Building on these results, we generalise the model allowing for interactions within hyper edges of any cardinality and explore in detail the role of involvement and stubbornness on polarisation.

Randomized experiments, or "A/B" tests, remain the gold standard for evaluating the causal effect of a policy intervention or product change. However, experimental settings such as social networks, where users are interacting and influencing one another, violate conventional assumptions of no interference needed for credible causal inference. Existing solutions include accounting for the fraction or count of treated neighbors in a user's network, among other strategies. Yet, there are often a high number of researcher degrees of freedom in specifying network interference conditions and most current methods do not account for the local network structure beyond simply counting the number of neighbors. Capturing local network structures is important because it can account for theories, such as structural diversity and echo chambers. Our study provides an approach that accounts for both the local structure in a user's social network via motifs as well as the assignment conditions of neighbors. We propose a two-part approach. We first introduce and employ "causal network motifs," i.e. network motifs that characterize the assignment conditions in local ego networks; and then we propose a tree-based algorithm for identifying different network interference conditions and estimating their average potential outcomes. We test our method on a real-world experiment on a large-scale network and a synthetic network setting, which highlight how accounting for local structures can better account for different interference patterns in networks.

(joint work with T. Kania, Academy of Sciences of the Czech Republic, Prague)
In this talk we discuss our recent result on the inverse eigenvalue problem for symmetric doubly stochastic matrices. 
Namely, we provide a new sufficient condition for a list of real numbers to be the spectrum of a symmetric doubly stochastic matrix. 
In our construction of such matrices, we employ the eigenvectors of the transition probability matrix of a simple symmetric random walk on the circle. 
We also demonstrate a simple algorithm for generating random doubly stochastic matrices based on our construction. Examples will be provided.

Here we propose a new method to compare the modular structure of a pair of node-aligned networks. The majority of current methods, such as normalized mutual information, compare two node partitions derived from a community detection algorithm yet ignore the respective underlying network topologies. Addressing this gap, our method deploys a community detection quality function to assess the fit of each node partition with respect to the other network's connectivity structure. Specifically, for two networks A and B, we project the node partition of B onto the connectivity structure of A. By evaluating the fit of B's partition relative to A's own partition on network A (using a standard quality function), we quantify how well network A describes the modular structure of B. Repeating this in the other direction, we obtain a two-dimensional distance measure, the bi-directional (BiDir) distance. The advantages of our methodology are three-fold. First, it is adaptable to a wide class of community detection algorithms that seek to optimize an objective function. Second, it takes into account the network structure, specifically the strength of the connections within and between communities, and can thus capture differences between networks with similar partitions but where one of them might have a more defined or robust community structure. Third, it can also identify cases in which dissimilar optimal partitions hide the fact that the underlying community structure of both networks is relatively similar. We illustrate our method for a variety of community detection algorithms, including multi-resolution approaches, and a range of both simulated and real world networks.

We develop random graph models where graphs are generated by connecting not only pairs of vertices by edges but also larger subsets of vertices by copies of small atomic subgraphs of arbitrary topology. This allows the for the generation of graphs with extensive numbers of triangles and other network motifs commonly observed in many real world networks. More specifically we focus on maximum entropy ensembles under constraints placed on the counts and distributions of atomic subgraphs and derive general expressions for the entropy of such models. We also present a procedure for combining distributions of multiple atomic subgraphs that enables the construction of models with fewer parameters. Expanding the model to include atoms with edge and vertex labels we obtain a general class of models that can be parametrized in terms of basic building blocks and their distributions that includes many widely used models as special cases. These models include random graphs with arbitrary distributions of subgraphs, random hypergraphs, bipartite models, stochastic block models, models of multilayer networks and their degree corrected and directed versions. We show that the entropy for all these models can be derived from a single expression that is characterized by the symmetry groups of atomic subgraphs.

Modular and hierarchical structures are pervasive in real-world complex systems. A great deal of effort has gone into trying to detect and study these structures. Important theoretical advances in the detection of modular, or "community", structures have included identifying fundamental limits of detectability by formally defining community structure using probabilistic generative models. Detecting hierarchical community structure introduces additional challenges alongside those inherited from community detection. Here we present a theoretical study on hierarchical community structure in networks, which has thus far not received the same rigorous attention. We address the following questions: 1) How should we define a valid hierarchy of communities? 2) How should we determine if a hierarchical structure exists in a network? and 3) how can we detect hierarchical structure efficiently? We approach these questions by introducing a definition of hierarchy based on the concept of stochastic externally equitable partitions and their relation to probabilistic models, such as the popular stochastic block model. We enumerate the challenges involved in detecting hierarchies and, by studying the spectral properties of hierarchical structure, present an efficient and principled method for detecting them.

https://arxiv.org/abs/2009.07196 (15 sept.)

We develop a theory to measure the variance and covariance of probability distributions defined on the nodes of a graph, which takes into account the distance between nodes. Our approach generalizes the usual (co)variance to the setting of weighted graphs and retains many of its intuitive and desired properties. As a particular application, we define the maximum-variance problem on graphs with respect to the effective resistance distance, and characterize the solutions to this problem both numerically and theoretically. We show how the maximum-variance distribution can be interpreted as a core-periphery measure, illustrated by the fact that these distributions are supported on the leaf nodes of tree graphs, low-degree nodes in a configuration-like graph and boundary nodes in random geometric graphs. Our theoretical results are supported by a number of experiments on a network of mathematical concepts, where we use the variance and covariance as analytical tools to study the (co-)occurrence of concepts in scientific papers with respect to the (network) relations between these concepts. Finally, I will draw connections to related notion of assortativity on networks, a network analogue of correlation used to describe how the presence and absence of edges covaries with the properties of nodes.

https://arxiv.org/abs/2008.09155

Systems with lattice geometry can be renormalized exploiting their embedding in metric space, which naturally defines the coarse-grained nodes. By contrast, complex networks defy the usual techniques because of their small-world character and lack of explicit metric embedding. Current network renormalization approaches require strong assumptions (e.g. community structure, hyperbolicity, scale-free topology), thus remaining incompatible with generic graphs and ordinary lattices. Here we introduce a graph renormalization scheme valid for any hierarchy of coarse-grainings, thereby allowing for the definition of block-nodes across multiple scales. This approach reveals a necessary and specific dependence of network topology on an additive hidden variable attached to nodes, plus optional dyadic factors. Renormalizable networks turn out to be consistent with a unique specification of the fitness model, while they are incompatible with preferential attachment, the configuration model or the stochastic blockmodel. These results highlight a deep conceptual distinction between scale-free and scale-invariant networks, and provide a geometry-free route to renormalization. If the hidden variables are annealed, the model spontaneously leads to realistic scale-free networks with cut-off. If they are quenched, the model can be used to renormalize real-world networks with node attributes and distance-dependence or communities. As an example we derive an accurate multiscale model of the International Trade Network applicable across arbitrary geographic resolutions.

https://arxiv.org/abs/2009.11024 (23 sept.)