Ohio State is in the process of revising websites and program materials to accurately reflect compliance with the law. While this work occurs, language referencing protected class status or other activities prohibited by Ohio Senate Bill 1 may still appear in some places. However, all programs and activities are being administered in compliance with federal and state law.

Topology, Geometry and Data Seminar - Minghao Tian

Topology, Geometry and Data Seminar
November 6, 2018
4:10 pm - 5:10 pm
Cockins Hall 240

Title: Local cliques in ER-perturbed random geometric graphs

Speaker: Minghao Tian (Ohio State University, CSE)

Abstract: Random graphs are mathematical models that have applications in a wide range of domains. Among them, the Erdös--Rényi and the random geometric graphs are two models whose theoretical properties (e.g., clique number and the largest component) are perhaps most well studied. We are interested in mixed models coming from the overlay of two graph structures. In particular, we study the following model where one adds Erdös--Rényi (ER) type perturbation to a random geometric graph. More precisely, assume $G_\mathcal{X}^{*}$ is a random geometric graph sampled from a nice measure on a metric space $\mathcal{X} = (X,d)$. The input observed graph $\widehat{G}(p,q)$ is generated by removing each existing edge from $G_\mathcal{X}^*$ with probability $p$, while inserting each non-existent edge to $G_\mathcal{X}^{*}$ with probability $q$. We refer to such random $p$-deletion and $q$-insertion as ER-perturbation. Although these graphs are related to the objects in the continuum percolation theory, our understanding of them is still rather limited.

We consider a localized version of the classical notion of clique number for the aforementioned ER-perturbed random geometric graphs: Specifically, we study the \emph{edge clique number} for each edge in a graph, defined as the size of the largest clique(s) in the graph containing that edge. The clique number of the graph is simply the largest edge clique number. Interestingly, given a ER-perturbed random geometric graph, we show that the edge clique number presents two fundamentally different types of behaviors, depending on which ``type'' of randomness it is generated from.

As an application of the above results, we show that by using a filtering process based on the edge clique number, we can recover the shortest-path metric of the random geometric graph $G_\mathcal{X}^*$ within a multiplicative factor of $3$, from an ER-perturbed observed graph $\widehat{G}(p,q)$, for a significantly wider range of insertion probability $q$ than in previous work.

This is joint work with Matthew Kahle and Yusu Wang.

Events Filters: