This was part of Randomness in Topology and its Applications

Erdos-Renyi perturbed random geometric graphs

Yusu Wang, University of California, San Diego (UCSD)

Friday, March 24, 2023


Graphs and network data are ubiquitous across a wide spectrum of scientific and application domains. Often in practice, an input graph can be considered as an observed snapshot of a (potentially continuous) hidden domain or process. Subsequent analysis and inferences are then performed on this observed graph. In this talk, we will describe a natural network model: we assume that there is a true grpah wihch is a certain proximity graph for points sampled from a nice domain. Then the observed graph is an Erdos-Renyi (ER) type perturbed version of that true graph, where random edges can be inserted and deleted. We will describe two main results obtained: the first concerns the recovery of shortest path metric of the true graph from this ER-perturbed graph. The second concerns the behavior of the so-called clique number of the graph. This is joint work with M. Kahle, S. Parthasarathy, S. Sivakoff, and M. Tian.