April 14-15-16, 2015

Random Walks on Random Graphs and Applications

Discrete random walks and related processes.

Analysis on random graph models,

and algorithmic applications to large networks

SUMMARY

The workshop focuses on:

1) The analysis of discrete random processes on random graph models. In particular: random walks, voting, information dissemination by randomized broadcasting, bootstrap percolation and interacting particle systems. Also of interest are self-modifying random networks and algorithmic aspects thereof.

2) The practical application of these methods to the algorithmic aspects of networks, such as organization of, and search and ranking in large networks.

ORGANISERS

INVITED SPEAKERS

PROGRAMME 

Tuesday April 14

Wednesday April 15

Thursday April 16

*****************************************************************************************************************************************

ABSTRACTS

Omer Angel

Random walks on unimodular planar networks

We study random hyperbolic planar graphs by using their circle packing embedding to connect their geometry to that of the hyperbolic plane. This leads to several results: Identification of the Poisson and
geometric boundaries, a connection between hyperbolicity and a form of non-amenability, and a new proof of the Benjamini-Schramm recurrence result.
(joint work with subsets of Martin Barlow, Ori Gurel-Gurevich, Tom Hutchcroft, Asaf Nachmias and Gourab Ray)

Konstantin Avratchenkov

Extremes and Random Walks in Network Sampling Processes

We consider random walk based algorithms to sample the nodes in social networks and study extremal properties in any associated stationary sequence of characteristics of interest like node degrees, number of followers or income of the nodes. Several useful extremes of the sampled sequence like k-th largest value, clusters of exceedances over a threshold, first hitting time of a large value etc. are analysed. We investigate the dependence structure in the sampled sequence. We abstract the dependence of extremes into a single parameter that appears in Extreme Value Theory, called Extremal Index. Under two mixing conditions, we derive the value of this parameter analytically and also estimate it
empirically for several sampling methods. In particular, we study various sampling processes on configuration type random graph model with degree-degree dependence.
(joint work with N. Markovich (RAS ICS) and J. Sreedharan (Inria))

Petra Berenbrink

The Moran Process

The Moran process was suggested by Lieberman, Hauert and Nowak (Nature, 433:312--316, 2005). Each node of a finite, connected (directed or undirected) graph models one individual. It is assumed that the initial population consists of a single mutant of fitness r>0 placed uniformly at random, with every other vertex occupied by an individual of fitness 1. At each time step, an individual (node) is chosen at random with probability proportional to its assigned ``fitness'' value. It reproduces by placing a copy of itself on a neighbouring node that is chosen uniformly at random, replacing the individual that was there. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction), and the time that it takes to reach fixation or extinction. In this talk I will give an overview over results bounding the fixation and extinction probabilities, as well as results analysing the convergence time.

Jiří Černý

Macroscopic phase transition for the vacant set of random walk on a large torus

It was conjectured that the vacant set of random walk on (some) finite graphs exhibits a phase transition similar to the Erdös-Rényi random graph. Up to now, this conjecture was proved only on the graphs that are "locally tree-like". The most interesting graph, the large d-dimensional discrete torus, remains open. In the talk, I will present the recent work with A. Teixeira (IMPA) proving the phase transition for certain specific observables in this case, and explain the soft-local times coupling technique that is the main ingredient of the proof.

Moez Draief

Viral Processes by Random Walks on Random Regular Graphs

We study the SIR epidemic model with infections carried by \(k\) particles making independent random walks on a random regular graph. We give an edge-weighted graph reduction of the dynamics of the process that allows us to apply standard results of Erdos-Renyi random graphs on the particle set. In particular, we show how the parameters of the model produce the following phase transitions: In the subcritical regime, \(O(ln k)\) particles are infected. In the supercritical regime, for a constant \(c \in (0,1)\) determined by the parameters of the model, \(c.\) \(k\) get infected with probability \(c\), and \(O(ln k)\) get infected with probability \((1-c)\). Finally, there is a regime in which all \(k\) particles are infected. Furthermore, the edge weights give information about when a particle becomes infected. We demonstrate how this can be exploited to determine the completion time of the process by applying a results on first-passage percolation.
(joint work with M. Abdullah and C. Cooper)

Martin Dyer

Random regular graphs and peer-to-peer networks

Random regular graphs have been proposed as a topology for peer-to-peer networks. A useful property for such networks is to be “self-organising”, in the sense that they retain their properties as clients join and leave the network. We will discuss Markov chain approaches to the construction and maintenance of these networks.

Robert Elsaesser

Randomized broadcasting - general results and recent advances

Information dissemination is a fundamental problem in parallel and distributed computing. In its simplest variant, known as the broadcasting problem, a message has to be spread among all nodes of a graph. A prominent communication protocol for this problem is the so-called random phone call model (Karp et al., FOCS 2000). In each step, every node opens a communication channel to a randomly chosen neighbor, which can then be used for bi-directional communication. It is known that in a complete graph, the broadcasting problem can be solved in time O(log n) by using O(log log n) message transmissions per node. Unfortunately, this performance cannot be achieved in sparse graphs even with best expansion and connectivity properties. We will present some simple modifications of the standard model, which allow us to significantly improve on the efficiency of randomized broadcasting in a number of sparse graphs.

Dick Epema

Exploiting random walks in decentralized reputation systems

In the BitTorrent-based peer-to-peer file-sharing system Tribler developed at Delft University of Technology, we have designed and implemented the BarterCast reputation system, which is based the contributions of the peers. Using a gossiping protocol, every peer builds its own local view of the system, which is a directed graph with peers as nodes and data transfers as edges. Peers compute the reputations of other peers by means of random walks in their local views that are either unbiased, or biased with local or global properties. In this talk the whole reputation mechanism will be explained and performance results of
BarterCast, and of the application of the same types of random walks to citation graphs and a Facebook graph, will be presented. In addition, a random walk-based information dissemination protocol that replaces the gossiping protocol, and its resilience to sybil attacks, will be discussed.
(based on the PhD research of Dimitra Gkorou, who obtained her PhD degree in November 2014)

Nikolaos Fountoulakis

Bootstrap percolation and the geometry of complex networks

We consider a geometric framework for complex networks that was proposed recently by Krioukov et al.
This model is in fact a geometrization of the well-known Chung-Lu model, which is a type of inhomogeneous random graphs with kernel of rank 1.  The model of Krioukov et al. is a special case of random geometric graphs on the hyperbolic plane and in fact the underlying hyperbolic geometry turns out to be the source of typical features that appear in complex networks such as power law degree distribution and clustering.
In this talk, we consider the evolution of the classical bootstrap percolation process on this class of random graphs that have N vertices and the tail of the degree distribution follows a power law with exponent between 2 and 3.
Assuming that p=p(N) is the initial infection rate, in each round of the process a vertex that is not infected but has at least r infected neighbors becomes infected and stays so forever.  We identify a critical function p_c (N) = o(1) such that with high probability if p >> p_c (N), the infection spreads to a positive fraction of the vertices, whereas if p << p_c(N) the process does not evolve. Furthermore, we show that this behavior is ``robust" under random deletions of the edges.  Our proofs also imply that the giant component of these random graphs is robust under random deletions and so is their r-core.
(joint work with Elisabetta Candellero from the University of Warwick.)

Alan Frieze

Random Walks on Random Graphs: Covertime; Vacant Sets and Vacant Nets

We survey some results on the title topics.
(joint work with Colin Cooper)

Catherine Greenhill

The switch Markov chain for sampling irregular graphs

The problem of efficiently sampling from a set of (undirected) graphs with a given degree sequence has many applications. One approach to this problem uses a simple Markov chain, which we call the switch chain, to perform the sampling. The switch chain is known to be rapidly mixing for regular degree sequences. We prove that the switch chain is rapidly mixing for any degree sequence with minimum degree at least 1 and with maximum degree \(d_{\max}\) which satisfies \(3\leq d_{\max}\leq \frac{1}{4}\sqrt{M}\), where \(M\) is the sum of the degrees. The mixing time bound obtained is only an order of \(n\) larger than that established in the regular case, where \(n\) is the number of vertices.

Karen Gunderson

Bootstrap percolation with recovery on the grid

Bootstrap processes are a type of cellular automaton in which vertices of a graph are in one of two states: ‘healthy’ or ‘infected’ and from an initial configuration of states, healthy vertices become infected by local rules. While the usual bootstrap processes are monotone in the sets of infected vertices, in this talk, I shall describe a model in which infected vertices can return to a healthy state.  I will present a process on a square grid in which healthy vertices with at least two infected neighbours become infected and simultaneously any infected vertices with zero infected neighbours become healthy.  These updates are repeated and the central question is whether all vertices eventually become infected and stay infected, in which case percolation is said to occur.  I will give some background and describe sharp thresholds for the critical probability for percolation when vertices are initially infected independently at random.

Johannes Lengler

Bootstrap Percolation with Inhibition

The Peach Company has a new fantastic innovation (SmartSocks) and releases it to the market. To get a start, the company gives SmartSocks to a small random set of people. A third of the people love it, while two thirds hate it. Of course, the people who love it recommend to buy it to everyone they meet (they meet their friends at random time intervals), while those who hate it warn everyone they see. In general, people are not so quick to buy new stuff, but if they get at least two more recommendations than warnings then they buy it. Then they also either love or hate SmartSocks (1/3 vs. 2/3) and start with recommendations or warnings. How many people will eventually buy Smart Socks? This seems like a ludicrous question as the answer must clearly depend on the structure of the social network. But in fact, it does not. Rather, under some mild assumptions exactly 25%+o(1) of all people will eventually buy SmartSocks.

Nelly Litvak

Ranking algorithms on directed configuration networks

We study the distribution of a family of rankings, which includes Google's PageRank, on a directed configuration model (DCM).  Our main result is that the rank of a randomly chosen node in the graph converges in distribution to a finite random variable that can be written as a linear combination of i.i.d. copies of the endogenous solution to a stochastic fixed point equation. For the first time in the literature, this result establishes a limiting behavior for a complete PageRank distribution. This provides a very accurate approximation for the PageRank distribution on the DCM but also on a complete English Wikipedia graph. The essence of the proof is in coupling of the DCM with a specially constructed tree. To obtain the main result, we show that the ranking in the graph converges with any given precision before the coupling breaks.
(joint work with Mariana Olvera-Cravioto  and Ningyuan Chen)

Ryuhei Mori

Analysis of the peeling algorithm on random hypergraph

When we try to solve a system of linear equations, we can consider a simple iterative algorithm in which an equation including only one variable is chosen at each step, and the variable is fixed to the value satisfying the equation.  The dynamics of this algorithm is captured by the peeling algorithm.  Analyses of the peeling algorithm on random hypergraphs are required for many problems, e.g., the decoding threshold of low-density parity check codes, the inverting threshold of Goldreich's pseudorandom generator, the load threshold of cuckoo hashing, etc.  On the other hand, the peeling algorithm gives natural generalization of the concepts of connectivity and connected components for hypergraphs.  In this work, we deal with random hypergraphs including polynomially many hyperedges, and derive the tight threshold for the succeeding of the peeling algorithm.  For the analysis, Wormald's method of differential equations, which is commonly used for analyses of the peeling algorithm, cannot be used due to the polynomially many hyperedges.A new method called the evolution of the generating function is used in this work.
(joint work with Osamu Watanabe (Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology))

Tobias Muller

A hyperbolic model for complex networks

In this talk, I will discuss a model for complex networks that was introduced recently by Krioukov et al. In this model, N points are chosen randomly on the hyperbolic plane and any two of them are joined by an edge if they are within a certain hyperbolic distance. The model turns out to have characteristics usually associated with complex networks. In particular, it exhibits a power-law degree sequence, small distances and clustering. I will present some results on the component structure of the graph model, and on the probability that it is connected.
(joint work with Michel Bode and Nikolaos Fountoulakis)

James Norris

Robust non-concentration for hitting times of Markov chains

Uniform estimates for a class of random processes are of value when the underlying model is random or in some way unknown. I will describe some upper bounds for `surprise probabilities' for finite state-space Markov chains. By a `surprise probability' we mean the probability that, after t steps, the chain arrives at a given state y for the first time, or simply at some state never seen before. These estimates depend on the size of the state-space and on qualitative properties of the chain, such as reversibility, or being the random walk on a simple graph, but are otherwise uniform.
(joint work with Yuval Peres (Microsoft Research) and Alex Zhai (Stanford University))

Alexandre Stauffer

Random walks on dynamic graphs given by dynamical percolation

We study the behavior of random walk on dynamical percolation. In this model, the edges of a graph \( G\) are either open or closed, and refresh their status at rate \(\mu\). At the same time a random walker moves on \(G\) at rate 1 but only along edges which are open.  The regime of interest here is when \(\mu\) goes to zero as the number of vertices of \(G\) goes to infinity, since this creates long-range dependencies on the model. When G is the \(d\)-dimensional torus of side length \(n\), we prove that in the subcritical regime, the mixing times is of order \(n^2/\mu\). We also obtain results concerning mean squared displacement and hitting times. 
(joint work with Yuval Peres and Jeff Steif)

He Sun

Heat kernel in graphs

Heat kernel is one of the most fundamental concepts in physics and mathematics. In physics, heat kernel is a fundamental solution of the heat equation and, through heat kernel, the Laplacian is associated with the rate of dissipation of heat. In spectral geometry, many of the most basic techniques involve heat kernels. In finite Markov chain theory, heat kernel corresponds to continuous-time random walks and becomes one of the most powerful techniques in estimating mixing time, etc.
In this talk, we will discuss this line of research, and their relations to the heat kernel in graphs. In particular, we will see how heat kernel is used in designing nearly-linear time algorithms for finding clusters in real networks. Some interesting open questions will be addressed as well.

Andrew Wade

Hypercycles in sparse random hypergraphs

Let $M$ be a random $m$ by $n$ matrix with 0, 1 entries and i.i.d. rows, which follow a specified distribution on their weight (number of ones). We study the number of left null vectors of $M$ with addition mod 2, as $n$ tends to infinity and $m/n$ tends to a given aspect ratio $\alpha$, while the weight distribution converges weakly to a limit distribution. We describe the asymptotics of the expected number of null vectors in terms of analytic properties of the limiting weight distribution. This random matrix model has other interpretations, including a random hypergraph model (where null vectors correspond to hypercycles), randomized XORSAT, and random walk on a generalized hypercube. Most of the existing literature considers the case where the limiting weight distribution is degenerate, i.e., constant.
(joint work with Richard Darling, Mathew Penrose, and Sandy Zabell)

PRACTICAL INFORMATION

●      Venue

Eurandom, Mathematics and Computer Science Dept, TU Eindhoven,

Den Dolech 2, 5612 AZ  EINDHOVEN,  The Netherlands

Eurandom is located on the campus of Eindhoven University of Technology, in the Metaforum building (4th floor) (about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).
Accessibility TU/e campus and map.

 

 

●      Registration

Registration is free, but compulsory for speakers and participants. Please follow the link: REGISTRATION PAGE

 

 

●      Accommodation

For invited participants, we will take care of accommodation. Other attendees will have to make their own arrangements.

We have a preferred hotel, which can be booked at special rates. Please email Patty Koorn for instructions on how to make use of this special offer.

For other hotels around the university, please see: Hotels (please note: prices listed are "best available"). 

More hotel options can be found on the webpages of the Tourist Information Eindhoven, Postbus 7, 5600 AA Eindhoven.

 

●      Travel

For those arriving by plane, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information, please consult the NS travel information pages or see Eurandom web page location.

Many low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult http://www.9292ov.nl

The University  can be reached easily by car from the highways leading to Eindhoven (for details, see our route descriptions or consult our map with highway connections.

 

●      Conference facilities : Conference room, Metaforum Building  MF11&12

The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants making an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.

 

●      Conference Secretariat

Upon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.

 

●      Cancellation

Should you need to cancel your participation, please contact Patty Koorn, the Workshop Officer.

There is no registration fee, but should you need to cancel your participation after January 2, 2014, we will be obliged to charge a no-show fee of 30 euro.

 

●      Contact

Mrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl

 

SPONSORS

The organisers acknowledge the financial support/sponsorship of:

 

 

---

 

 

        

        

Last updated 03-04-15,
by PK

 P.O. Box 513, 5600 MB Eindhoven, The Netherlands
tel. +31 40 2478100  
  e-mail: info@eurandom.tue.nl