- This event has passed.
YEP XV “Information Diffusion on Random Networks”
Mar 25, 2019 - Mar 29, 2019
Summary
When available, the slide presentations of the speakers have been added to this website, please see “Abstracts”.
The “Information diffusion on random graphs” workshop is the 15th workshop in the ‘Young European Probabilists’ yearly workshops.
Diffusion processes in networks manifests themselves in many real-life scenarios, such as epidemic spreading, viral marketing and power blackouts. This YEP workshop focuses information diffusion on networks. The phenomenon of information diffusion recently attracted vast attention across a wide range of research fields, including mathematics, physics, computer science, and social sciences. Therefore, this YEP will focus not only on purely probabilistic aspects, but also take an algorithmic and application perspective. The aim of the workshop is to bring together junior and senior researchers from probability and from other fields, and to bridge the corresponding scientific communities.
The workshop will have three mini courses by internationally renowned researchers, giving an opportunity to junior as well as senior attendants to learn about a new topic related to information diffusion. Other than that, the workshop will consist of invited talks by junior and senior researchers.
Sponsors
Organizers
| Remco van der Hofstad | TU Eindhoven |
| Nelly Litvak | University of Twente/TU Eindhoven |
| Clara Stegehuis | TU Eindhoven |
Speakers
When available, the slide presentations of the speakers have been added to this website, please see “Abstracts”.
Tutorial speakers:
| Frank Ball | University of Nottingham |
| Mia Deijfen | Stockholm University |
| Renaud Lambiotte | University of Oxford |
Invited speakers:
| Claudio Castellano | Sapienza, Rome |
| Eric Cator | Radboud University Nijmegen |
| Wei Chen | Microsoft Research Asia |
| Petter Holme | Tokyo Institute of Technology |
| Marton Karsai | ENS Lyon |
| Juliá Komjathy | TU Eindhoven |
| Lasse Leskelä | Aalto University |
| Naoki Masuda | University of Bristol |
| Peter Mörters | Cologna University |
| David Sirl | University of Nottingham |
| Chi Tran | Université des Sciences et Technologies de Lille |
| Daniel Valesin | University of Groningen |
| Rose Yu | Northeastern University |
Contributed talks/posters
During the conference we have a few slots available for contributed talks by participants.
Programme
Abstracts
Caio Alvez (contributed)
In this talk we will discuss our recent work introducing a model of preferential attachment random graphs where the asymptotic ratio between vertices and edges of the graph is governed by a non-increasing regularly varying function f: N-> [0,1], which we call the edge-step function. We prove general results about the associated empirical degree distribution, as well as topological results about the graph’s clique number and diameter. Except for the case of the diameter of slowly varying functions, which exhibit a wider range of behavior, our results depend essentially on the index of regularity of f at infinity. We then discuss applications of the above results for the contact process and bootstrap percolation process in these random graphs. Joint work with Rémy Sanchis Rodrigo Ribeiro and Daniel Valesin.
Epidemics on networks
PRESENTATION: Epidemics on networks 1 Epidemics on networks 2
There has been considerable interest in the past two decades in models for the spread of epidemics on networks. The usual paradigm is that the population is described by an undirected random graph and disease can spread only along the edges of the graph. This mini-course gives an introduction to the analysis of SIR (susceptible-infective-recovered) epidemics on configuration model (and related) networks, which is by far the most studied class of such epidemics. Topics covered include:
- branching process approximation for the early stages of an epidemic, which determines whether or not an epidemic with few initial infectives can become established and lead to a major outbreak;
- susceptibility sets and the final outcome of a major outbreak;
- effective degree analysis of models, which yields a functional central limit theorem (CLT) for the temporal behaviour and a CLT for the final outcome of a major epidemic;
- models with superimposed household structure, a key component of human populations which can have a significant impact on disease dynamics;
- vaccination schemes, including acquaintance vaccination which targets high-degree individuals.
Information and Influence Propagation in Social Networks: Modeling and Influence Maximization
PRESENTATION: Information and Influence Propagation in Social Networks
Information and influence propagation is a fundamental phenomenon in social networks that leads to many applications both for business and for public good, such as viral marketing, social recommendations, rumor control, epidemic prevention, etc. In this talk, I will survey the research area on information/influence diffusion dynamics and the influence maximization problem, which is the problem of selecting a small number of seed nodes in a social network such that their influence spread is maximized. The talk will cover basic stochastic diffusion models, algorithmic techniques for scalable influence maximization, as well as some of my recent research work on influence-based centrality, competitive and complementary influence diffusion, etc.
Emilio Cruciani (contributed)
We investigate the behavior of a simple majority dynamics on networks of agents whose interaction topology exhibits a community structure. By leveraging recent advancements in the analysis of dynamics, we prove that, when the states of the nodes are randomly initialized, the system rapidly and stably converges to a configuration in which the communities maintain internal consensus on different states. This is the first analytical result on the behavior of dynamics for non-consensus problems on non-complete topologies, based on the first symmetry-breaking analysis in such setting.
Our result has several implications in different contexts in which dynamics are adopted for computational and biological modeling purposes. In the context of Label Propagation Algorithms, a class of widely used heuristics for community detection, it represents the first theoretical result on the behavior of a distributed label propagation algorithm with quasi-linear message complexity. In the context of evolutionary biology, dynamics such as the Moran process have been used to model the spread of mutations in genetic populations (Lieberman, Hauert, and Nowak 2005); our result shows that, when the probability of adoption of a given mutation by a node of the evolutionary graph depends super-linearly on the frequency of the mutation in the neighborhood of the node and the underlying evolutionary graph exhibits a community structure, there is a non-negligible probability for species differentiation to occur.
Competing growth on lattices and graphs
PRESENTATION: Competition -References
Competing first passage percolation describes the growth of two competing infections on an underlying graph structure. It was first studied on the Z^d-lattice. The main question is if the infection types can grow to occupy infinite parts of the lattice simultaneously, the conjecture being that the answer is yes if and only if the infections grow with the same intensity. Recently, the model has been analyzed on more heterogeneous graph structures, where the degrees of the vertices can have an arbitrary distribution. In this case, it turns out that also the degree distribution plays a role in determining the outcome of the competition. I will give a survey of existing results, both on Z^d and on heterogeneous graphs, and describe open problems. I will also describe related competition models such as the multitype contact process and models driven by moving particles.
Peter Gracar (contributed)
Spread of infection by random walks – Multi-scale percolation along a Lipschitz surface
A conductance graph on $\mathbb{Z}^d$ is a nearest-neighbor graph where all of the edges have positive weights assigned to them. We first consider a point process of particles on the nearest neighbour graph $(\mathbb{Z}^d,E)$ and show some known results about the spread of infection between particles performing continuous time simple random walks. Next, we extend consider the case of uniformly elliptic random graphs on $\mathbb{Z}^d$ and show that the infection spreads with positive speed also in this more general case. We show this by developing a general multi-scale percolation argument using a two-sided Lipschitz surface that can also be used to answer other questions of this nature. Joint work with Alexandre Stauffer.
Temporal networks of human interaction
The power of any kind of network approach lies in the ability to simplify a complex system so that one can better understand its function as a whole. Sometimes it is beneficial, however, to include more information than in a simple graph of only nodes and links. Adding information about times of interactions—modeling your system as temporal networks—can make predictions and mechanistic understanding more accurate. Just as there can be network structures affecting disease spreading, temporal structures can also govern the spreading dynamics. We will discuss recent developments in the analysis of temporal networks, including community detection, the definition of time scales, random walks and various forms of spreading processes. We argue that adding time to network representations fundamentally changes our usual network concepts—so much that it is perhaps meaningless to think of temporal networks as an extension of the network paradigm.
How to stop explosion by penalising transmission to hubs
In this talk we study the spread of information in infinite inhomogeneous spatial random graphs.
To model the spread of information in social networks, we take a spatial random graph that is scale free, that is, the degree of a vertex follows a power law with exponent tau in (2,3). One common approach to model the spread information is then to equip each edge with a random and iid transmission cost L, and study the cost of the least-cost past between vertices. In these graphs, it was observed earlier than it is possible to reach infinitely many vertices within finite cost, as long as the cumulative distribution function of L is not doubly-exponentially flat close to 0. This phenomenon is called explosion, and it seems off from reality for cases where individual contact is necessary, e.g., spreading of viruses, etc.
We introduce a penalty to transmit the information to hubs, and increase the cost of transmission through an edge with expected degrees W and Z by a factor that is a power of the product WZ.
We find a threshold behaviour between explosion, depending on how steep the cumulative distribution function of L increases at 0: it should be at least polynomially steep, where the exponent depends on both the power-law exponent tau and the penalty-exponent.
This behaviour is arguably a better representation of information spreading processes in social networks than the case without penalizing factor.
PRESENTATION: Random walks on networks 1 Random walks on networks 2
Diffusion and Communities in Networks
The presence of communities, or clusters, in networks is well known to affect diffusive processes. Conversely, tracking the trajectories of random walkers on the graph can be used to uncover communities hidden in large graphs. During this tutorial, I will review the relations between the two sides of the problem, and present in detail community detection methods based on first-order and higher-order Markov models, as well as methods allowing to uncover non-assortative communities in networks.
Statistical graph models induced by overlapping communities of variable sizes and strengths
Information transmission in today’s society is more and more realized through overlapping communities of various sizes and strengths. This talk discusses a statistical network model where a pair of nodes sharing a community are linked with probability determined by the community strength. The model is parametrized by a limiting empirical joint distribution of community sizes and strengths, allowing to capture the property that large communities often provide weaker pairwise links. A natural property of the model is that high variability of community sizes causes the degree distribution to have heavy tails. The main focus of this talk is to discuss the effect of size-strength correlations on graph parameters relevant to information diffusion, especially the transitivity spectrum. Based on joint work with Mindaugas Bloznelis (Vilnius U).
Epidemic processes on dynamically switching networks: Effects of commutator and concurrency
Epidemic processes on temporally varying networks are complicated by complexity of both network structure and temporal dimensions. We analyse the susceptible-infected-susceptible (SIS) epidemic model on regularly switching networks, where each contact network is used for a finite fixed duration before switching to another. First, we analyse the epidemic threshold under a deterministic approximation called the individual-based approximation. We show that, under this approximation, temporality of networks lessens the epidemic threshold such that infections persist more easily in temporal networks than in their static counterparts. We further show that the commutator bracket of the adjacency matrices at different times is empirically a useful predictor of the impact of temporal networks on the epidemic threshold. The second topic is the effects of concurrency (i.e., the number of neighbours that a node has at a given time point) on the epidemic threshold in the stochastic SIS dynamics. For a particular switching network model, we show that network dynamics can suppress epidemics (i.e., yield a higher epidemic threshold) when nodes’ concurrency is low (where stochasticity effects are stronger) and can enhance epidemics when the concurrency is high.
Metastability of the contact process on evolving scale-free networks
We study the contact process in the regime of small infection rates on scale-free networks evolving by stationary dynamics. A parameter allows us to interpolate between slow (static) and fast (mean-field) network dynamics. For two paradigmatic classes of networks we investigate transitions between phases of fast and slow extinction and in the latter case we analyse the density of infected vertices in the metastable state. The talk is based on joint work with Emmanuel Jacob (ENS Lyon) and Amitai Linker (Universidad de Chile).
Gergely Odor (contributed)
In sensor based source localization we attempt to detect the source of an epidemic process spreading in a graph, given the time of infection of the sensor nodes. We are interested in the minimal number of sensors we need to select for perfect detection when the epidemic is deterministic (i.e. each sensor reports its distance from the source), and the graph is drawn from the Erdos-Renyi distribution. When the sensors are selected before any of the observations are made, this problem reduces to the Metric Dimension problem, which has already been analysed for Erdos-Renyi graphs. In this talk, we consider a modified version of the problem, when the sensors are selected sequentially, adaptively to previous observations. We present tight bounds for the reduction in the number of required sensors compared to the non-adaptive version of the problem.
Guilherme Reis (contributed)
Interacting diffusions on random graphs
We consider systems of diffusion processes whose interactions are described by a graph. For example, traditional mean-field interacting diffusions correspond to a complete interaction graph. In recent years some effort has been directed to understanding more general interactions. When the interaction graph is random, in the particular case of the Erd\H{o}s-R\'{e}nyi random graph, we show how the behavior of this particle system changes whether the mean degree of the Erd\”{o}s-R\'{e}nyi graph diverges to infinity or converges to a constant. When the mean degree converges to a constant we exploit a locality property of this system. Loosely speaking, the locality property states that information does not propagate too fast over the graph for this kind of particle system.
Markus Schepers (contributed)
The local clustering coefficient in hyperbolic random graphs
The local clustering coefficient is a quantity which has been studied for its influence on diffusive processes on a graph. For a given vertex of the graph it measures the extent to which its neighbourhood resembles a complete graph. Hyperbolic random graphs are given by a collection of points distributed uniformly in a hyperbolic disk with edges between nearby vertices. This model was invented by Krioukov et al. and has been suggested as a suitable model for real-world networks such as the Internet.
In this project we study the local clustering coefficient averaged over all vertices and averaged over all vertices of degree k in the hyperbolic random graph in the probabilistic limit (convergence in probability) as the number of vertices n tends to infinity.
We consider both the case of a fixed degree k, as well as a sequence of degrees (kn) tending to
infinity. We derive exact analytic limiting expressions as well as the asymptotic scaling
(including the multiplicative constant).
(joint work with: Nikolaos Fountoulakis, Pim van der Hoorn, Tobias Müller)
A network epidemic model with preventive rewiring
Network epidemic models have developed enormously in the last 20 years or so in response to some of the unrealistic assumptions of homogeneity in most simple epidemic models. A significant feature of most epidemic-on-a-network models is that the epidemic evolves on a static network.
We consider an SIR (Susceptible – Infectious – Removed) epidemic spreading on a configuration-model network (a random network with specified degree distribution), with the addition of some simple network dynamics. The addition is to allow susceptible individuals to “drop” connections to infectious neighbours. A further extension permits such susceptible individuals to then “rewire” to connect instead with someone else in the population.
For the model with dropping only (i.e. with no rewiring), we present some limit theorems (in the limit of large population size) for the temporal evolution of the model and for the final size of the epidemic (the number of initial susceptibles that are ultimately recovered). For the model with rewiring included too, we show that whilst the preventive behaviour of rewiring is always rational at the individual level, it may have negative consequences at the population level.
This work is joint with Frank Ball (Nottingham), Tom Britton (Stockholm) and KaYin Leung (Stockholm).
Réka Szabo (contributed)
We consider an inhomogeneous percolation model on an oriented regular tree, where besides the usual bonds, additional bonds of a certain length are also present. Percolation is defined on this graph, by letting these additional edges be open with probability q and every other edge with probability p. We give an improved lower bound for the critical curve which delimits the set of pairs (p, q) for which there is almost surely no infinite cluster. Furthermore, we show that the cluster of the root has the same distribution as the family tree of a certain multi-type branching process, which allows us to state some limit theorems. Joint work with D. Valesin and B. N. B. de Lima.
Sam Thomas (contributed)
We study the behaviour of random walk on dynamical percolation. In this model, the edges of a graph are either open or closed and refresh their status at rate μ, while at the same time a random walker moves on G at rate 1, but only along edges which are open. In this talk I present recent results proving cutoff in the case when G is the complete graph and the bond percolation parameter is of order 1/n, ie we consider a random walk on dynamical Erdos-Renyi graph. We do this via an explicit coupling argument. Joint work with Perla Sousi
User-driven exploration of social networks with application in epidemiology
To understand the spread of certain diseases such as HIV or HCV, the modelling of social networks (sexual partners or people who inject drug together) is important. In the case of HCV, the network is hidden since drug use is illegal. We have designed in Paris a ‘Respondent-driven’ study to discover the social network of people who inject drugs (PWIDs). The underlying idea is to have the graph explored by random (branching) walks: each interviewee receives a certain number of coupons that she/he distributes to her/his injection partners. After having described the general case, we focus on what happens for the family of Stochastic Block Model graphs. Which proportion of the graph can we discover and what can be said on the topologies that are found ?
Viktoria Vadon (contributed)
Percolation on the Random Intersection Graph with Communities
The Random Intersection Graph with Communities (RIGC) models a network based on individuals and communities they are part of, with two key features: each community has its arbitrary internal structure described by a small graph, and communities are allowed to overlap. It generalizes the classical Random Intersection Graph (RIG) model, and is constructed based on a Bipartite Configuration Model. We study percolation, i.e., independent removal of edges, as a simple model for a randomized information spread: we view the connected component of a vertex as the cluster this vertex is able to broadcast information to. We show that percolation on the RIGC, in particular, percolation on the classical RIG, is (again) an RIGC with different parameters, and prove that percolation on the RIGC exhibits a phase transition, in terms of whether a linear-sized component persists. We may touch on robustness, and why robustness of edge and vertex percolation behave differently.
The asymmetric multitype contact process
We study a class of interacting particle systems known as the multitype contact process on Z^d. In this model, sites of Z^d can be either empty or occupied by an individual of one of two species. Individuals die with rate one and send descendants to neighboring sites with a rate that depends on their (the parent’s) type. Births are not allowed at sites that are already occupied. We assume that one of the types has a birth rate that is larger than that of the other type, and larger than the critical value of the standard contact process. We prove that, if initially present, the stronger type has a positive probability of never going extinct. Conditionally on this event, it takes over a ball of radius growing linearly in time. We also completely characterize the set of stationary distributions of the process and prove a complete convergence theorem. Joint work with Pedro L. B. Pantoja and Thomas Mountford.
Learning Graph Diffusion with Deep Neural Networks
Diffusion processes on graphs have complex dynamics. Due to their complexity, learning graph diffusion often relies on strong assumptions or is computationally expensive. Deep neural networks provide flexible models for modeling complex data. While existing deep neural networks have shown to be highly effective in, for example, computer vision and natural language processing, off-the-shelf deep models have limited utility in modeling graph-structured data.
In this talk, I will showcase how to design deep neural networks to learn the dynamics of graph diffusion. In particular, I will discuss (1) Diffusion Convolution Recurrent Neural Networks (DCRNN): a neural sequence model for spatiotemporal forecasting and (2) DAG to DAG Recursive Neural Networks (D2DRNN): a message passing neural network for DAG to DAG translation. I will also demonstrate successful applications of these models to real-world traffic prediction and Boolean expression simplification tasks.
Xiangying (Zoe) (contributed)
The Contact Process on Random Graphs and Galton-Watson Trees
The key to our investigation is an improved (and in a sense sharp) understanding of the survival time of the contact process on star graphs. Using these results, we show that for the contact process on Galton-Watson trees, when the offspring distribution (i) is subexponential the critical value for local survival $\lambda_2=0$ and (ii) when it is geometric($p$) we have $\lambda_2 \le C_p$, where the $C_p$ are much smaller than previous estimates. We also study the critical value $\lambda_c(n)$ for “prolonged persistence” on graphs with $n$ vertices generated by the configuration model. In the case of power law and stretched exponential distributions where it is known $\lambda_c(n) \to 0$ we give estimates on the rate of convergence. Physicists tell us that $\lambda_c(n) \sim 1/\Lambda(n)$ where $\Lambda(n)$ is the maximum eigenvalue of the adjacency matrix. Our results show that this is not correct.
Dong Yao (contributed)
The symbiotic contact process
We consider a contact process on $\ZZ^d$ with two species that interact in a symbiotic manner. Each site can either be vacant or host individuals of species A and/or B. Multiple occupancy by the same species at a single site is prohibited. Symbiosis is represented by a reduced death rate $\mu \in [0,1) $. If only one specie is present at a site then that particle dies with rate 1 but if both species are present then the death rate is reduced to $\mu$ for the two particles at that site. We prove that the critical infection rate $\lambda_c(\mu)$ for weak survival is of order $\sqrt{\mu}$, which coincides with the mean field calculation. We also investigate the nature of the phase transition. We show that in dimension $d=1$ the survival of the system is through oriented percolation. We also show that, for all dimensions, the phase transition is continuous and $\lambda_c(\mu)$ is 1 (regardless of the value of $\mu$), if we let particles move around with a rate going to infinity. The talk is based on ongoing work with Rick Durrett.
Xiu-Xiu Zhan (contributed)
Information Diffusion Backbones in Temporal Networks
Information diffusion on a temporal network can be modeled by viral spreading processes such as the Susceptible-Infected (SI) spreading process. An infected node meaning that the node possesses the information could spread the information to a Susceptible node with a given spreading probability β whenever a contact happens between the two nodes. Progress has been made in the understanding of how temporal network features and the choice of the source node affect the prevalence, i.e. the percentage of nodes reached by the information. In this work, we explore further: which node pairs are likely to contribute to the actual diffusion of information, i.e. appear in a diffusion trajectory? How is this related to the local temporal connection features of the node pair? Such deep understanding of the role of node pairs is crucial to explain and control the prevalence of information spread. First, we propose the construction of an information diffusion backbone G_B (β) for an SI spreading process with an infection probability β on a temporal network. The backbone is a weighted network where the weight of each node pair indicates how likely the node pair contributes to a diffusion process starting from an arbitrary node. Second, we investigate the relation between the backbones with different infection probabilities on a temporal network. We find that the backbone topologies obtained for low and high infection probabilities approach the backbone G_B (β→0) and G_B (β=1), respectively. The backbone G_B (β→0) equals the integrated weighted network, where the weight of a node pair counts the total number of contacts in between, a local temporal connection feature. Finally, we discover a local connection feature among many other features that could well predict which node pairs are likely to appear in G_B (β=1), whose computation complexity is high. This local feature encodes the time that each contact occurs, pointing out the importance of temporal features in determining the role of node pairs in a dynamic process beyond the features of the integrated network.
Registration
Link to the online registration form: REGISTRATION
Practical Information
Information on travel, location etc. : INFORMATION