Past Networks Seminar

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.

The advent of social media and the resulting ability to instantaneously communicate ideas and messages to connections worldwide is one of the great consequences arising from the telecommunications revolution over the last century. Individuals do not, however, communicate only upon a single platform; instead there exists a plethora of options available to users, many of whom are active on a number of such media. While each platform offers some unique selling point to attract users, e.g., keeping up to date with friends through messaging and statuses (Facebook), photo sharing (Instagram), seeing information from friends, celebrities and numerous other outlets (Twitter) or keeping track of the career paths of friends and past colleagues (Linkedin), the platforms are all based upon the fundamental mechanisms of connecting with other users and transmitting information to them as a result of this link.

In this talk a model for the spreading of online information or “memes" on multiplex networks is introduced and analyzed using branching-process methods. The model generalizes that of [Gleeson et al., Phys. Rev. X., 2016] in two ways. First, even for a monoplex (single-layer) network, the model is defined for any specific network defined by its adjacency matrix, instead of being restricted to an ensemble of random networks. Second, a multiplex version of the model is introduced to capture the behavior of users who post information from one social media platform to another. In both cases the branching process analysis demonstrates that the dynamical system is, in the limit of low innovation, poised near a critical point, which is known to lead to heavy-tailed distributions of meme popularity similar to those observed in empirical data.

[1] J. P. Gleeson et al. “Effects of network structure, competition and memory time on social spreading phenomena”. Physical Review X 6.2 (2016), p. 021019.

[2] J. D. O’Brien et al. "Spreading of memes on multiplex networks." New Journal of Physics 21.2 (2019): 025001.

With the introduction of supermarket loyalty cards in recent decades, there has been an ever-growing body of customer-level shopping data. A natural way to represent this data is with a bipartite network, in which customers are connected to products that they purchased. By predicting likely edges in these networks, one can provide personalised product recommendations to customers.
In this talk, I will first discuss a basic approach for recommendations, based on network community detection, that we have validated on a promotional campaign run by our industrial collaborators. I will then describe a multilayer network model that accounts for the fact that customers tend to buy the same grocery items repeatedly over time. By modelling such correlations explicitly, link-prediction accuracy improves considerably. This approach is also useful in other networks that exhibit significant edge correlations, such as social networks (in which people often have repeated interactions with other people), airline networks (in which popular routes are often served by more than one airline), and biological networks (in which, for example, proteins can interact in multiple ways). 
 

We propose a novel class of network models for temporal dyadic interaction data. Our objective is to capture important features often observed in social interactions: sparsity, degree heterogeneity, community structure and reciprocity. We use mutually-exciting Hawkes processes to model the interactions between each (directed) pair of individuals. The intensity of each process allows interactions to arise as responses to opposite interactions (reciprocity), or due to shared interests between individuals (community structure). For sparsity and degree heterogeneity, we build the non time dependent part of the intensity function on compound random measures following (Todeschini et al., 2016). We conduct experiments on real- world temporal interaction data and show that the proposed model outperforms competing approaches for link prediction, and leads to interpretable parameters.

Link to paper: https://papers.nips.cc/paper/7502-modelling-sparsity-heterogeneity-reci…

Many real-world networks contain small recurring connectivity patterns also known as network motifs. Although network motifs are widely considered to be important structural features of networks that are closely connected to their function methods for characterizing and modelling the local connectivity structure of complex networks remain underdeveloped. In this talk, we will present a non-parametric approach that is based on generative models in which networks are generated by adding not only single edges but also but also copies of larger subgraphs such as triangles to the graph. We show that such models can be formulated in terms of latent states that correspond to subgraph decompositions of the network and derive analytic expressions for the likelihood of such models. Following a Bayesian approach, we present a nonparametric prior for model parameters. Solving the resulting inference problem results in a principled approach for identifying atomic connectivity patterns of networks that do not only identify statistically significant connectivity patterns but also produces a decomposition of the network into such atomic substructures. We tested the presented approach on simulated data for which the algorithm recovers the latent state to a high degree of accuracy. In the case of empirical networks, the method identifies concise sets atomic subgraphs from within thousands of candidates that are plausible and include known atomic substructures.

There have been two main attempts so far to forecast the level of development of artificial intelligence (or ‘computerisation’) over time, Frey and Osborne (2013, 2017) and Manyika et al (2017). Unfortunately, their methodology seems to be flawed. Their results depend upon expert predictions of which occupations will be automatable in 2050, but these predictions are notoriously unreliable. Therefore, we develop an alternative which does not depend upon these expert predictions. We build a dataset of all the start-ups, firms, and university research laboratories working on automating different types of tasks, and use this to build a dynamic network model of them and how they interact. How automatable each type of task is ‘emerges’ from the model. We validate it, predicting the level of development of supervised learning in 2017 using data from the year 2000, and use it to forecast of the automatability of each of these task types from 2018 to 2050. Finally, we discuss extensions for our model; how it could be used to test the impact of public policy decisions or forecast developments in other high-technology industries.

We examine the relationship between social structure and sentiment through the analysis of a large collection of tweets about the Irish Marriage Referendum of 2015. We obtain the sentiment of every tweet with the hashtags #marref and #marriageref that was posted in the days leading to the referendum, and construct networks to aggregate sentiment and use it to study the interactions among users. Our analysis shows that the sentiment of outgoing mention tweets is correlated with the sentiment of incoming mentions, and there are significantly more connections between users with similar sentiment scores than among users with opposite scores in the mention and follower networks. We combine the community structure of the follower and mention networks with the activity level of the users and sentiment scores to find groups that support voting ‘yes’ or ‘no’ in the referendum. There were numerous conversations between users on opposing sides of the debate in the absence of follower connections, which suggests that there were efforts by some users to establish dialogue and debate across ideological divisions. Our analysis shows that social structure can be integrated successfully with sentiment to analyse and understand the disposition of social media users around controversial or polarizing issues. These results have potential applications in the integration of data and metadata to study opinion dynamics, public opinion modelling and polling.

The problem of authorship attribution (AA) involves matching a text of unknown authorship with its creator, found among a pool of candidate authors. In this work, we examine in detail authorship attribution methods that rely on networks of function words to detect an “authorial fingerprint” of literary works. Previous studies interpreted these word adjacency networks (WANs) as Markov chains, giving transition rates between function words, and they compared them using information-theoretic measures. Here, we apply a variety of network flow-based tools, such as role-based similarity and community detection, to perform a direct comparison of the WANs. These tools reveal an interesting relation between communities of function words and grammatical categories. Moreover, we propose two new criteria for attribution based on the comparison of connectivity patterns and the similarity of network partitions. The results are positive, but importantly, we observe that the attribution context is an important limiting factor that is often overlooked in the field's literature. Furthermore, we give important new directions that deserve further consideration.

Joint work with Zsolt Vizi (Bolyai Institute, University of Szeged, Hungary), Istvan Kiss (Department
of Mathematics, University of Sussex, United Kingdom)

Pairwise models have been proven to be a flexible framework for analytical approximations
of stochastic epidemic processes on networks that are in many situations much more accurate
than mean field compartmental models. The non-Markovian aspects of disease transmission
are undoubtedly important, but very challenging to incorporate them into both numerical
stochastic simulations and analytical investigations. Here we present a generalization of
pairwise models to non-Markovian epidemics on networks. For the case of infectious periods
of fixed length, the resulting pairwise model is a system of delay differential equations, which
shows excellent agreement with results based on the explicit stochastic simulations. For more
general distribution classes (uniform, gamma, lognormal etc.) the resulting models are PDEs
that can be transformed into systems of integro-differential equations. We derive pairwise
reproduction numbers and relations for the final epidemic size, and initiate a systematic
study of the impact of the shape of the particular distributions of recovery times on how
the time evolution of the disease dynamics play out.

Crime is a major risk to society’s well-being, particularly in cities, and yet the scientific literature lacks a comprehensive statistical characterization of crime that could uncover some of the mechanisms behind such pervasive social phenomenon. Evidence of nonlinear scaling of urban indicators in cities, such as wages and serious crime, has motivated the understanding of cities as complex systems—a perspective that offers insights into resources limits and sustainability, but usually without examining the details of indicators. Notably, since the nineteenth century, criminal activities have been known not to occur uniformly within a city. Crime concentrates in such way that most of the offenses take place in few regions of the city. However, though this concentration is confirmed by different studies, the absence of broad examinations of the characteristics of crime concentration hinders not only the comprehension of crime dynamics but also the proposal of sounding counter-measures. Here, we developed a framework to characterize crime concentration which splits cities into regions with the same population size. We used disaggregated criminal data from 25 locations in the U.S. and the U.K. which include offenses in places spanning from 2 to 15 years of data. Our results confirmed that crime concentrates regardless of city and revealed that the level of concentration does not scale with city size. We found that distribution of crime in a city can be approximated by a power-law distribution with exponent α that depends on the type of crime. In particular, our results showed that thefts tend to concentrate more than robberies, and robberies more than burglaries. Though criminal activities present regularities of concentration, we found that criminal ranks have the tendency to change continuously over time. Such features support the perspective of crime as a complex system which demands analyses and evolving urban policies covering the city as a whole. 

Disease transmission and rumour spreading are ubiquitous in social and technological networks. In this talk, we will present our last results on the modelling of rumour and disease spreading in multilayer networks.  We will derive analytical expressions for the epidemic threshold of the susceptible-infected-susceptible (SIS) and susceptible-infected-recovered dynamics, as well as upper and lower bounds for the disease prevalence in the steady state for the SIS scenario. Using the quasistationary state method, we numerically show the existence of disease localization and the emergence of two or more susceptibility peaks in a multiplex network. Moreover, we will introduce a model of epidemic spreading with awareness, where the disease and information are propagated in different layers with different time scales. We will show that the time scale determines whether the information awareness is beneficial or not to the disease spreading. 

Mechanical percolation is a phenomenon in materials processing wherein ‘filler’ rod-like particles are incorporated into polymeric materials to enhance the composite’s mechanical properties. Experiments have well-characterized a nonlinear phase transition from floppy to rigid behavior at a threshold filler concentration, but the underlying mechanism is not well understood. We develop and utilize an iterative graph compression algorithm to demonstrate that this experimental phenomenon coincides with the formation of a spatially extending set of mutually rigid rods (‘rigidity percolation’). First, we verify the efficacy of this method in two-dimensional fiber systems (intersecting line segments), then moving to the more interesting and mechanically representative problem of three-dimensional fiber systems (cylinders). We show that, when the fibers are uniformly distributed both spatially and orientationally, the onset of rigidity percolation appears to co-occur with a mean field prediction that is applicable across a wide range of aspect ratios.

There is a mismatch between levels of crime and its fear and often, cities might see an increase or a decrease in crime over time while the fear of crime remains unchanged. A model that considers fear of crime as an opinion shared by simulated individuals on a network will be presented, and the impact that different distributions of crime have on the fear experienced by the population will be explored. Results show that the dynamics of the fear is sensitive to the distribution of crime and that there is a phase transition for high levels of concentration of crime.

Matrix completion is an area of great mathematical interest and has numerous applications, including recommender systems for e-commerce. The recommender problem can be viewed as follows: given a database where rows are users and and columns are products, with entries indicating user preferences, fill in the entries so as to be able to recommend new products based on the preferences of other users. Viewing the interactions between user and product as links in a bipartite graph, the problem is equivalent to approximating a partially observed graph using clusters. We propose a divide and conquer algorithm inspired by the work of [1], who use recursive rank-1 approximation. We make the case for using an LP rank-1 approximation, similar to that of [2] by a showing that it guarantees a 2-approximation to the optimal, even in the case of missing data. We explore our algorithm's performance for different test cases.

[1]  Shen, B.H., Ji, S. and Ye, J., 2009, June. Mining discrete patterns via binary matrix factorization. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 757-766). ACM.

[2] Koyutürk, M. and Grama, A., 2003, August. PROXIMUS: a framework for analyzing very high dimensional discrete-attributed datasets. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 147-156). ACM.