Networks
Training
Training Week 5
On 30 October– 3 November 2017 NETWORKS organizes the fifthTraining Week for PhD Students of NETWORKS. The topics of this Training Week are a minicourse on Expansion properties of networks and one on Random walks, forests and network analysis. Viresh Patel and Luca Avena are the main lecturers in the morning during this Training Week.
In the afternoon various Networks PhD students and other Networks researchers will give talks about their recent results. There will also be time for joint research in small groups (either in existing collaborations or in new collaborations) in so-called working sessions.
Expansion properties of networks
Lecturer Viresh Patel
Expansion is a measure of how well connected a graph or network is. There are different closely-related notions of expansion depending on whether one takes a geometric, algebraic or probabilistic perspective. One way of defining expansion is the following: the expansion of an n-vertex graph is the smallest number c such that for every subset S of vertices with |S| \leq n/2, one must delete at least c|S| edges in order to disconnect S from the rest of the graph. The idea of expansion appears in different areas of mathematics and computer science with several applications, e.g. to construction of error correcting codes and to derandomisation of algorithms. The aim of the minicourse will be to give a basic understanding of various notions of expansion and how they are related to each other as well as some of their applications.
A good source of material for the course in the following survey:
http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
Random walks, forests and network analysis
Lecturer: Luca Avena
In this mini-course I will present part of my recent research work on random spanning forests on arbitrary given networks (graphs).
The main emphasis will be given on new applications in networks analysis and related randomized algorithms.
In particular, I plan to discuss in some details 1) a probabilistic notion of well distributed points in a network 2) a network reduction procedure 3) and an algorithm in the spirit of wavelets to process graph signals (i.e. functions defined on networks). If time allows, I'll also touch some further potential applications in clustering problems.
The main object of investigation will be a certain probability measure on spanning rooted forests of a graph. This measure is a variant of the so-called ``uniform spanning tree measure'' and it is intimately related with the graph Laplacian and with lots of random combinatorial models of current research interest in statistical mechanics (e.g. loop-erased walks, integrable systems, dimer models, sandpiles, Gaussian free fields, percolation, determinantal and coalescence-fragmentation processes). Although in the introductory lecture I'll try to highlight this more fundamental line of investigation, for the rest of the lectures I plan to discuss concrete applications and open problems at the interface of probability theory and computer science. As prerequisites, I will only assume familiarity with basic notions on Markov chains.
Most of the course will be based on material from the following references:
1) Avena and Gaudillière: https://arxiv.org/abs/1310.1723 (2013)
2) Avena and Gaudillière: J. Theor. Probab (2017). https://doi.org/10.1007/s10959-017-0771-3
3) Avena, Castell, Mélot and Gaudillière: https://arxiv.org/abs/1707.04616 (2017)
4) Avena, Castell, Mélot and Gaudillière: https://arxiv.org/abs/1702.05992 (2017)
Further, for those interested in understanding deeper connections with statistical mechanics models, here is a good starting reference: A. Jarai, lecture notes: ``The uniform spanning tee and related models'', 2009. Avialable at: http://www.maths.bath.ac.uk/~aj276/teaching/USF/USFnotes.pdf
Location
De Schildkamp, Leerdamseweg 44, 4147 BM Asperen
Programme
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||