Training week 15

Random walks on networks

Mini course by Nelly Litvak (UT and TU/e)

 

A random walk on a network is a stochastic process that moves from one network node to another. One can see this as a process of randomly exploring the network and its neighbourhoods. Despite the randomness, such exploration is very useful and has many applications. This minicourse will address two applications of random walks in the analysis of networks: clustering and ranking.  

 

In the context of network science, by clustering we mean identifying communities of nodes that have much more connections to each other than to the rest of the network.  Random walks tend to spend long time before exiting such communities, and this is how communities can be identified. In a broader sense, clustering is a typical machine learning task that means grouping similar objects together. Remarkably, seminal recent work made random walks relevant for this task as well. Specifically, random walks DeepWalk and node2vec are routinely used to embed network vertices in high-dimensional spaces so that the nodes can be clustered by their position. We will discuss how these algorithms work, as well as recent attempts at their analysis.

 

Ranking is a task of sorting network nodes in the order of their importance, based on their position in the network graph. While the first works on ranking in social networks appeared already in late 1940s, massive attention to this problem was triggered by application of random-walk based PageRank algorithm by Google in 1998. We will discuss the definition and basic properties of PageRank, algorithms for its computation, and the asymptotic distribution of PageRank when the network size goes to infinity. In the latter topic we will use the concept of local weak convergence -- the current state-of-the art notion of convergence for sparse graphs.

 

Semidefinite programming for Network Problems

Mini course by Etienne de Klerk (UvT)

 

Semidefinite programming (SDP) is a class of convex optimization problems that may be solved in polynomial time to fixed precision. It may best be described as conic linear optimization with positive semidefinite matrix variables. Due to the tractability of SDP, it has been used extensively in designing approximation algorithms for NP-hard combinatorial problems. In this minicourse we will look at some of this work, including:

• SDP approximation of the quadratic assignment problem;
• SDP approximation of the crossing number problem in graphs;
• Exploiting algebraic (often group) symmetry to reduce the size of the SDP problem.

The minicourse will be mostly self-contained, but a basic background in linear optimization, elementary graph theory, and approximation algorithms would be helpful. The minicourse will include an open problem session, with problems that could potentially be interesting for participants interested in algorithmics as well as stochastics.

 

Location

Conferentiecentrum De Schildkamp, Leerdamseweg 44, 4147 BM Asperen.