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

#### Data driven discovery of sparse dynamics

Rachel Ward and collaborator Giang Tran (former Bing Instructor in the UT Mathematics department) are investigating the identification of a dynamical system (say, within the class of polynomial systems of ordinary differential equations) given snapshots of the system in time. Such problems prove challenging when there is a high level of noise on the data. In the paper Exact recovery of Chaotic systems from highly corrupted data, they show that if the underlying trajectory exhibits ergodicy or chaos, and if the underlying dynamics have a sparse representation with respect to the polynomial basis, then a LASSO / l1 type algorithm will exactly recover the underlying dynamics even when most of the data is highly corrupted. This establishes a new link between the areas of dynamical systems and machine learning / sparse recovery, and many interesting questions remain.

#### Detecting planted communities in random graphs

The stochastic block model (aka. planted partition model) is a popular model for representing networks with communities. Elchanan Mossel, Joe Neeman, and Allan Sly have been investigating algorithms and fundamental limits for detecting and recovering these communities. They established sharp transitions for the problem of extracting non-trivial information and the problem of exactly recovering communities. They also gave a new algorithm that obtains provably optimal accuracy for the problem of detecting communities in “Consistency thresholds for the planted bisection model” and “Belief propagation, robust reconstruction, and optimal recovery of block models“.

#### On the steady state of continuous time stochastic opinion dynamics

François Baccelli, Sriram Vishwanath and Jae Oh Woo proposed a computational framework for continuous time opinion dynamics with additive noise. They derived a non-local partial differential equation for the distribution of opinions differences. They used Mellin transforms to solve the stationary solution of this equation in closed form. This approach can be applied both to linear dynamics on an interaction graph and to bounded confidence dynamics in the Euclidean space. To the best of our knowledge, the closed form expression on the stationary distribution of the bounded confidence model is the first quantitative result on the equilibria of this class of models.

#### Stochastic opinion dynamics in social networks

Avhishek Chatterjee, François Baccelli and Sriram Vishwanath proposed a stochastic extension of the bounded confidence model where opinions take their values in the Euclidean space and where friendship and interactions are dynamically defined through time varying and random neighborhoods. Two basic sub-models are defined: the influencing model where each agent is an attractor to the opinions of its neighbors and the listening model where each agent gathers information from others to update its own opinions. The general model contains a rich set of variants for which they proposed a classification. They analyzed the stability of its dynamics. The analysis highlights the need of certain leaders with heavy tailed neighborhoods for stability to hold. See Pairwise Stochastic Bounded Confidence Opinion Dynamics: Heavy Tails and Stability