Stochastic Geometry and Point Processes

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.

Extremes of spatial shot noise processes

Anup Biswas and François Baccelli studied the scaling limit of a class of shot-noise fields defined on an independently marked stationary Poisson point process and with a power law response function. Under appropriate conditions, they showed that the shot-noise field can be scaled suitably to have a non degenerate alpha-stable limit, as the intensity of the underlying point process goes to infinity. More precisely, finite dimensional distributions  converge and the finite dimensional distributions of the limiting random field have i.i.d. stable random components. This limit is hence called the alpha- stable white noise field. Analogous results are also obtained for the extremal shot-noise field which converges to a Fréchet white noise field.

Information theory and high dimensional stochastic geometry

The most basic capacity and error exponent questions of information theory can be expressed in terms of random geometric objects living in Euclidean spaces with dimensions tending to infinity. This approach was introduced by Venkat Anantharam and François Baccelli to evaluate random coding error exponents in channels with additive stationary and ergodic noise. More generally, the analysis of stochastic geometry in the Shannon regime leads to new high dimension stochastic geometry questions that are currently investigated. Eliza O’Reilly and and Francois Baccelli have also studied determinantal point processes in high dimensions. This work describes the strength and reach of repulsion of a typical point of certain parametric families of determinantal point process in the Shannon regime.

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.

Point processes on topological groups

Using the framework of Günter Last, James Murphy has extended the cardinality classification to the case of point processes on unimodular groups. J. Murphy has studied point-shifts of point processes on topological groups at length.

Spatial birth and death processes

Spatial point processes involving birth and death dynamics are ubiquitous in networks. Such dynamics are particularly important in peer-to-peer networks and in wireless networks. In the paper “Mutual Service Processes in R^d, Existence and Ergodicity”, Fabien Mathieu (Bell Laboratories), Ilkka Norros (VTT) and François Baccelli proposed a way to analyze the long term behavior of such dynamics on Euclidean spaces using coupling techniques. This line of though is continued by Mayank Manjrekar on other classes of processes like hard core spatial birth and death processes.

Zeros of Random Tropical Polynomials

Ngoc Mai Tran and François Baccelli derived a tropical version of the result of Kac on the zeros of polynomials with random coefficients (Zeros of Random Tropical Polynomials, Random Polygons and Stick-Breaking). 

The common roots of tropical of a class of random polynomials in two variables is analyzed in a recent work by the same authors in Iterated Gilbert Mosaics and Poisson Tropical Plane Curves using a stochastic geometry approach based on iterated random tessellations.

Members

Chang-sik Choi

Department of Electrical and Computer Engineering, UT Austin
chang-sik.choi@utexas.edu
Read More »

James Murphy

Read More »

Natasa Dragovic

Department of Mathematics
ndragovic@math.utexas.edu
Read More »

Ali Khezeli

Department of Mathematics, Sharif University of Technology
alikhezeli@math.utexas.edu
Read More »

Charles Radin

Department of Mathematics, UT Austin
radin@math.utexas.edu
512 471 0174
Read More »

Eliza O’Reilly

Department of Mathematics, UT Austin
eoreilly@math.utexas.edu
Read More »

Mir Omid Haji Mirsadeghi 2013-2015

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

Mayank Manjrekar

Department of Mathematics, UT Austin
mmanjrekar@math.utexas.edu
Read More »

Gustavo de Veciana

Department of Electrical and Computer Engineering, UT Austin
gustavo@ece.utexas.edu
512 471 1573
Read More »

François Baccelli

Department of Mathematics and Deparment of Electrical and Computer Engineering, UT Austin
baccelli@math.utexas.edu
512 471 17 54
Read More »

Antonio Sodre

Department of Mathematics, UT Austin
asodre@math.utexas.edu
Read More »

Publications

2017-06-01_1000994

Spatial Birth Death Wireless Networks

Abishek Sankararaman and François Baccelli IEEE Transactions on Information Theory 63(6): 3964-3982 (2017)
Download PDF
2017-05-09_1000975 2016-05-20_1000948

Shape Theorems For Poisson Hail on a Bivariate Ground

Francois Baccelli, Hector A. Chang-Lara, and Sergey Foss ArXiv 2016
Download PDF
2016-01-14_1000623

Point-Shift Foliation of a Point Process

Francois Baccelli and Mir-Omid Haji-Mirsadeghi ArXiv 2016
Download PDF
2015-05-28_1000151

On Scaling Limits of Power Law Shot-noise Fields

François Baccelli and Anup Biswas To appear in Stochastic Models 2015
Download PDF
2014-08-06_1000286

The Boolean Model in the Shannon Regime: Three Thresholds and Related Asymptotics

Venkat Anantharam and François Baccelli Arxiv 2014 To appear in Advances in Applied Probability
Download PDF
2014-07-19_1000288

Compactification of the Action of a Point-Map on the Palm Probability of a Point Process

François Baccelli and Mir-Omid Haji-Mirsadeghi Arxiv 2014 To appear in the Annals of Probability
Download PDF
2014-04-08_1000146

Mutual Service Processes in R^d, Existence and Ergodicity

François Baccelli, Fabien Mathieu and Ilkka Norros ArXiv 2014
Download PDF
2000-01-01_1000992

Community Detection on Euclidean Random Graphs

Abishek Sankararaman and François Baccelli ArXiv 2017
Download PDF