[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ősRé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 breakpoint 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 meanfield 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 highdimensional 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?
[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:
 JanMar, 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 31June 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 10July 17, 2013.
Y. Wen at Inria ParisRocquencourt. Partially funded by FQNRT's CARP.
 Aug 1024, 2013.
N. Broutin at McGill.
Work with L. AddarioBerry, and C. Goldschmidt (Funded by Royal Society)
on the nature of phase transitions in random graphs.
In particular continuum ErdősRényi dynamics.
Work with L. Devroye, and G. Lugosi on connectivity of random wireless networks.
 Aug 1314 and 22, 2013.
N. Broutin at Carleton (Ottawa): work with
V. Dujmovic, and P. Morin (trip funded by NSERC).
 Sep 26, 2013.
S. Langerman (UL Brussels, funded by PHC Tournesol). Work on random geometric hypergraph models for wireless networks.
 Nov 1113, 2013. Visit to ULB to work with S. Langerman on partitioning geometric coverings (Funded by PHC Tournesol).
 Nov 1823, 2013. Visit to McGill to work on the connectivity of wireless networks.
Year 2014:
 Jan 617, 2014. Visit to Eurandom, TU Eindhoven. Work on the theoretical aspects.
 Feb 35, 2014. Visit to the probability group of the University of Bath.
 Feb 1821, 2014. Visit of J.F. Marckert from LaBRI, Bordeaux. Lead to
a paper listed below.
 Mar 616, 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 2428, 2014. Visit of J.P. Vigneaux from Santiago. Work on random
geometric graphs. Paper in the process of being written.
 Apr 411, 2014. McGill Bellairs workshop on probabilistic combinatorics:
work with L. AddarioBerry, L. Devroye, R. Kang (Nimiegen, The Netherlands), G. Lugosi.
 Apr 1417, 2014. Workshop on New Frontiers in random geometric graphs.
Work with R. Kang. Lead to a paper listed below.
 May 1415, 2014. Visit to Nice, workshop on random graphs.
 May 1923, 2014. Workshop LOFAS, Palagrufel: joint work with S. Bubeck (Princeton),
L. Devroye, G. Lugosi on the practical aspects. Work in progress.
 June 1927. Visit of L. AddarioBerry and work on the theoretical aspects.
Year 2015:
 Feb 1620, 2015. Visit of J.F. Marckert from LaBRI, Bordeaux: work on directed percolation.
 Mar 2326, 2015. Leo Rolla in Paris: forest fire models and activated random walks.
 Mar 31Apr 2, 2015. Visit to McGill: work with L. Devroye and H. Sulzbach.
 Apr 310, 2015. McGill Bellairs Workshop on Probabilistic Combinatorics: work with
G. Lugosi, and C. Mailler.
 Jun 15, 2015. S. Janson is 60: work with L. AddarioBerry, C. Mailler, C. Goldschmidt,
and J.F. Marckert.
 Jun 2223, 2015. Visit to Einhoven: workshop at SoCG, and work with J. Bose, and G. Lugosi.
 Jul 2122, 2015. Visit to LaBRI: work on directed percolation.
 Aug 18Dec 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ősRé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ősRé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ősRényi random graph and the rank1
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ősRé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ősRé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 realvalued 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 breadthfirst (or depthfirst)
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. 812854, 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.
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_iX_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 integervalued
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 $no(n)$. This offers a natural noncentralized sparsification
of a random geometric graph that is mostly connected.
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.
[hal00940743]
[±]
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. AddarioBerry,
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 GromovHausdorffProkhorov 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ösRényi random
graph, and the explicit description of its scaling limit in the
socalled critical window.
Cutting down trees with a Markov chainsaw.
L. AddarioBerry, 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 GaltonWatson tree with critical, finitevariance offspring distribution, conditioned to have total progeny $n$. Our proof is based on a coupling which yields a precise, nonasymptotic distributional result for the case of uniformly random rooted labeled trees (or, equivalently, Poisson GaltonWatson trees conditioned on their size). Our approach also provides a new, random reversible transformation between Brownian excursion and Brownian bridge.
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. 22242270, 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 socalled contraction method in function spaces, we prove that, when properly rescaled, the planar dual of the discrete lamination converges almost surely in the GromovHausdorff sense to a limit real tree $\mathscr T$, which is encoded by $\mathscr M$. This confirms a conjecture of Curien and Le Gall.
A limit process for partial match queries in random quadtrees and 2d trees. N. Broutin,
R. Neininger,
and
H. Sulzbach.
The Annals of Applied Probability, vol. 23, pp. 25602603, 2013.
[arXiv:1202.1342]
[±]
We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees and kd 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.