Random Graphs


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


James Murphy

Read More »

Ali Khezeli

Department of Mathematics, Sharif University of Technology
Read More »

Lorenzo Sadun

Department of Mathematics, UT Austin
Read More »

Rachel Ward

Department of Mathematics, UT Austin
Read More »

Charles Radin

Department of Mathematics, UT Austin
512 471 0174
Read More »

Sujay Sanghavi

Department of Electrical and Computer Engineering, UT Austin
512 475 9798
Read More »

Sanjay Shakkottai

Department of Electrical and Computer Engineering, UT Austin
512 471 5376
Read More »

Joe Neeman

Department of Electrical and Computer Engineering and Department of Mathematics, UT Austin
Read More »

Mir Omid Haji Mirsadeghi 2013-2015

Department of Mathematics, Sharif University of Technology. Visiting Scholar, Department of Mathematics, UT Austin
Read More »

Ngoc Mai Tran

Department of Mathematics, UT Austin
Read More »

François Baccelli

Department of Mathematics and Deparment of Electrical and Computer Engineering, UT Austin
512 471 17 54
Read More »


2017_1000869 2016-08-21_1000762

Dynamics on Unimodular Random Graphs

François Baccelli, Mir-Omid Haji-Mirsadeghi, Ali Khezeli https://arxiv.org/abs/1608.05940
Download PDF

A symmetry breaking transition in the edge/triangle network model

Charles Radin, Kui Ren and Lorenzo Sadun Arxiv 2016
Download PDF

Point-Shift Foliation of a Point Process

Francois Baccelli and Mir-Omid Haji-Mirsadeghi ArXiv 2016
Download PDF

Bipodal structure in oversaturated random graphs

R. Kenyon, C. Radin, K. Ren and L. Sadun ArXiv 2015
Download PDF

Consistency thresholds for the planted bisection model

Elchanan Mossel, Joe Neeman and Allan Sly To appear in Symposium on the Theory of Computer Science 2015
Download PDF

Singularities in the Entropy of Asymptotically Large Simple Graphs

Charles Radin and Lorenzo Sadun J. Stat. Phys. 158 (2015) 853-865
Download PDF

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

Elchanan Mossel, Joe Neeman and Allan Sly Conference on Learning Theory 2014
Download PDF

The Asymptotics of Large Constrained Graphs

Charles Radin, Kui Ren and Lorenzo Sadun J. Phys. A: Math. Theor. 47 (2014) 175001
Download PDF

Multipodal Structure and Phase Transitions in Large Constrained Graphs

Richard Kenyon, Charles Radin, Kui Ren and Lorenzo Sadun ArXiv 2014
Download PDF

Community Detection on Euclidean Random Graphs

Abishek Sankararaman and François Baccelli ArXiv 2017
Download PDF