Past Networks Seminar

In this work, study the mean first saturation time (MFST), a generalization to the mean first passage time, on networks and show an application to the 2015 Burundi refugee crisis. The MFST between a sink node j, with capacity s, and source node i, with n random walkers, is the average number of time steps that it takes for at least s of the random walkers to reach a sink node j. The same concept, under the name of extreme events, has been studied in previous work for degree biased-random walks [2]. We expand the literature by exploring the behaviour of the MFST for node-biased random walks [1] in Erdős–Rényi random graph and geographical networks. Furthermore, we apply MFST framework to study the distribution of refugees in camps for the 2015 Burundi refugee crisis. For this last application, we use the geographical network of the Burundi conflict zone in 2015 [3]. In this network, nodes are cities or refugee camps, and edges denote the distance between them. We model refugees as random walkers who are biased towards the refugee camps which can hold s_j people. To determine the source nodes (i) and the initial number of random walkers (n), we use data on where the conflicts happened and the number of refugees that arrive at any camp under a two-month period after the start of the conflict [3]. With such information, we divide the early stage of the Burundi 2015 conflict into two waves of refugees. Using the first wave of refugees we calibrate the biased parameter β of the random walk to best match the distribution of refugees on the camps. Then, we test the prediction of the distribution of refugees in camps for the second wave using the same biased parameters. Our results show that the biased random walk can capture, to some extent, the distribution of refugees in different camps. Finally, we test the probability of saturation for various camps. Our model suggests the saturation of one or two camps (Nakivale and Nyarugusu) when in reality only Nyarugusu camp saturated.

[1] Sood, Vishal, and Peter Grassberger. ”Localization transition of biased random walks on random
networks.” Physical review letters 99.9 (2007): 098701.
[2] Kishore, Vimal, M. S. Santhanam, and R. E. Amritkar. ”Extreme event-size fluctuations in biased
random walks on networks.” arXiv preprint arXiv:1112.2112 (2011).
[3] Suleimenova, Diana, David Bell, and Derek Groen. ”A generalized simulation development approach
for predicting refugee destinations.” Scientific reports 7.1 (2017): 13377.

Graphs are a central object of study in various scientific fields, such as discrete mathematics, theoretical computer science and network science. These graphs are typically studied using combinatorial, algebraic or probabilistic methods, each of which highlights the properties of graphs in a unique way. I will discuss a novel approach to study graphs: the simplex geometry (a simplex is a generalized triangle). This perspective, proposed by Miroslav Fiedler, introduces techniques from (simplex) geometry into the field of graph theory and conversely, via an exact correspondence. We introduce the graph-simplex correspondence, identify a number of basic connections between graph characteristics and simplex properties, and suggest some applications as example.

Reference: https://arxiv.org/abs/1807.06475
 

Many protein interaction databases provide confidence scores based on the experimental evidence underpinning each in- teraction. The databases recommend that protein interac- tion networks (PINs) are built by thresholding on these scores. We demonstrate that varying the score threshold can re- sult in PINs with significantly different topologies. We ar- gue that if a node metric is to be useful for extracting bio- logical signal, it should induce similar node rankings across PINs obtained at different thresholds. We propose three measures—rank continuity, identifiability, and instability— to test for threshold robustness. We apply these to a set of twenty-five metrics of which we identify four: number of edges in the step-1 ego network, the leave-one-out dif- ference in average redundancy, average number of edges in the step-1 ego network, and natural connectivity, as robust across medium-high confidence thresholds. Our measures show good agreement across PINs from different species and data sources. However, analysis of synthetically gen- erated scored networks shows that robustness results are context-specific, and depend both on network topology and on how scores are placed across network edges. 

Fake accounts detection and users’ polarization are two very well known topics concerning the social media sphere, that have been extensively discussed and analyzed, both in the academic literature and in everyday life. Social bots are autonomous accounts that are explicitly created to increase the number of followers of a target user, in order to inflate its visibility and consensus in a social media context. For this reason, a great variety of methods for their detection have been proposed and tested. Polarisation, also known as confirmation bias, is instead the common tendency to look for information that confirms one's preexisting beliefs, while ignoring opposite ones. Within this environment, groups of individuals characterized by the same system of beliefs are very likely to form. In the present talk we will first review part of the literature discussing both these topics. Then we will focus on a new dataset collecting tweets from the last Italian parliament elections in 2018 and some preliminary results will be discussed.

Neural networks underpin both biological intelligence and modern AI systems, yet there is relatively little theory for how the observed behavior of these networks arises. Even the connectivity of neurons within the brain remains largely unknown, and popular deep learning algorithms lack theoretical justification or reliability guarantees.  In this talk, we consider paths towards a more rigorous understanding of neural networks. We characterize and, where possible, prove essential properties of neural algorithms: expressivity, learning, and robustness. We show how observed emergent behavior can arise from network dynamics, and we develop algorithms for learning more about the network structure of the brain.

Cascading phenomena are prevalent in natural and social-technical complex networks. We study the persistent cascade-recovery dynamics on random networks which are robust against small trigger but may collapse for larger one. It is observed that depending on the relative intensity of triggering and recovery, the network belongs one of the two dynamical phases: collapsing or active phase. We devise an analytical framework which characterizes not only the critical behaviour but also the temporal evolution of network activity in both phases. Results from agent-based simulations show good agreement with theoretical calculations. This work is an important attempt in understanding networked systems gradually evolving into a state of critical transition, with many potential applications.
 

Several scholars of evolutionary biology have suggested that functional redundancy (also known as "biological degener-
acy") is important for robustness of biological networks. Structural redundancy indicates the existence of structurally
similar subsystems that can perform the same function. Functional redundancy indicates the existence of structurally
di erent subsystems that can perform the same function. For networks with Ornstein--Uhlenbeck dynamics, Tononi et al.
[Proc. Natl. Acad. Sci. U.S.A. 96, 3257{3262 (1999)] proposed measures of structural and functional redundancy that are
based on mutual information between subnetworks. For a network of n vertices, an exact computation of these quantities
requires O(n!) time. We derive expansions for these measures that one can compute in O(n3) time. We use the expan-
sions to compare the contributions of di erent types of motifs to a network's functional redundancy.

Wikipedia has more than 40 million articles in 280 languages. It represents a decent coverage of human knowledge.
Even with its biases it can tell us a lot about what's important for people. London has an article in 238 languages and
Swansea has in 73 languages. Is London more "culturally" important than Swansea? Probably. 
We use this information and look at various factors that could help us model "cultural" importance of a city and hence
try to find the driving force behind sister city relationships.
We also look at creating cultural maps of different cities, finding the artsy/hipster, academic, political neighbourhoods of a city.

With the advent of large-scale data and the concurrent development of robust scientific tools to analyze them, important discoveries are being made in a wider range of scientific disciplines than ever before. A field of research that has gained substantial attention recently is the analytical, large-scale study of human behavior, where many analytical and statistical techniques are applied to various behavioral data from online social media, markets, and mobile communication, enabling meaningful strides in understanding the complex patterns of humans and their social actions.

The importance of such research originates from the social nature of humans, an essential human nature that clearly needs to be understood to ultimately understand ourselves. Another essential human nature is that they are creative beings, continually expressing inspirations or emotions in various physical forms such as a picture, sound, or writing. As we are successfully probing the social behaviors humans through science and novel data, it is natural and potentially enlightening to pursue an understanding of the creative nature of humans in an analogous way. Further, what makes such research even more potentially beneficial is that human creativity has always been in an interplay of mutual influence with the scientific and technological advances, being supplied with new tools and media for creation, and in return providing valuable scientific insights.

In this talk I will present two recent ongoing works on the mathematical analysis of color contrast in painting and measuring novelty in piano music.

The story of human progress is often described as a succession of ‘eras’ or ‘ages’ that are characterised by their most dominant technologies (e.g., the bronze age, the industrial revolution or the information age). In modern times, the fast pace of technological progress has accelerated the succession of eras. In addition, the increasing complexity of inventions has made the task of determining when eras begin and end more challenging, as eras are less about the dominance of a single technology and more about the way in which different technologies are combined. We present a data-driven method to determine and uncover technological eras based on networks and patent classification data. We construct temporal networks of technologies that co-appear in patents. By analyzing the evolution of the core-periphery structure and centrality time-series in these networks, we identify periods of time dominated by technological combinations which we identify as distinct ‘eras’. We test the performance of our method using a database of patents in Great Britain spanning a century, and identify five distinct eras.

Protein interaction networks (PINs) allow the representation and analysis of biological processes in cells. Because cells are dynamic and adaptive, these processes change over time. Thus far, research has focused either on the static PIN analysis or the temporal nature of gene expression. By analysing temporal PINs using multilayer networks, we want to link these efforts. The analysis of temporal PINs gives insights into how proteins, individually and in their entirety, change their biological functions. We present a general procedure that integrates temporal gene expression information with a monolayer PIN to a temporal PIN and allows the detection of modular structure using multilayer modularity maximisation.

The structure of the state of art of scientific research is an important object of study motivated by the understanding of how research evolves and how new fields of study stem from existing research. In the last years complex networks tools contributed to provide insights on the structure of research, through the study of collaboration, citation and co-occurrence networks, in particular keyword co-occurrence networks proved useful to provide maps of knowledge inside a scientific domain. The network approach focuses on pairwise relationships, often compressing multidimensional data structures and inevitably losing information. In this paper we propose to adopt a simplicial complex approach to co-occurrence relations, providing a natural framework for the study of higher-order relations in the space of scientific knowledge. Using topological methods we explore the shape of concepts in mathematical research, focusing on homological cycles, regions with low connectivity in the simplicial structure, and we discuss their role in the understanding of the evolution of scientific research. In addition, we map authors’ contribution to the conceptual space, and explore their role in the formation of homological cycles.

Authors: Daniele Cassese, Vsevolod Salnikov, Renaud Lambiotte
 

We study how the synchronizability of a diffusive network increases (or decreases) when we add some links in its underlying graph. This is of interest in the context of power grids where people want to prevent from having blackouts, or for neural networks where synchronization is responsible of many diseases such as Parkinson. Based on spectral properties for Laplacian matrices, we show some classification results obtained (with Tiago Pereira and Philipp Pade) with respect to the effects of these links.
 

Assortative mixing in networks is the tendency for nodes with the same attributes, or metadata, to link to each other. It is a property often found in social networks manifesting as a higher tendency of links occurring between people with the same age, race, or political belief. Quantifying the level of assortativity or disassortativity (the preference of linking to nodes with different attributes) can shed light on the factors involved in the formation of links and contagion processes in complex networks. It is common practice to measure the level of assortativity according to the assortativity coefficient, or modularity in the case of discrete-valued metadata. This global value is the average level of assortativity across the network and may not be a representative statistic when mixing patterns are heterogeneous. For example, a social network spanning the globe may exhibit local differences in mixing patterns as a consequence of differences in cultural norms. Here, we introduce an approach to localise this global measure so that we can describe the assortativity, across multiple scales, at the node level. Consequently we are able to capture and qualitatively evaluate the distribution of mixing patterns in the network. We find that for many real-world networks the distribution of assortativity is skewed, overdispersed and multimodal. Our method provides a clearer lens through which we can more closely examine mixing patterns in networks.

Link to arxiv paper:  https://arxiv.org/abs/1708.01236

Online discussions are the essence of many social platforms on the Internet. Discussion platforms are receiving increasing interest because of their potential to become deliberative spaces. Although previous studies have proposed approaches to measure online deliberation using the complexity of discussion networks as a proxy, little research has focused on how these networks are affected by changes of platform features.

In this talk, we will focus on how interfaces might influence the network structures of discussions using techniques like interrupted time series analysis and regression discontinuity design. Futhermore, we will review and extend state-of-the-art generative models of discussion threads to explain better the structure and growth of online discussions.
 

Systemic risk arises as a multi-layer network phenomenon. Layers represent direct financial exposures of various types, including interbank liabilities, derivative or foreign exchange exposures. Another network layer of systemic risk emerges through common asset holdings of financial institutions. Strongly overlapping portfolios lead to similar exposures that are caused by price movements of the underlying financial assets. Based on the knowledge of portfolio holdings of financial agents we quantify systemic risk of overlapping portfolios. We present an optimization procedure, where we minimize the systemic risk in a given financial market by optimally rearranging overlapping portfolio networks, under the constraints that the expected returns and risks of the individual portfolios are unchanged. We explicitly demonstrate the power of the method on the overlapping portfolio network of sovereign exposure between major European banks by using data from the European Banking Authority stress test of 2016. We show that systemic-risk-efficient allocations are accessible by the optimization. In the case of sovereign exposure, systemic risk can be reduced by more than a factor of two, without any detrimental effects for the individual banks. These results are confirmed by a simple simulation of fire sales in the government bond market. In particular we show that the contagion probability is reduced dramatically in the optimized network.
 

Many studies of digital communication, in particular of Twitter, use natural language processing (NLP) to find topics, assess sentiment, and describe user behaviour.
In finding topics often the relationships between users who participate in the topic are neglected.
We propose a novel method of describing and classifying online conversations using only the structure of the underlying temporal network and not the content of individual messages.
This method utilises all available information in the temporal network (no aggregation), combining both topological and temporal structure using temporal motifs and inter-event times.
This allows us to describe the behaviour of individuals and collectives over time and examine the structure of conversation over multiple timescales.
 

Current technological progress has raised concerns about automation of tasks performed by workers resulting in job losses. Previous studies have used machine learning techniques to compute the automation probability of occupations and thus, studied the impact of automation on employment. However, such studies do not consider second-order effects, for example, an occupation with low automation probability can have a  surplus of labor supply due to similar occupations being automated. In this work, we study such second-order effects of automation using a network approach.  In our network – the Job Space – occupations are nodes and edges link occupations which share a significant amount of work activities. By mapping employment, automation probabilities into the network, and considering the movement of workers, we show that an occupation’s position in the network may be crucial to determining its employment future.

A great deal of effort has gone into trying to model social influence --- including the spread of behavior, norms, and ideas --- on networks. Most models of social influence tend to assume that individuals react to changes in the states of their neighbors without any time delay, but this is often not true in social contexts, where (for various reasons) different agents can have different response times. To examine such situations, we introduce the idea of a timer into threshold models of social influence. The presence of timers on nodes delays the adoption --- i.e., change of state --- of each agent, which in turn delays the adoptions of its neighbors. With a homogeneous-distributed timer, in which all nodes exhibit the same amount of delay, adoption delays are also homogeneous, so the adoption order of nodes remains the same. However, heterogeneously-distributed timers can change the adoption order of nodes and hence the "adoption paths" through which state changes spread in a network. Using a threshold model of social contagions, we illustrate that heterogeneous timers can either accelerate or decelerate the spread of adoptions compared to an analogous situation with homogeneous timers, and we investigate the relationship of such acceleration or deceleration with respect to timer distribution and network structure. We derive an analytical approximation for the temporal evolution of the fraction of adopters by modifying a pair approximation of the Watts threshold model, and we find good agreement with numerical computations. We also examine our new timer model on networks constructed from empirical data.

Link to arxiv paper: https://arxiv.org/abs/1706.04252

Temporal networks are increasingly being used to model the interactions of complex systems. 
Most studies require the temporal aggregation of edges (or events) into discrete time steps to perform analysis.
In this article we describe a static, behavioural representation of a temporal network, the temporal event graph (TEG).
The TEG describes the temporal network in terms of both inter-event time and two-event temporal motifs.
By considering the distributions of these quantities in unison we provide a new method to characterise the behaviour of individuals and collectives in temporal networks as well as providing a natural decomposition of the network.
We illustrate the utility of the TEG by providing examples on both synthetic and real temporal networks.

Identifying clusters or "communities" of densely connected nodes in networks is an active area of research, with relevance to many applications. Recent advances in the field have focused especially on temporal, multiplex, and other kinds of multilayer networks.

One method for detecting communities in multilayer networks is to maximise a generalised version of an objective function known as modularity. Writing down multilayer modularity requires the specification of two types of resolution parameters, and choosing appropriate values is crucial for uncovering meaningful community structure. In the simplest case, there are just two parameters, one controlling the sizes of detected communities, and the other influencing how much communities change from layer to layer. By establishing an equivalence between modularity optimisation and a multilayer maximum-likelihood approach to community detection, we are able to determine statistically optimal values for these two parameters. 

When applied to existing multilayer benchmarks, our optimized approach performs significantly better than using parameter choices guided by heuristics. We also apply the method to supermarket data, revealing changes in consumer behaviour over time.