Networks

Training Week : Expansion properties and Random Walks

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

 

4Patel_VireshExpansion 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

lucaIn 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

https://www.schildkamp.nl/

 

Programme 

Monday 30 October

12:00 – 13:30

Lunch

13:30 – 14:30 

Session 1: presentations

14:30 – 14:40

Short break

14:40 – 15:40 

Session 2: presentations

15:40 – 16:00

Break

16:00 – 17:00

Open problem session

17:00 – 18:00

Research session: work in small groups

 

 

 

 

Tuesday 31 October

09:00 – 10:15

Mini-course on Expansion properties of networks: Viresh Patel

10:15 – 10:45

Break

10:45 – 12:00

Mini-course on Random walks, forests and network analysis: Luca Avena

12:00 – 13:30

Lunch

13:30 – 14:50 

Session 3: presentations

14:50 – 15:20

Break

15:20 – 18:00

Research session: work in small groups

 

 

 

 

Wednesday 1 November

09:00 – 10:15

Mini-course on Expansion properties of networks: Viresh Patel

10:15 – 10:45

Break

10:45 – 12:00

Mini-course on Random walks, forests and network analysis: Luca Avena

12:00 – 13:30

Lunch

13:30 – 14:30 

Research talks, Session 4: presentations

14:10 – 14:30

Break

14:30 – 16:30

Research session: work in small groups

16:30 –

Social event

 

 

Thursday 2 November

09:00 – 10:15

Mini-course on Expansion properties of networks: Viresh Patel

10:15 – 10:45

Break

10:45 – 12:00

Mini-course on Random walks, forests and network analysis: Luca Avena

12:00 – 13:30

Lunch

13:30 – 14:50 

Session 5: presentations

14:50 – 15:20

Break

15:20 – 18:00

Research session: work in small groups

 

 

 

 

Friday 3 November

09:00 – 10:00

Session 6: presentations

10:00 – 10:30

Break

10:30 – 12:00

Closing session

12:00 – 13:30

Lunch

Details
When: Monday October 30th, 2017  -  Friday November 3rd, 2017
Time: 12:00 - 13:30
Where: De Schildkamp, Asperen
Location

schildkamp

De Schildkamp
Leerdamseweg 44
4147 BM Asperen