[Description of the project]

The project consists of two complementary facets on foundational and applied aspects of connectivity in random networks.


The connectivity of usual models for networks based on random graphs models (Erdős-Rényi and random geometric graphs) may be tuned by adjusting the average degree. There is a phase transition as the average degree approaches one, a giant connected component containing a positive proportion of the nodes suddenly appears. The phase of practical interest is the supercritical one, when there is at least a giant component, while the theoretical interest lies at the critical phase, the break-point just before it appears.

A. The nature of the phase transition. The critical phase is more easily studied by putting aside many issues resorting to the dependence resulting from the underlying geometry, and we consider mean-field models. At the critical point there is not yet a macroscopic component and the network consists of a large number of connected component at the mesoscopic scale. From a theoretical point of view, this phase is most interesting since the structure of the clusters there is expected (heuristically) to be universal. Understanding this phase and its universality is a great challenge that would impact the knowledge of phase transitions in all high-dimensional models of statistical physics and combinatorial optimization.

B. Geometric graphs for wireless networks. For the applications the underlying geometry is crucial, in particular, in the context of wireless networks: we consider random geometric graphs and related models. The level of connection of the network is of course crucial, but the scalability imposes that the underlying graph also be sparse: trade offs must be made, which required a fine evaluation of the costs/benefits. Various direct and indirect measures of connectivity are crucial to these choices: What is the size of the overwhelming connected component? When does complete connectivity occur? What is the order of magnitude of distances? Are paths to a target easy to find using only local information? Are there simple broadcasting algorithms? Can one put an end to viral infections? How much time for a random crawler to see most of the network?

[Members]
The project is jointly funded by Inria thanks to the Associate Team program, and Quebec's FQRNT team grant CARP.

RAP - Inria Paris-Rocquencourt
CARP - McGill University
Associate members (with external funding)
[Meetings and Visits]
The funding provided by Inria but also by the partner team via FQRNT has made possible to organize the following research visits and workshops.

Year 2013:
  • Jan--Mar, 2013. Juan Pablo Vigneaux visited and worked on bootstrap percolation in random geometric graphs. He will be coming back next year to finalize a publication.
  • May 31--June 6, 2013. Satellite meeting of AofA 2013. S. Boucheron (Paris 7), N. Broutin, L. Devroye, T. Linder (Queens, Canada) G. Lugosi (Pompeu Fabra, Spain), L. Gyorfi (Budapest). Efficient and distributed design of wireless networks.
  • June 10--July 17, 2013. Y. Wen at Inria Paris-Rocquencourt. Partially funded by FQNRT's CARP.
  • Aug 10--24, 2013. N. Broutin at McGill. Work with L. Addario-Berry, and C. Goldschmidt (Funded by Royal Society) on the nature of phase transitions in random graphs. In particular continuum Erdős-Rényi dynamics. Work with L. Devroye, and G. Lugosi on connectivity of random wireless networks.
  • Aug 13-14 and 22, 2013. N. Broutin at Carleton (Ottawa): work with V. Dujmovic, and P. Morin (trip funded by NSERC).
  • Sep 2--6, 2013. S. Langerman (UL Brussels, funded by PHC Tournesol). Work on random geometric hypergraph models for wireless networks.
  • Nov 11--13, 2013. Visit to ULB to work with S. Langerman on partitioning geometric coverings (Funded by PHC Tournesol).
  • Nov 18--23, 2013. Visit to McGill to work on the connectivity of wireless networks.

Year 2014:
  • Jan 6--17, 2014. Visit to Eurandom, TU Eindhoven. Work on the theoretical aspects.
  • Feb 3--5, 2014. Visit to the probability group of the University of Bath.
  • Feb 18--21, 2014. Visit of J.-F. Marckert from LaBRI, Bordeaux. Lead to a paper listed below.
  • Mar 6--16, 2014. Visit of S. Bhamidi from University of North Carolina. Work on universality of the scaling limit of random graph models at criticality. Lead to a paper listed below.
  • Mar 24--28, 2014. Visit of J.P. Vigneaux from Santiago. Work on random geometric graphs. Paper in the process of being written.
  • Apr 4--11, 2014. McGill Bellairs workshop on probabilistic combinatorics: work with L. Addario-Berry, L. Devroye, R. Kang (Nimiegen, The Netherlands), G. Lugosi.
  • Apr 14--17, 2014. Workshop on New Frontiers in random geometric graphs. Work with R. Kang. Lead to a paper listed below.
  • May 14--15, 2014. Visit to Nice, workshop on random graphs.
  • May 19--23, 2014. Workshop LOFAS, Palagrufel: joint work with S. Bubeck (Princeton), L. Devroye, G. Lugosi on the practical aspects. Work in progress.
  • June 19--27. Visit of L. Addario-Berry and work on the theoretical aspects.

Year 2015:
  • Feb 16-20, 2015. Visit of J.-F. Marckert from LaBRI, Bordeaux: work on directed percolation.
  • Mar 23-26, 2015. Leo Rolla in Paris: forest fire models and activated random walks.
  • Mar 31-Apr 2, 2015. Visit to McGill: work with L. Devroye and H. Sulzbach.
  • Apr 3-10, 2015. McGill Bellairs Workshop on Probabilistic Combinatorics: work with G. Lugosi, and C. Mailler.
  • Jun 1-5, 2015. S. Janson is 60: work with L. Addario-Berry, C. Mailler, C. Goldschmidt, and J.F. Marckert.
  • Jun 22-23, 2015. Visit to Einhoven: workshop at SoCG, and work with J. Bose, and G. Lugosi.
  • Jul 21-22, 2015. Visit to LaBRI: work on directed percolation.
  • Aug 18-Dec 21, 2015. Fall at NYU Shanghai.
[Publications and Manuscripts]
Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erdős-Rényi random graph. S. Bhamidi, N. Broutin, S. Sen, and X. Wang. Submitted (99 p.), 2014. [arXiv:1411.3417] [±]

Over the last few years a wide array of random graph models have been postulated to understand properties of empirically observed networks. Most of these models come with a parameter $t$ (usually related to edge density) and a (model dependent) critical time tc which specifies when a giant component emerges. There is evidence to support that for a wide class of models, under moment conditions, the nature of this emergence is universal and looks like the classical Erdős--Rényi random graph, in the sense of the critical scaling window and (a) the sizes of the components in this window (all maximal component sizes scaling like $n^{2/3}$) and (b) the structure of components (rescaled by $n^{−1/3}$) converge to random fractals related to the continuum random tree. Till date, (a) has been proven for a number of models using different techniques while (b) has been proven for only two models, the classical Erdős-Rényi random graph and the rank-1 inhomogeneous random graph. The aim of this paper is to develop a general program for proving such results. The program requires three main ingredients: (i) in the critical scaling window, components merge approximately like the multiplicative coalescent (ii) scaling exponents of susceptibility functions are the same as the Erdős-Rényi random graph and (iii) macroscopic averaging of expected distances between random points in the same component in the barely subcritical regime. We show that these apply to a number of fundamental ran- dom graph models including the configuration model, inhomogeneous random graphs modulated via a finite kernel and bounded size rules. Thus these models all belong to the domain of attraction of the classical Erdős-Rényi random graph. As a by product we also get results for component sizes at criticality for a general class of inhomogeneous random graphs.

A new encoding of combinatorial coalescent processes. Applications to the additive and multiplicative cases N. Broutin and J.-F. Marckert. Submitted (29 p.), 2014. [arXiv:1409.4266] [±]

We revisit the discrete additive and multiplicative coalescents, starting with $n$ particles with unit mass. These cases are known to be related to some ``combinatorial coalescent processes'': a time reversal of a fragmentation of Cayley trees or a parking scheme in the additive case, and the random graph process $(G(n,p), p\in [0,1])$ in the multiplicative case. Time being fixed, encoding these combinatorial objects in real-valued processes indexed by the line is the key to describing the asymptotic behaviour of the masses as $n\to +\infty$. We propose to use the Prim order on the vertices instead of the classical breadth-first (or depth-first) traversal to encode the combinatorial coalescent processes. In the additive case, this yields interesting connections between the different representations of the process. In the multiplicative case, it allows one to answer to a stronger version of an open question of Aldous [Ann. Probab., vol. 25, pp. 812--854, 1997]: we prove that not only the sequence of (rescaled) masses, seen as a process indexed by the time $\lambda$, converges in distribution to the reordered sequence of lengths of the excursions above the current minimum of a Brownian motion with parabolic drift $(B_t+\lambda t - t^2/2, t\geq 0)$, but we also construct a version of the standard augmented multiplicative coalescent of Bhamidi, Budhiraja and Wang [Probab. Theory Rel., to appear] using an additional Poisson point process.

pdf
Almost optimal sparsification of random geometric graphs. N. Broutin, L. Devroye, and G. Lugosi. Submitted (26 pages), 2014. [arXiv:1403.1274] [±]

A random geometric irrigation graph $\Gamma_n(r_n,\xi)$ has $n$ vertices identified by $n$ independent uniformly distributed points $X_1,\ldots,X_n$ in the unit square $[0,1]^2$. Each point $X_i$ selects $\xi_i$ neighbors at random, without replacement, among those points $X_j$ ($j\neq i$) for which $\|X_i-X_j\| \le r_n$, and the selected vertices are connected to $X_i$ by an edge. The number $\xi_i$ of the neighbors is an integer-valued random variable, chosen independently with identical distribution for each $X_i$ such that $\xi_i$ satisfies $1\le \xi_i \le \kappa$ for a constant $\kappa>1$. We prove that when $r_n = \gamma_n \sqrt{\log n/n}$ for $\gamma_n \to \infty$ with $\gamma_n =o(n^{1/6}/\log^{5/6}n)$, then the random geometric irrigation graph experiences \emph{explosive percolation} in the sense that when $\mathbf E \xi_i=1$, then the largest connected component has size $o(n)$ but if $\mathbf E \xi_i >1$, then the size of the largest connected component is with high probability $n-o(n)$. This offers a natural non-centralized sparsification of a random geometric graph that is mostly connected.

pdf
Connectivity of sparse Bluetooth networks. N. Broutin, L. Devroye, and G. Lugosi. Submitted (12 pages), 2014. [arXiv:1402.3696] [±]

Consider a random geometric graph defined on $n$ vertices uniformly distributed in the $d$-dimensional unit torus. Two vertices are connected if their distance is less than a ``visibility radius'' $r_n$. We consider Bluetooth networks that are locally sparsified random geometric graphs. Each vertex selects $c$ of its neighbors in the random geometric graph at random and connects only to the selected points. We show that if the visibility radius is at least of the order of $n^{-(1-\delta)/d}$ for some $\delta > 0$, then a constant value of $c$ is sufficient for the graph to be connected, with high probability. It suffices to take $c \ge \sqrt{(1+\epsilon)/\delta} + K$ for any positive $\epsilon$ where $K$ is a constant depending on $d$ only. On the other hand, with $c\le \sqrt{(1-\epsilon)/\delta}$, the graph is disconnected with high probability.

Efficiently navigating a random Delaunay triangulation. N. Broutin, O. Devillers, and R. Hemsley. Submitted (46 p), 2014. [hal-00940743] [±]

Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. However, whilst a number of algorithms and existence proofs have been proposed, very little analysis is available for the properties of the paths generated and the computational resources required to generate them under a random distribution hypothesis for the input. In this paper we analyse a new deterministic planar navigation algorithm with constant competitiveness which follows vertex adjacencies in the Delaunay triangulation. We call this strategy cone walk. We prove that given $n$ uniform points in a smooth convex domain of unit area, and for any start point $z$ and query point $q$; cone walk applied to $z$ and $q$ will access at most $O(|zq|\sqrt{n} +\log^7 n)$ sites with complexity $O(|zq|\sqrt{n} \log \log n + \log^7 n)$ with probability tending to 1 as $n$ goes to infinity. We additionally show that in this model, cone walk is $(\log ^{3+\xi} n)$-memoryless with high probability for any pair of start and query point in the domain, for any positive $\xi$. We take special care throughout to ensure our bounds are valid even when the query points are arbitrarily close to the border.

The scaling limit of the minimum spanning tree of a complete graph. L. Addario-Berry, N. Broutin, C. Goldschmidt, and G. Miermont. Submitted (60 p), 2013. [±]

Consider the minimum spanning tree of the complete graph with $n$ vertices, when edges are assigned independent random weights. We show that, when this tree is endowed with the graph distance renormalized by $n^{1/3}$ and with the uniform measure on its vertices, the resulting space converges in distribution as $n\to\infty$ to a random limiting metric space in the Gromov--Hausdorff--Prokhorov topology. We show that this space is a random binary $\mathbb R$-tree and has Minkowski dimension $3$ almost surely. In particular, its law is mutually singular with that of the Brownian continuum random tree or any rescaled version thereof. Our approach relies on a coupling between the minimum spanning tree problem and the Erdös--Rényi random graph, and the explicit description of its scaling limit in the so-called critical window.

pdf
Cutting down trees with a Markov chainsaw. L. Addario-Berry, N. Broutin and C. Holmgren. The Annals of Applied Probability, to appear (32 p), 2013. [arXiv:1110.6455] [±]

We provide simplified proofs for the asymptotic distribution of the number of cuts required to cut down a Galton--Watson tree with critical, finite-variance offspring distribution, conditioned to have total progeny $n$. Our proof is based on a coupling which yields a precise, non-asymptotic distributional result for the case of uniformly random rooted labeled trees (or, equivalently, Poisson Galton--Watson trees conditioned on their size). Our approach also provides a new, random reversible transformation between Brownian excursion and Brownian bridge.

pdf
The dual tree of a recursive triangulation of the disk. N. Broutin and H. Sulzbach. The Annals of Probability, to appear (31 p), 2013. [arXiv:1211.1343] [±]

In the recursive lamination of the disk, one tries to add chords one after another at random; a chord is kept and inserted if it does not intersect any of the previously inserted ones. Curien and Le Gall [Ann. Probab., vol. 39, pp. 2224--2270, 2011] have proved that the set of chords converges to a limit triangulation of the disk encoded by a continuous process $\mathscr M$. Based on a new approach resembling ideas from the so-called contraction method in function spaces, we prove that, when properly rescaled, the planar dual of the discrete lamination converges almost surely in the Gromov--Hausdorff sense to a limit real tree $\mathscr T$, which is encoded by $\mathscr M$. This confirms a conjecture of Curien and Le Gall.

pdf
A limit process for partial match queries in random quadtrees and 2-d trees. N. Broutin, R. Neininger, and H. Sulzbach. The Annals of Applied Probability, vol. 23, pp. 2560--2603, 2013. [arXiv:1202.1342] [±]

We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees and k-d trees). We assume the classical model where the data consist of independent and uniform points in the unit square. For this model, in a structure on $n$ points, it is known that the complexity, measured as the number of nodes $C_n(\xi)$ to visit in order to report the items matching a random query $\xi$, independent and uniformly distributed on $[0,1]$, satisfies $\mathbf E[C_n(\xi)]\sim \kappa n^{\beta}$, where $\kappa$ and $\beta$ are explicit constants. We develop an approach based on the analysis of the cost $C_n(s)$ of any fixed query $s\in [0,1]$, and give precise estimates for the variance and limit distribution. Moreover, a functional limit law for a rescaled version of the process $(C_n(s))_{0\le s\le 1}$ is derived in the space of cadlag functions with the Skorokhod topology. For the worst case complexity $\max_{s\in [0,1]} C_n(s)$ the order of the expectation as well as a limit law are given.

The random connection model on the torus. L. Devroye N. Fraiman. Combinatorics, Probability and Computing, to appear (9 pages), 2013.
Connectivity threshold of inhomogeneous random graphs. L. Devroye N. Fraiman. Random Structures and Algorithms, to appear (13 pages), 2013.
Trees, graphs and recursive partitions. N. Broutin, Habilitation, Université Paris 6, 2013.