Simons Chair Lectures on Network Mathematics
Speakers:
-
Prof. Sergey Foss, s.foss@hw.ac.uk, Heriot-Watt University, Edinburgh and Institute of Mathematics, Novosibirsk, will lecture on "Rare events in random walks and queueing networks in the presence of heavy-tailed distributions".
-
Dr. Laurent Massoulie, Laurent.Massoulie@inria.fr INRIA Microsoft Research Center, Paris, will lecture on "Spectral, submodular and semi-definite clustering in social networks."
The lectures will be held on Tuesday-Wednesday-Thursday May 7-9 from 9.30 to 12.30 in Room RLM 7.104.
Lecture Videos:
Conference Poster
Schedule
Tuesday May 7
9.30-9.35: Introduction
9:35-10.50: S. Foss, Lecture 1
10:50-11.15: Coffee break
11:15-12.30: L. Massoulie, Lecture 1
Wednesday May 8
9:30-10.45: L. Massoulie, Lecture 2
10:45-11.15: Coffee break
11:15-12.30: S. Foss, Lecture 2
Thursday May 9,
9:30-10.45: S. Foss, Lecture 3
10:45-11.15: Coffee break
11:15-12.30: L. Massoulie, Lecture 3
Registration
The lectures are expected to be of potential interest to faculty and students in several departments (mathematics, ECE, OR, CS).
For organizational reasons, please fill out the registration form here.
Abstracts
Sergey Foss
Rare Events in random walks and queueing networks in the presence of heavy-tailed distributions
The content of lectures is based on a book ``An Introduction to Heavy-Tailed and Subexponential Distributions'' by Foss, Korshunov and Zachary (Springer, 2011 --1st edition, 2013 -- 2nd edition) and on research papers.
I. I will start with definitions and properties of heavy- and long-tailed distributions. Then discuss the significance of coefficient 2 in the definition of subexponential (SE) distributions and their further tail properties. Then I will talk about various classes of SE distributions and the relations between them. The local and delta-subexponential distributions will also be introduced. If time allows, I will briefly introduce the class $S(\gamma )$ of light-tailed distributions that have properties similar to those of SE distributions.
II. In this lecture, I will consider sums, random sums and maxima of sums of SE random variables. The summands are either i.i.d. or Markov-modulated or conditionally independent. I will establish conditions for the `principle of a single big jump'' to hold: the most likely cause for the sum/maximum to be large is one large summand. Then I will provide an example of an SE distribution where the principle fails. Finally, I will derive the asymptotics for the time and height of the first overshoot over a high level.
III. In the last lecture I will consider queueing applications. I will analyse the asymptotics for the stationary sojourn/waiting time and queue length in the GI/GI/1 queue. Then I will then turn to tandems of queues, generalized Jackson networks, multi-access and some other systems - these are examples of monotone separable systems. Finally I will consider the stationary waiting time in a multi-server queue. is considered.
Laurent Massoulie
Spectral, submodular and semi-definite clustering in social networks
The objective of this course is to introduce i) clustering problems motivated by content management in online social networks, ii) related algorithms and iii) theoretical analyses of their performance.
A first part will focus on the identification of clusters of objects based on noisy signals, which could be ratings of objects provided by users. We will consider a particular generative probabilistic model for the observations, namely the so-called ``planted partition'' model. We will describe spectral transformations and associated clustering schemes for partitioning objects into distinct groups. Exploiting results on the spectrum of random graphs, we will establish consistency of these approaches under suitable assumptions. We will also discuss open questions on phase transitions for cluster detectability in such planted partition models.
A second part will consider optimization problems in which publishers are to choose which contents to publish in order to maximize the benefits to the users following them. This again gives rise to problems of clustering contents at publishers. These tasks are readily shown to be NP-hard. Nevertheless, they exhibit structure that can be exploited to develop polynomial-time algorithms achieving performance within a constant factor of the optimal. We will first develop such results by identifying submodularity properties of the optimization problem at hand. We will then describe another approach based on semi-definite programming and randomized rounding. In particular we will explain the approach used by Goemans and Williamson in their analysis of the ``MAXCUT'' problem. We will also introduce a recent approach of Alon and Naor and discuss its applicability to the problem at hand.