Past Networks Seminar

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.

We investigate a nonlinear version of coevolving voter models, in which both node states and network structure update as a coupled stochastic dynamical process. Most prior work on coevolving voter models has focused on linear update rules with fixed rewiring and adopting probabilities. By contrast, in our nonlinear version, the probability that a node rewires or adopts is a function of how well it "fits in" within its neighborhood. To explore this idea, we incorporate a parameter σ that represents the fraction of neighbors of an updating node that share its opinion state. In an update, with probability σq (for some nonlinearity parameter q), the updating node rewires; with complementary probability 1−σq, the updating node adopts a new opinion state. We study this mechanism using three rewiring schemes: after an updating node deletes a discordant edge, it then either (1) "rewires-to-random" by choosing a new neighbor in a random process; (2) "rewires-to-same" by choosing a new neighbor in a random process from nodes that share its state; or (3) "rewires-to-none" by not rewiring at all (akin to "unfriending" on social media). We compare our nonlinear coevolving model to several existing linear models, and we find in our model that initial network topology can play a larger role in the dynamics, whereas the choice of rewiring mechanism plays a smaller role. A particularly interesting feature of our model is that, under certain conditions, the opinion state that is initially held by a minority of nodes can effectively spread to almost every node in a network if the minority nodes views themselves as the majority. In light of this observation, we relate our results to recent work on the majority illusion in social networks.

Reference: 

Kureh, Yacoub H., and Mason A. Porter. "Fitting In and Breaking Up: A Nonlinear Version of Coevolving Voter Models." arXiv preprint arXiv:1907.11608 (2019).

The vulnerability of a host population to a specific disease measures how likely pathogen introduction will lead to an epidemic outbreak, and how hard it is to contain or eliminate an ongoing one. Predicting vulnerability is thus key to designing risk-reduction strategies that limit disease burden on public health and economic development. To do that, highly-resolved data tracking contacts and mobility of the host population need to integrate into detailed models of disease dynamics. This represents a twofold challenge. Firstly, we need theoretical frameworks that turn data feeds into predictors of epidemic risk, and can identify which of the structural features of the host population drive its vulnerability. Secondly, we need new ways to access, analyze, and share the relevant contact and mobility data: a necessary step to make our predictions realistic and reliable. In my talk, I will address both issues. I will show how to analytically derive the conditions that discriminate between epidemic regime and quick pathogen extinction, by representing empirically measured contacts as time-evolving complex networks. The analytical core of this theory leads to a broad range of applications. At the same time, its data-driven nature prompts context-specific predictions that can inform policymaking, as I will show in two case studies: reorganizing nurse scheduling to reduce the risk of spread of healthcare-associated infections; linking the features of livestock trade movements to the spatial spread of cattle diseases. The latter application is also an example of how limited access and incomplete data collection represent a big hurdle to predictive vulnerability analysis. To overcome this, I will present a collaborative platform for analyzing and comparing trade networks coming from several European countries. Using a bring code to the data approach, our platform surmounts the strict regulations preventing data sharing, and builds an algorithm that predicts vulnerability even in situations when limited data on cattle trade are available. The ultimate goal of all these theoretical and numerical developments is to inform strategies that reduce the vulnerability of the host population by restructuring its contacts. However, such restructuring may entail a feedback effect, acting as selective pressure on the pathogen itself. In the last part of my talk, I will extend the developed formalism to modeling evolutionary pathways that maximize the invasion potential of the pathogen, given the observed host population structure. Specifically, I will link the emergence of exotic replication behaviors in plant-infecting viruses to historical changes in plant distribution patterns.

In recent years, much attention has been given to single-cell RNA sequencing techniques as they allow researchers to examine the functions and relationships of single cells inside a tissue. In this study, we combine single-cell RNA sequencing data with protein–protein interaction networks (PPINs) to detect active modules in cells of different transcriptional states. We achieve this by clustering single-cell RNA sequencing data, constructing node-weighted PPINs, and identifying the maximum-weight connected subgraphs with an exact Steiner-Tree approach. As a case study, we investigate RNA sequencing data from human liver spheroids but the techniques described here are applicable to other organisms and tissues. The benefits of our novel method are two-fold: First, it allows us to identify important proteins (e.g., receptors) which are not detected from a differential gene-expression analysis as they only interact with proteins that are transcribed in higher levels. Second, we find that different transcriptional states have different subnetworks of the PPIN significantly overexpressed. These subnetworks often reflect known biological pathways (e.g., lipid metabolism and stress response) and we obtain a nuanced picture of cellular function as we can associate them with a subset of all analysed cells.

Short- and long-term memories are distinguished by their forgettability. Most of what we perceive and store is lost rather quickly to noise, as new sensations replace older ones, while some memories last for as long as we live. Synaptic dynamics is key to the process of memory storage; in this talk I will discuss a few approaches we have taken to this problem, culminating in a model of synaptic networks containing both cooperative and competitive dynamics. It turns out that the competitionbetween synapses is key to the natural emergence of long-term memory in this model, as in reality.

References
​Mehta, Anita. "Storing and retrieving long-term memories: cooperation and competition in synaptic dynamics." Advances in Physics: X 3.1 (2018): 1480415.

The comparison of graphs is a vitally important, yet difficult task which arises across a number of diverse research areas including biological and social networks. There have been a number of approaches to define graph distance however often these are not metrics (rendering standard data-mining techniques infeasible), or are computationally infeasible for large graphs. In this work, we define a new metric based on the spectrum of the non-backtracking graph operator and show that it can not only be used to compare graphs generated through different mechanisms but can reliably compare graphs of varying size. We observe that the family of Watts-Strogatz graphs lie on a manifold in the non-backtracking spectral embedding and show how this metric can be used in a standard classification problem of empirical graphs.

Complexity Science aims to understand what is that makes some systems to be "more than the sum of their parts". A natural first step to address this issue is to study networks of pairwise interactions, which have been done with great success in many disciplines -- to the extend that many people today identify Complexity Science with network analysis. In contrast, multivariate complexity provides a vast and mostly unexplored territory. As a matter of fact, the "modes of interdependency" that can exist between three or more variables are often nontrivial, poorly understood and, yet, are paramount for our understanding of complex systems in general, and emergence in particular. 
In this talk we present an information-theoretic framework to analyse high-order correlations, i.e. statistical dependencies that exist between groups of variables that cannot be reduced to pairwise interactions. Following the spirit of information theory, our approach is data-driven and model-agnostic, being applicable to discrete, continuous, and categorical data. We review the evolution of related ideas in the context of theoretical neuroscience, and discuss the most prominent extensions of information-theoretic metrics to multivariate settings. Then, we introduce the O-information, a novel metric that quantify various structural (i.e. synchronous) high-order effects. Finally, we provide a critical discussion on the framework of Integrated Information Theory (IIT), which suggests an approach to extend the analysis to dynamical settings. To illustrate the presented methods, we show how the analysis of high-order correlations can reveal critical structures in various scenarios, including cellular automata, Baroque music scores, and various EEG datasets.

References:
[1] F. Rosas, P.A. Mediano, M. Gastpar and H.J. Jensen, ``Quantifying High-order Interdependencies via Multivariate Extensions of the Mutual Information'', submitted to PRE, under review.
https://arxiv.org/abs/1902.11239
[2] F. Rosas, P.A. Mediano, M. Ugarte and H.J. Jensen, ``An information-theoretic approach to self-organisation: Emergence of complex interdependencies in coupled dynamical systems'', in Entropy, vol. 20 no. 10: 793, pp.1-25, Sept. 2018.
https://www.mdpi.com/1099-4300/20/10/793

 

Coupling dynamics of the states of the nodes of a network to the dynamics of the network topology leads to generic absorbing and fragmentation transitions. The coevolving voter model is a typical system that exhibits such transitions at some critical rewiring. We study the robustness of these transitions under two distinct ways of introducing noise. Noise affecting all the nodes destroys the absorbing-fragmentation transition, giving rise in finite-size systems to two regimes: bimodal magnetization and dynamic fragmentation. Noise targeting a fraction of nodes preserves the transitions but introduces shattered fragmentation with its characteristic fraction of isolated nodes and one or two giant components. Both the lack of absorbing state for homogeneous noise and the shift in the absorbing transition to higher rewiring for targeted noise are supported by analytical approximations.

Paper Link:

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.92.032803

Social surveys are widely used in today's society as a method for obtaining opinions and other information from large groups of people. The questions in social surveys are usually presented in either multiple-choice or free-response formats. Despite their advantages, free-response questions are employed less commonly in large-scale surveys, because in such situations, considerable effort is needed to categorise and summarise the resulting large dataset. This is the so-called coding problem. Here we propose a survey framework in which, respondents not only write down their own opinions, but also input information characterising the similarity between their individual responses and those of other respondents. This is done in much the same way as ``likes" are input in social network services. The information input in this simple procedure constitutes relational data among opinions, which we call the opinion graph. The diversity of typical opinions can be identified as a modular structure of such a graph, and the coding problem is solved through graph clustering in a statistically principled manner. We demonstrate our approach using a poll on the 2016 US presidential election and a survey given to graduates of a particular university.

George Soules [1] introduced a set of vectors $r_1,...,r_N$ with the remarkable property that for any set of ordered numbers $\lambda_1\geq\dots\geq\lambda_N$, the matrix $\sum_n \lambda_nr_nr_n^T$ has nonnegative off-diagonal entries. Later, it was found [2] that there exists a whole class of such vectors - Soules vectors - which are intimately connected to binary rooted trees. In this talk I will describe the construction of Soules vectors starting from a binary rooted tree, and introduce some basic properties. I will also cover a number of applications: the inverse eigenvalue problem, equitable partitions in Laplacian matrices and the eigendecomposition of the Clauset-Moore-Newman hierarchical random graph model.

[1] Soules (1983), Constructing Symmetric Nonnegative Matrices
[2] Elsner, Nabben and Neumann (1998), Orthogonal bases that lead to symmetric nonnegative matrices

Commuting concerns people’s spatial behaviour resulting from the geographic separation of home and workplace and is connected with their willingness to seek economic opportunities outside their place of residence (Rouwendal J., Nijkamp P., 2004). Such opportunities are usually found in the urban areas, so this phenomenon is often a subject of urban studies or research focusing on city centres (Drejerska N., Chrzanowska M., 2014). In literature, commuting patterns are used to determine the boundaries of local and regional labour markets. Furthermore, labour market is one of the most important features for the delimitation of functional regions, as commuting involves not only working outside one’s place of residence but also, among other things, using various services offered there, from shopping to health or cultural services. Taking this into account, it can be stated that commuting is an important characteristic of relations between territories, and these relations form complex networks.

People decide to commute to work for various reasons. Most commuters travel from a small town, village or rural area to a city or town where they have a wider range of employment opportunities. However, people differ in their attitudes toward commuting. While some people find it troublesome, others enjoy their daily travel. There are also people who regard commuting as the necessary condition for supporting themselves and their families. Therefore, commuting is an important factor that should be taken into account in the research on the quality of life and quality of work.

The main goals of this presentation is to identify and analyse relations between communities (municipalities) from the perspective of labour market, especially commuting in the vicinity of Warsaw, Data on the number of commuters come from the Central Statistical Office of Poland and cover the year 2011.

 Bibliography

Drejerska N., Chrzanowska M., 2014: Commuting in the Warsaw suburban area from a spatial perspective – an example of empirical research, Acta Universitatis Lodziensis. Folia Oeconomica 2014, Vol. 6, no 309, pp. 87-96.

Rouwendal J., Nijkamp P., 2004: Living in Two Worlds: A Review of Home-to-Work Decisions, Growth and Change, Volume 35, Issue 3, p. 287.