### 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.

#### Dimensions of unimodular random discrete spaces

This work by F.Baccelli, M.-O. Haji-Mirsadeghi, and A. Khezeli, is focused on large scale properties of infinite graphs and discrete subsets of the Euclidean space. It presents two new notions of dimension, namely the unimodular Minkowski and Hausdorff dimensions, which are inspired by the classical Minkowski and Hausdorff dimensions. These dimensions are defined for unimodular discrete spaces, which are defined in this work as a class of random discrete metric spaces with a distinguished point called the origin. These spaces provide a common generalization to stationary point processes under their Palm version and unimodular random rooted graphs.

The main novelty is the use of unimodularity in the definitions where it suggests replacing the infinite sums pertaining to coverings by large balls by the expectation of certain random variables at the origin. In addition, the main manifestation of unimodularity, that is the mass transport principle, is the key element in the proofs and dimension evaluations.

These dimensions are connected to the growth rate of balls. In particular, versions of the mass distribution principle, Billingsley’s lemma, and Frostman’s lemma are established for unimodular discrete spaces.

The dimensions in question are explicitly evaluated or conjectured for a comprehensive set of examples pertaining to the theory of point processes, unimodular random graphs, and self-similarity.

On the Dimension of Unimodular Discrete Spaces, Part I: Definitions and Basic Properties

On the Dimension of Unimodular Discrete Spaces, Part II: Relations with Growth Rate

#### 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 and follow-up paper by Charles Radin and Harry Swinney. 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.