English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Random graphs are mathematical models that have applications in a wide range of domains. We study the following model where one adds ErdH{o}s--Ru0027enyixspace (ER)  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. In this paper we consider a localized version of the classical notion of clique number for the aforementioned emph{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.

Local cliques in ER-perturbed random geometric graphs.