## Random Graphs

### Topics

#### Community Detection on Euclidean Random Graphs

In this paper, Abishek Sankararaman and François Baccelli introduce the problem of Community Detection on a new class of sparse spatial random graphs embedded in the Euclidean space. They consider the planted partition version of the random connection model graph studied in classical stochastic geometry. The nodes of the graph form a marked Poisson Point Process of intensity \lambda with each node being equipped with an i.i.d. uniform mark drawn from {-1,+1}. Conditional on the labels, edges are drawn independently at random depending both on the Euclidean distance between the nodes and the community labels on the nodes. The paper studies the Community Detection problem on this random graph which consists in estimating the partition of nodes into communities, based on an observation of the random graph along with the spatial location labels on nodes. For all dimensions greater than or equal to 2, they establish a phase transition in the intensity of the point process. They show that if the intensity is small, then no algorithm for Community Detection can beat a random guess. This is proven by introducing and analyzing a new problem called ‘Information Flow from Infinity’. On the positive side, they give an efficient algorithm to perform Community Detection as long as the intensity is sufficiently high. Along the way, a distinguishability result is established, which says that one can always infer the presence of a partition, even when one cannot identify the partition better than at random. This is a surprising new phenomenon not observed thus far in any non spatial Erdos-Renyi based planted partition models.

#### Order parameters of dense phases

Dense phases of emergent systems, such as constrained complex networks,
exhibit distinct characteristics, the most studied being broken symmetry.
However for practical purposes “rigidity”, the resistance to change, is
also of wide interest. There are difficulties analyzing rigidity since
when perturbed a system can easily move out of its phase. A new approach to
overcome this contradiction has been initiated by David Aristoff and
Charles Radin: see the discussion in Quanta Magazine. Another characteristic
of dense phases are their nonspherical `Wulff’ shapes, polyhedral for ordinary crystals.
This is examined in this expository paper by Charles Radin, and in a related direction in this paper by Charles Radin, Kui Ren, and Lorenzo Sadun.

In a different direction, the process of nucleation is a dynamical signature of the creation of a dense phase, which can appear even in systems far removed from ordinary atomic materials, as shown in this paper by Frank Rietz, Charles Radin, Harry Swinney and Matthias Schroeter. All the above characteristics make essential use of finite systems, a nonstandard approach to understanding emergent phases.

#### Phases and phase transitions in complex networks

In the phenomenon of emergence, a system of many interacting objects
exhibits the collective behavior of one or more “phases”, which are
only detectable or even meaningful for the system as a whole. This is
an organizing principle widely used in biology, physics and indeed all
the sciences: crystals, hurricanes, animal flocking etc. One wants to
understand the spontaneous appearance of phases in systems of large
size, in particular to determine a mechanism of some generality. A
convenient framework for such an analysis is large networks with
constraints. Such an analysis has been undertaken by the group of
Richard Kenyon, Charles Radin, Kui Ren and Lorenzo Sadun, on entropy singularities, the edge/triangle system I, the edge/triangle system II, multipodal structure,
order-disorder transitions and oversaturated networks. There is also a related asymptotic analysis of large permutations undertaken by the group of Richard Kenyon, Daniel Kral, Charles Radin and Peter Winkler: permutations with fixed pattern densities, and a review of phases in general combinatorial systems.

#### Point maps on point processes

A compatible point-shift f maps, in a translation invariant way, each point of a stationary point process N to some point of N. It is fully determined by its associated point-map, g, which gives the image of the origin by f. The initial question studied by Mir-Omid Haji-Mirsadeghi and François Baccelli is whether there exist probability measures which are left invariant by the translation of -g. The point map probabilities of N are defined from the action of the semigroup of point-map translations on the space of Palm probabilities, and more precisely from the compactification of the orbits of this semigroup action. If the point-map probability is uniquely defined, and if it satisfies certain continuity properties, it then provides a solution to the initial question. Point-map probabilities are shown to be a strict generalization of Palm probabilities: when the considered point-shift f is bijective, the point-map probability of N boils down to the Palm probability of N. When it is not bijective, there exist cases where the point-map probability of N is absolutely continuous with respect to its Palm probability, but there also exist cases where it is singular with respect to the latter.

Each such point-shift defines a random graph on the points of the point process. The connected components of this graph can be split into a collection of foils, which are the analogue of the stable manifold of the point-shift dynamics.
The same authors give a general classification of point-shifts in terms of the cardinality of the foils of these connected components. There are three types: F/F, I/F and I/I as shown in the paper Point-Shift Foliation of a Point Process.

#### Vertex Shifts on Random Graphs

Ali Khezeli, Mir-Omid Haji-Mirsadeghi and François Baccelli studied dynamics on the vertices of a random graph in the paper Dynamics on Unimodular Graphs. The first result of the paper is a classification of vertex-shifts on unimodular random networks. Each such vertex-shift partitions the vertices into a collection of connected components and foils, as in the case of point-shifts on point processes.
The classification is based on the cardinality of the connected components and foils. Up to an event of zero probability, there are three types of foliations in a connected component: F/F (with finitely many finite foils), I/F (infinitely many finite foils), and I/I (infinitely many infinite foils).
An infinite connected component of the graph of a vertex-shift on a random network forms an infinite directed tree with one selected end which is referred to as an Eternal Family Tree. An Eternal Family Tree contains a subtree which is a stochastic generalization of a branching process. In a unimodular Eternal Family Tree, the subtree in question is a generalization of a critical branching process. In a $\sigma$-invariant Eternal Family Tree, the subtree is a generalizisation of a non-necessarily critical branching process. The latter trees allow one to analyze dynamics on networks which are not necessarily unimodular.

### Publications

2017_1000869

#### Associative content-addressable networks with exponentially many robust stable states.

##### R. Chaudhuri and I.R. Fiete arXiv:1704.02019
2016-08-21_1000762

#### Dynamics on Unimodular Random Graphs

##### François Baccelli, Mir-Omid Haji-Mirsadeghi, Ali Khezelihttps://arxiv.org/abs/1608.05940
2016-04-27_1000640

#### A symmetry breaking transition in the edge/triangle network model

2016-01-14_1000623

#### Point-Shift Foliation of a Point Process

##### Francois Baccelli and Mir-Omid Haji-MirsadeghiArXiv 2016
2015-09-18_1000522

#### Bipodal structure in oversaturated random graphs

2015-06-16_1000329

#### Consistency thresholds for the planted bisection model

##### Elchanan Mossel, Joe Neeman and Allan SlyTo appear in Symposium on the Theory of Computer Science 2015
2015-03-01_1000218

#### Singularities in the Entropy of Asymptotically Large Simple Graphs

2014-06-18_1000333

#### Belief propagation, robust reconstruction, and optimal recovery of block models

##### Elchanan Mossel, Joe Neeman and Allan SlyConference on Learning Theory2014
2014-04-13_1000212