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 

Download in pdf

 

Monday

October 30, 2017

12:00 – 12:30

Arrival

12:30 – 13:30

Lunch

13:30 – 14:30 

Session 1: Optimization and control of network traffic

  • Jaap Storm: Analysis of a roundabout model
  • Abishek: A novel approach to analyze unsignalized intersections: How to incorporate driver behavior and heterogeneous traffic
  • Liron Ravner: A strategic model of job arrivals to a single machine with earliness and tardiness penalties

14:30 – 14:40

Short break

14:40 – 15:40 

Session 2: Network structure

  • Alessandro Garavaglia: Results and open problems on citation networks
  • Debankur Mukherjee: Phase transitions of extremal cuts for random graphs
  • Margriet Oomen: Spatial populations on hierarchical graphs with seed-bank

15:40 – 16:00

Break

16:00 – 17:00

Open problem session

17:00 – 18:00

Research session: work in small groups

18:30

Dinner

 

 

Tuesday

October 31, 2017

07:30 – 09:00

Breakfast

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: (Geometric) Graph Algorithms

  • Jesper Nederlof: Using graph decompositions algorithmically via matrix rank
  • Astrid Pieterse: Optimal data reduction for graph coloring using low-degree polynomials
  • Bart Jansen: TBA
  • Mark de Berg: Geodesic spanners for points on a polyhedral terrain

14:50 – 15:20

Break

15:20 – 18:00

Research session: work in small groups

18:30

Dinner

 

 

Wednesday

November 1, 2017

07:30 – 09:00

Breakfast

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:10 

Session 4: Dynamics on random graphs

  • Jan Nagel: Random walks in barely supercritical random environments
  • Hakan Guldas: Mixing times for random walks on dynamic random graphs
  • Pieter Kleer: Shapley cost-sharing in clustering games on (random) graphs

14:10 – 14:30

Break

14:30 – 16:30

Research session: work in small groups

16:30 – 21:00

Social activity and dinner

 

 

Thursday

November 2, 2017

07:30 – 09:00

Breakfast

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: Queueing and more

  • Matteo Sfragara: Transition time asymptotics  of queue-based activation protocols in random-access networks
  • Nicos Starreveld: A network of M/M/infty queues with connection failures
  • Fiona Sloothaak: Cascading failures on a connected configuration model

14:50 – 15:20

Break

15:20 – 18:00

Research session: work in small groups

18:30

Dinner

 

Friday

November 3, 2017

07:30 – 09:00

Breakfast

09:00 – 10:00

Session 6: Decision making and performance analysis

  • Stella Kapodistria: Decision making in a Bayesian framework
  • Madelon de Kemp: Appointment scheduling
  • Murtuza Ali Abidini: Performance analysis of optical networks

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