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

Clique and near-clique counts are important graph properties withapplications in graph generation, graph modeling, graph analytics, communitydetection among others. They are the archetypal examples of dense subgraphs.While there are several different definitions of near-cliques, most of themshare the attribute that they are cliques that are missing a small number ofedges. Clique counting is itself considered a challenging problem. Countingnear-cliques is significantly harder more so since the search space fornear-cliques is orders of magnitude larger than that of cliques.  We give a formulation of a near-clique as a clique that is missing a constantnumber of edges. We exploit the fact that a near-clique contains a smallerclique, and use techniques for clique sampling to count near-cliques. Thismethod allows us to count near-cliques with 1 or 2 missing edges, in graphswith tens of millions of edges. To the best of our knowledge, there was noknown efficient method for this problem, and we obtain a 10x - 100x speedupover existing algorithms for counting near-cliques.  Our main technique is a space-efficient adaptation of the Tur\'an Shadowsampling approach, recently introduced by Jain and Seshadhri (WWW 2017). Thisapproach constructs a large recursion tree (called the Tur\'an Shadow) thatrepresents cliques in a graph. We design a novel algorithm that builds anestimator for near-cliques, using an online, compact construction of theTur\'an Shadow.

Provably and Efficiently Approximating Near-cliques using the Tur\'an Shadow: PEANUTS