Doctor Ayalvadi Ganesh, University of Bristol
The course will discuss a variety of stochastic processes over networks, which are both of interest in their own right and also play a role in many applications in computer science, in particular in the design and analysis of distributed algorithms.
Rumors and first-passage percolation: consider the complete graph on n vertices, where there is an edge between every pair of vertices. We associate with each edge a random weight, or length, drawn from an exponential distribution, independently across edges. We begin by studying the lengths of shortest paths between two vertices, its expectation, and fluctuations. We go on to study some related combinatorial optimisation problems in this model, which is called the stochastic mean-field model of distance. If time permits, we will also look at the problem of rumour source identification.
Voter model and variants: Consider a set of n agents connected by an arbitrary network. Each agent has an opinion, taking values in a finite set. Agents update their opinions by contacting other agents at random times and adopting their opinions. We study the time to consensus, and the probability of consensus on each possible value, in this model. We go on to discuss some variants of this model, and their application to majority voting.
Epidemics: We study the contact process or SIS epidemic on a connected network. Here, each node can be infected or susceptible. Susceptible nodes are infected at some constant rate by each of their infected neighbours, while infected nodes spontaneously recover after a random time and become immediately susceptible. We describe the survival time of the epidemic in large networks, and a sharp transition that it exhibits in many random graph models. We also study control policies for achieving short or long-lived epidemics.
This course was lectured at the ICTS School and Conference on Advances in Applied Probability, August 2019, Bangalore, and an earlier version at the Finnish Summer School in Stochastics, June 2012.
Ayalvadi Ganesh is an Associate Professor at the School of Mathematics at University of Bristol, UK. Ganesh graduated in electrical engineering from the Indian Institute of Technology, Madras, in 1988 and received the M.S. and Ph.D. degrees from Cornell University, Ithaca, NY, in 1991 and 1995, respectively. His research interests include communication networks, peer-to-peer and wireless networks, queueing theory, large deviations, and random graphs.
