On 17 - 21 April 2023 NETWORKS organizes the 15th Training Week in De Schildkamp in Asperen.
The topics of this Training Week are a minicourse on random walks on networks and one on semidefinite programming for network problems. Nelly Litvak (UT and TU/e) and Etienne de Klerk (UvT) are the lecturers of the minicourses.
Next to the minicourses new NETWORKS members will introduce themselves and various Networks members will give talks about their recent results during a research presentation or open problem session. There will also be time for joint research in small groups (either in existing collaborations or in new collaborations) in so-called working sessions. On Wednesday afternoon there will be a social event.
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.
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:
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.
Conferentiecentrum De Schildkamp, Leerdamseweg 44, 4147 BM Asperen.