Past Networks Seminar

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.

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.)

We consider random graph models where graphs are generated by connecting not only pairs of nodes by edges but also larger subsets of
nodes by copies of small atomic subgraphs of arbitrary topology. More specifically we consider canonical and microcanonical ensembles
corresponding to constraints placed on the counts and distributions of atomic subgraphs and derive general expressions for the entropy of such
models. We also introduce a procedure that enables the distributions of multiple atomic subgraphs to be combined resulting in more coarse
grained models. As a result 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 (Karrer & Newman PRE 2010, Bollobas et al. RSA 2011), random hypergraphs, bipartite models, stochastic block models, models of multilayer networks and their degree corrected and directed versions. We show that the entropy expressions for all these models can be derived from a single expression that is characterized by the symmetry groups of their atomic subgraphs.

Many real networks feature the property of nestedness, i.e. the neighbours of nodes with a few connections are hierarchically nested within the neighbours of nodes with more connections. Despite the abstract simplicity of this notion, different mathematical definitions of nestedness have been proposed, sometimes giving contrasting results. Moreover, there is an ongoing debate on the statistical significance of nestedness, since even random networks where the number of connections (degree) of each node is fixed to its empirical value are typically as nested as real-world ones. In this talk we show unexpected effects due to the recent finding that random networks where the degrees are enforced as hard constraints (microcanonical ensembles) are thermodynamically different from random networks where the degrees are enforced as soft constraints (canonical ensembles). We show that if the real network is perfectly nested, then the two ensembles are trivially equivalent and the observed nestedness, independently of its definition, is indeed an unavoidable consequence of the empirical degrees. On the other hand, if the real network is not perfectly nested, then the two ensembles are not equivalent and alternative definitions of nestedness can be even positively correlated in the canonical ensemble and negatively correlated in the microcanonical one. This result disentangles distinct notions of nestedness captured by different metrics and highlights the importance of making a principled choice between hard and soft constraints in null models of ecological networks.

[1] Bruno, M., Saracco, F., Garlaschelli, D., Tessone, C. J., & Caldarelli, G. (2020). Nested mess: thermodynamics disentangles conflicting notions of nestedness in ecological networks. arXiv preprint arXiv:2001.11805.
 

The notion of emergence is at the core of many of the most challenging open scientific questions, being so much a cause of wonder as a perennial source of philosophical headaches. Two classes of emergent phenomena are usually distinguished: strong emergence, which corresponds to supervenient properties with irreducible causal power; and weak emergence, which are properties generated by the lower levels in such "complicated" ways that they can only be derived by exhaustive simulation. While weak emergence is generally accepted, a large portion of the scientific community considers causal emergence to be either impossible, logically inconsistent, or scientifically irrelevant.

In this talk we present a novel, quantitative framework that assesses emergence by studying the high-order interactions of the system's dynamics. By leveraging the Integrated Information Decomposition (ΦID) framework [1], our approach distinguishes two types of emergent phenomena: downward causation, where macroscopic variables determine the future of microscopic degrees of freedom; and causal decoupling, where macroscopic variables influence other macroscopic variables without affecting their corresponding microscopic constituents. Our framework also provides practical tools that are applicable on a range of scenarios of practical interest, enabling to test -- and possibly reject -- hypotheses about emergence in a data-driven fashion. We illustrate our findings by discussing minimal examples of emergent behaviour, and present a few case studies of systems with emergent dynamics, including Conway’s Game of Life, neural population coding, and flocking models.
[1] Mediano, Pedro AM, Fernando Rosas, Robin L. Carhart-Harris, Anil K. Seth, and Adam B. Barrett. "Beyond integrated information: A taxonomy of information dynamics phenomena." arXiv preprint arXiv:1909.02297 (2019).
 

Spatial networks are often the most natural way to represent spatial information of different kinds. One of the outstanding problems in current spatial network research is to effectively quantify the heterogeneity of the discrete-valued spatial distributions underlying a spatial graph. In this talk we will presentsome recent alternative approaches to estimate heterogeneity in spatial networks based on simple dynamical processes running on them.

Multilayer networks are a way to represent dependent connectivity patterns — e.g., time-dependence, multiple types of interactions, or both — that arise in many applications and which are difficult to incorporate into standard network representations. In the study of multilayer networks, it is important to investigate mesoscale (i.e., intermediate-scale) structures, such as communities, to discover features that lie between the microscale and the macroscale. We introduce a framework for the construction of generative models for mesoscale structure in multilayer networks.  We model dependency at the level of partitions rather than with respect to edges, and treat the process of generating a multilayer partition separately from the process of generating edges for a given multilayer partition. Our framework can admit many features of empirical multilayer networks and explicitly incorporates a user-specified interlayer dependency structure. We discuss the parameters and some properties of our framework, and illustrate an example of its use with benchmark models for multilayer community-detection tools. 

Real networks are highly clustered (large number of short cycles) in contrast with their random counterparts. The Erdős–Rényi model and the Configuration model will generate networks with a tree like structure, a feature rarely observed in real networks. This means that traditional random networks are a poor choice as null models for real networks. Can we do better than that? Maximum entropy random graph ensembles are the natural choice to generate such networks. By introducing a bias with respect to the number of short cycles in a degree constrained graph, we aim to get a random graph model with a tuneable number of short cycles [1,2]. Nevertheless, the story is not so simple. In the same way random unclustered graphs present undesired topology, highly clustered ones will do as well if one is not careful with the scaling of the control parameters relative to the system size. Additionally the techniques to generate and sample numerically from general biased degree constrained graph ensembles will also be discussed. The topological transition has an important impact on the computational cost to sample graphs from these ensembles. To take it one step further, a general approach using the eigenvalues of the adjacency matrix rather than just the number of short cycles will also be presented, [2].

[1] López, Fabián Aguirre, et al. "Exactly solvable random graph ensemble with extensively many short cycles." Journal of Physics A: Mathematical and Theoretical 51.8 (2018): 085101.
[2] López, Fabián Aguirre, and Anthony CC Coolen. "Imaginary replica analysis of loopy regular random graphs." Journal of Physics A: Mathematical and Theoretical 53.6 (2020): 065002.

Random graphs were introduced as a convenient example for demonstrating the impossibility of ‘complete disorder’ by Erdos, who also thought that these objects will never become useful in the applied areas outside of pure mathematics. In this talk, I will view random graphs as objects in the field of applied mathematics and discus how the application-driven objectives have set new directions for studying random graphs. I will focus on characterising the sizes of connected components in graphs with a given degree distribution, on the percolation-like processes on such structures, and on generalisations to the coloured graphs. These theoretical questions have interesting implications for studying resilience of networks with nontrivial structures, and for materials science where they explain kinetics-driven phase transitions. Even more surprisingly, the results reveal intricate connections between random graphs and non-linear partial differential equations indicating new possibilities for their analysis.

Can spatial fungal networks be informative for both ecology and network science?

Filamentous organisms grow as adaptive biological spatial networks. These networks are in a continuous balance of two main forces: exploration of the habitat to acquire scarce resources, and the transport of those resources within the developing network. In addition, the construction of the network has to be kept a low cost while taking into account the risk of damage by predation. Such network optimization is not unique to biological systems, but is relevant to transport networks across many domains. Thus, this collaborative project between FU-Berlin and University of Oxford represents the beginning of a research program that aims at: First, setting up protocols for the use of network analysis to characterize spatial networks formed by both macroscopic and microscopic filamentous organisms (e.g. Fungi), and determining the fitness and ecological consequences of different structure of the networks. Second, extracting biologically-inspired algorithms that lead to optimized network formation in fungi and discuss their utility in other network domains. This information is critical to demonstrate that we have a viable and scalable pipeline for the measurement of such properties as well provide preliminary evidence of the usefulness of studying network properties of fungi.

It is known that many real-world networks exhibit geometric properties.  Brain networks, social networks, and wireless communication networks are a few examples.  Storage and transmission of the information contained in the topologies and structures of these networks are important tasks, which, given their scale, is often nontrivial.  Although some (but not much) work has been done to characterize and develop compression limits and algorithms for nonspatial graphs, little is known for the spatial case.  In this talk, we will discuss an information theoretic formalism for studying compression limits for a fairly broad class of random geometric graphs.  We will then discuss entropy bounds for these graphs and, time permitting, local (pairwise) connection rules that yield maximum entropy properties in the induced graph distribution.

Cities are now central to addressing global changes, ranging from climate change to economic resilience. There is a growing concern of how to measure and quantify urban phenomena, and one of the biggest challenges in quantifying different aspects of cities and creating meaningful indicators lie in our ability to extract relevant features that characterize the topological and spatial patterns of urban form. Many different models that can reproduce large-scale statistical properties observed in systems of streets have been proposed, from spatial random graphs to economical models of network growth. However, existing models fail to capture the diversity observed in street networks around the world. The increased availability of street network datasets and advancements in deep learning models present a new opportunity to create more accurate and flexible models of urban street networks, as well as capture important characteristics that could be used in downstream tasks.  We propose a simple approach called Convolutional-PCA (ConvPCA) for both creating low-dimensional representations of street networks that can be used for street network classification and other downstream tasks, as well as a generating new street networks that preserve visual and statistical similarity to observed street networks.

Link to the preprint

Political polarization generates strong effects on society, driving controversial debates and influencing the institutions. Territorial disputes are one of the most important polarized scenarios and have been consistently related to the use of language. In this work, we analyzed the opinion and language distributions of a particular territorial dispute around the independence of the Spanish region of Catalonia through Twitter data. We infer a continuous opinion distribution by applying a model based on retweet interactions, previously selecting a seed of elite users with fixed and antagonist opinions. The resulting distribution presents a mainly bimodal behavior with an intermediate third pole that appears spontaneously showing a less polarized society with the presence of not only antagonist opinions. We find that the more active, engaged and influential users hold more extreme positions. Also we prove that there is a clear relationship between political positions and the use of language, showing that against independence users speak mainly Spanish while pro-independence users speak Catalan and Spanish almost indistinctly. However, the third pole, closer in political opinion to the pro-independence pole, behaves similarly to the against-independence one concerning the use of language.

Ref: https://www.nature.com/articles/s41598-019-53404-x

We aim to generate gene coexpression networks from gene expression data. In our networks, nodes represent genes and edges depict high positive correlation in their expression across different samples. Methods based on Pearson correlation are the most commonly used to generate gene coexpression networks. We propose the use of distance correlation as an effective alternative to Pearson correlation when constructing gene expression networks. Our methodology pipeline includes a thresholding step which allows us to discriminate which pairs of genes are coexpressed. We select the value of the threshold parameter by studying the stability of the generated network, rather than relying on exogenous biological information known a priori.

Persistent homology has been applied to graph classification problems as a way of generating vectorizable features of graphs that can be fed into machine learning algorithms, such as neural networks. A key ingredient of this approach is a filter constructor that assigns vector features to nodes to generate a filtration. In the case where the filter constructor is smoothly tuned by a set of real parameters, we can train a neural network graph classifier on data to learn an optimal set of parameters via the backpropagation of gradients that factor through persistence diagrams [Leygonie et al., arXiv:1910.00960]. We propose a flexible, spectral-based filter constructor that parses standalone graphs, generalizing methods proposed in [Carrière et al., arXiv: 1904.09378]. Our method has an advantage over optimizable filter constructors based on iterative message passing schemes (`graph neural networks’) [Hofer et al., arXiv: 1905.10996] which rely on heuristic user inputs of vertex features to initialise the scheme for datasets where vertex features are absent. We apply our methods to several benchmark datasets and demonstrate results comparable to current state-of-the-art graph classification methods.

Identifying systemically important countries is crucial for global financial stability. In this work we use (multilayer) network methods to identify systemically important countries. We study the financial system as a multilayer network, where each layer represent a different type of financial investment between countries. To rank countries by their systemic importance, we implement MultiRank, as well a simplistic model of financial contagion. In this first model, we consider that each country has a capital buffer, given by the capital to assets ratio. After the default of an initial country, we model financial contagion with a simple rule: a solvent country defaults when the amount of assets lost, due to the default of other countries, is larger than its capital. Our results show that when we consider that there are various types of assets the ranking of systemically important countries changes. We make all our methods available by introducing a python library. Finally, we propose a more realistic model of financial contagion that merges multilayer network theory and the contingent claims sectoral balance sheet literature. The aim of this framework is to model the banking, private, and sovereign sector of each country and thus study financial contagion within the country and between countries. 

Spreading processes on geometric networks are often influenced by a network’s underlying spatial structure, and it is insightful to study the extent to which a spreading process follows that structure. In particular, considering a threshold contagion on a network whose nodes are embedded in a manifold and which has both 'geometric edges' that respect the geometry of the underlying manifold, as well as 'non-geometric edges' that are not constrained by the geometry of the underlying manifold, one can ask whether the contagion propagates as a wave front along the underlying geometry, or jumps via long non-geometric edges to remote areas of the network. 
Taylor et al. developed a methodology aimed at determining the spreading behaviour of threshold contagion models on such 'noisy geometric networks' [1]. This methodology is inspired by nonlinear dimensionality reduction and is centred around a so-called 'contagion map' from the network’s nodes to a point cloud in high dimensional space. The structure of this point cloud reflects the spreading behaviour of the contagion. We apply this methodology to a family of noisy-geometric networks that can be construed as being embedded in a torus, and are able to identify a region in the parameter space where the contagion propagates predominantly via wave front propagation. This consolidates contagion map as both a tool for investigating spreading behaviour on spatial network, as well as a manifold learning technique. 
[1] D. Taylor, F. Klimm, H. A. Harrington, M. Kramar, K. Mischaikow, M. A. Porter, and P. J. Mucha. Topological data analysis of contagion maps for examining spreading processes on networks. Nature Communications, 6(7723) (2015)

Cities and their inter-connected transport networks form part of the fundamental infrastructure developed by human societies. Their organisation reflects a complex interplay between many natural and social factors, including inter alia natural resources, landscape, and climate on the one hand, combined with business, commerce, politics, diplomacy and culture on the other. Nevertheless, despite this complexity, there has been some success in capturing key aspects of city growth and network formation in relatively simple models that include non-linear positive feedback loops. However, these models are typically embedded in an idealised, homogeneous space, leading to regularly-spaced, lattice-like distributions arising from Turing-type pattern formation. Here we argue that the geographical landscape plays a much more dominant, but neglected role in pattern formation. To examine this hypothesis, we evaluate the weighted distance between locations based on a least cost path across the natural terrain, determined from high-resolution digital topographic databases for Italy. These weights are included in a co-evolving, dynamical model of both population aggregation in cities, and movement via an evolving transport network. We compare the results from the stationary state of the system with current population distributions from census data, and show a reasonable fit, both qualitatively and quantitatively, compared with models in homogeneous space. Thus we infer that that addition of weighted topography from the natural landscape to these models is both necessary and almost sufficient to reproduce the majority of the real-world spatial pattern of city sizes and locations in this example.

Many complex systems can be represented as networks. However, it is often not possible or even desirable to observe the entire network structure. For example, in social networks, it is often difficult to obtain samples of large networks due to commercial sensitivity or privacy concerns relating to the data. However, it may be possible to provide a coarse grained picture of the graph given knowledge of the distribution of different demographics (e.g age, income, location, etc…) in a population and their propensities for forming ties between each other.

I will explore the degree to which it is possible to influence Ising systems, which are commonly used to model social influence, on unobserved graphs. Using both synthetic networks (stochastic blockmodels) and case studies of real world social networks, I will demonstrate how simple models which rely only on a coarse grained description of the system or knowledge of only the underlying external fields can perform comparably to more expensive optimization algorithms.

In many applications we are confronted with the following scenario: we observe snapshots of data describing the state of a system at particular times, and based on these observations we want to infer the (dynamical) interactions between the entities we observe. However, often the number of samples we can obtain from such a process are far too few to identify the network exactly. Can we still reliable infer some aspects of the underlying system?
Motivated by this question we consider the following alternative system identification problem: instead of trying to infer the exact network, we aim to recover a (low-dimensional) statistical model of the network based on the observed signals on the nodes.  More concretely, here we focus on observations that consist of snapshots of a diffusive process that evolves over the unknown network. We model the (unobserved) network as generated from an independent draw from a latent stochastic block model (SBM), and our goal is to infer both the partition of the nodes into blocks, as well as the parameters of this SBM. We present simple spectral algorithms that provably solve the partition and parameter inference problems with high-accuracy.

Many soft materials, such as elastomers and hydrogels, are made of long chain molecules crosslinked to form a three-dimensional network. Their mechanical properties depend on network parameters such as chain density, chain length distribution and the functionality of the crosslinks. Understanding the relationships between the topology of polymer networks and their mechanical properties has been a long-standing challenge in polymer physics.

In this work, we focus on so-called “near-ideal” networks, which are produced by the cross-coupling of star-like macromolecules with well-defined chain length. We developed a computational approach based on random discrete networks, according to which the polymer network is represented by an assembly of non-linear springs connected at junction points representing crosslinks. The positions of the crosslink points are determined from the conditions of mechanical equilibrium. Scaling relations for the elastic modulus and maximum extensibility of the network were obtained. Our scaling relations contradict some predictions of classical estimates of rubber elasticity and have implications for the interpretation of experimental data for near-ideal polymer networks.

Reference: G. Alame, L. Brassart. Relative contributions of chain density and topology to the elasticity of two-dimensional polymer networks. Soft Matter 15, 5703 (2019).