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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We consider the problem of recovering a planted partition (e.g., a small bisection or a large cut) from a random graph. During the last 30 years many algorithms for this problem have been developed that work provably well on models resembling the Erd˝ os-Renyi modelGn;m. Since in these random graph models edges are distributed very uniformly, the recent theory of large networks provides convincing evidence that real-world networks, albeit looking random in some sense, cannot sensibly be described by these models. Therefore, a variety of new types of random graphs have been introduced. One of the most popular of these new models is characterized by a prescribed expected degree sequence. We study a natural variant of this model that features a planted partition, the main re- sult being that there is a polynomial time algorithm for recovering (a large share of) the planted partition efficiently. In contrast to prior work, the algorithm's in- put only consists of the graph, i.e., no further parameters of the distribution (such as the expected degree sequence) are required.

Partitioning Random Graphs with General Degree Distributions