Past Networks Seminar

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.
 

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