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

For many random graph models, the analysis of a related birth processsuggests local sampling algorithms for the size of, e.g., the giant connectedcomponent, the $k$-core, the size and probability of an epidemic outbreak, etc.In this paper, we study the question of when these algorithms are robustagainst misspecification of the graph model, for the special case of the2-core. We show that, for locally converging graphs with bounded averagedegrees, under a weak notion of expansion, a local sampling algorithm providesrobust estimates for the size of both the 2-core and its largest component. Ourweak notion of expansion generalizes the classical definition of expansion,while holding for many well-studied random graph models.  Our method involves a two-step sprinkling argument. In the first step, we usesprinkling to establish the existence of a non-empty $2$-core inside the giant,while in the second, we use this non-empty $2$-core as seed for a secondsprinkling argument to establish that the giant contains a linear sized$2$-core. The second step is based on a novel coloring scheme for the verticesin the tree-part. Our algorithmic results follow from the structural propertiesfor the $2$-core established in the course of our sprinkling arguments.  The run-time of our local algorithm is constant independent of the graphsize, with the value of the constant depending on the desired asymptoticaccuracy $\epsilon$. But given the existential nature of local limits, ourarguments do not give any bound on the functional dependence of this constanton $\epsilon$, nor do they give a bound on how large the graph has to be forthe asymptotic additive error bound $\epsilon$ to hold.

Locality via Global Ties: Stability of the 2-Core Against Misspecification