Models of sparse graphs and network algorithms (12w5004)

Arriving in Banff, Alberta Sunday, February 5 and departing Friday February 10, 2012


(Inria Paris-Rocquencourt)

(McGill University)

(ICREA & Pompeu Fabra University)


There is no doubt now that the current trend that every electronic device should be connected in one way or another (usually many) implies a greater need for efficient networks. These networks should be connected, exhibit small-world behaviour and their topology should be robust to local modifications like device movement; all this should be achieved using minimal (devices might not be powerful) and distributed processes.

The topic we propose lies at the intersection of computer science, computational geometry, operations research, and theoretical probability; it also raises both exciting mathematical problems and hits on very practical aspects of today's technological challenges. One of the main objectives of the meeting is to gather experts from the different communities involved, give them the opportunity to expose their points of view, and foster fruitful exchanges. We also want to use this forum to make a state-of-the-art on the subject quickly available to a broader audience, in particular graduate students.

We will organise the workshop mostly around scientific presentations, but we will also organise discussions and schedule some time for group work sessions. We think that the workshop would be an invaluable opportunity to discuss the following more precise mathematical questions. The presence of experts in different fields will certainly lead to interesting confrontations of ideas and raise related questions whose answer could shed more light on the subject.

A. The models of sparse geometric networks have so far mainly been studied using very little knowledge of the mathematical percolation corpus. In most cases, the graphs of interest are two-dimensional, which allows for the use of the specific techniques developed and used by Kesten [1980] in his proof that the critical threshold for bond percolation on the square lattice is $frac 12$. There is no doubt that a more thorough use of these powerful geometrical techniques will be of great help in understanding the precise connectivity parameters of various models of random geometric graphs.

B. The spanning ratio of a network is the maximal ratio over all pairs of points of the graph distance over the shortest (geometric, Euclidean) distance. It is a rather difficult parameter to study ---indeed, virtually no theoretically precise results are known about it for standard graphs (such as the Delaunay triangulation, or minimal spanning tree, or random geometric graph). For recent work, se the survey by Aldous and Shun [2010].

C. A first step towards more general results about broadcasting algorithms consists in characterizing the time for rumour spreading in terms of an important parameter of the connectivity of the graph that would be computed for specific examples. The first result in this direction is due to Chierichetti et a. [2010] who provide almost tight bounds for the broacast time using a push--pull strategy in terms of the graph conductance. We will discuss ways to nail down the correct asymptotics and dicuss what other important graph invariant might be more suitable to express the asymptotic bounds in a useful way.

D. One of the more challenging questions concerns the universality of the behaviour of graph models. Rather than analyzing the models one by one, one would gain a lot of insight by adopting a more abstract point of view. The main obstacle here is to define a suitable measure of similarity between graphs. The question of metrics on the space of graphs and continuity of the parameters in the induced topology is crucial here. The question has been very successfully answered for dense graphs with the notion of graph limits by Lovasz and Szegedy [2006] (See also, Diaconis and Janson [2008]). For sparse graphs, the question is more subtle and many natural metrics (like the Gromov--Hausdorff metric) do not yield good topologies on the spaces of sparse graph that are not ``critical'' (only supercritical (branching) graphs are crucial in practice for their expansion properties.) The recent survey by Bollobas and Riordan [2009] provides possible approaches. The question of convergence of geometric networks is also the main theme of Aldous' talk at the ICM [Aldous, 2010].