Past Networks Seminar

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

In an increasingly urbanized world, where cities are changing continuously, it is essential for policy makers to have access to regularly updated decision-making tools for an effective management of urban areas. An example of these tools is the delineation of cities into functional areas which provides knowledge on high spatial interaction zones and their socioeconomic composition. In this paper, we presented a method for the structural analysis of a city, specifically for the determination of its functional areas, based on communities detection in graphs. The nodes of the graph correspond to geographical units resulting from a cartographic division of the city according to the road network. The edges are weighted using a Gaussian distance-decay function and the amount of spatial interactions between nodes. Our approach optimize the modularity to ensure that the functional areas detected have strong interactions within their borders but lower interactions outside. Moreover, it leverages on POIs' entropy to maintain a good socioeconomic heterogeneity in the detected areas. We conducted experiments using taxi trips and POIs datasets from the city of Porto, as a study case. Trough those experiments, we demonstrate the ability of our method to portray functional areas while including spatial and socioeconomic dynamics.
 

The analysis and characterization of human mobility using population-level mobility models is important for numerous applications, ranging from the estimation of commuter flows to modeling trade flows. However, almost all of these applications have focused on large spatial scales, typically from intra-city level to inter-country level. In this paper, we investigate population-level human mobility models on a much smaller spatial scale by using them to estimate customer mobility flow between supermarket zones. We use anonymized mobility data of customers in supermarkets to calibrate our models and apply variants of the gravity and intervening-opportunities models to fit this mobility flow and estimate the flow on unseen data. We find that a doubly-constrained gravity model can successfully estimate 65-70% of the flow inside supermarkets. We then investigate how to reduce congestion in supermarkets by combining mobility models with queueing networks. We use a simulated-annealing algorithm to find store layouts with lower congestion than the original layout. Our research gives insight both into how customers move in supermarkets and into how retailers can arrange stores to reduce congestion. It also provides a case study of human mobility on small spatial scales.