Titles and Abstracts

Rumours, Epidemics and Consensus on Networks

The course will develop techniques for studying the long-term behaviour of random processes on networks. A large part of the motivation comes from computer science, where one is interested in designing decentralised algorithms for large networked systems such as the Internet or P2P networks or blockchain systems. Decentralised mechanisms for disseminating information or achieving consensus are typically a basic building block of such algorithms. Randomness can help create mechanisms which are exceptionally simple as well as highly robust, both to random faults and to malicious agents. Other motivations for the material studied in this course come from ecology, social science and economics, where one is interested in collective decision-making in humans and other animals, and from infectious disease epidemiology. The course will develop probabilistic tools for analysing these random processes. These mathematical methods have considerable elegance of their own.

References: 

• M. Draief and L. Massoulie, Epidemics and Rumours in Complex Networks, Cambridge University Press, 2009.

• A. J. Ganesh,  Complex Networks,  Course webpage.

Pre-requisites:  Knowledge of discrete probability is essential. Familiarity with Markov chains - at least discrete time and finite state space; for example see Chapter 1 of the 'Complex Networks' course listed above. Familiarity with Poisson processes will be helpful.

Statistical Inference for Combinatorial Data:
Graphical Models, Networks, and Rankings

The course will focus on statistical inference for combinatorial data, organized around three interrelated themes: graphical models, networks, and rankings. We will first discuss methods of estimation for dependent combinatorial data, specifically through the lens of the Ising model. Next, we will study estimation in inhomogeneous random graph models, graphons, and exponential random graph models. Finally, we will consider estimation problems for ranking models, such as the Bradley-Terry and Mallows models, and their applications to social choice theory.

References: 

• S. Janson, T. Łuczak, and A. Ruciński, Random Graphs, 2000.

• L. Lovász, Large Networks and Graph Limits, 2012. 

• S. Chatterjee, Large Deviations for Random Graphs, Lecture Notes in Mathematics, 2017

Prerequisites: Some background in discrete probability (first 2 chapters of the Janson et. al. book can be useful) and basic statistical inference (at the level of  G. Casella and R. L. Berger, Statistical Inference, 2002) would be helpful.