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/

Zendy Plus

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

Zendy Tools

Zendy Open

Clique counts reveal important properties about the structure of massivegraphs, especially social networks. The simple setting of just 3-cliques(triangles) has received much attention from the research community. For largercliques (even, say 6-cliques) the problem quickly becomes intractable becauseof combinatorial explosion. Most methods used for triangle counting do notscale for large cliques, and existing algorithms require massive parallelism tobe feasible.  We present a new randomized algorithm that provably approximates the numberof k-cliques, for any constant k. The key insight is the use of (strengtheningsof) the classic Tur\'an's theorem: this claims that if the edge density of agraph is sufficiently high, the k-clique density must be non-trivial. We definea combinatorial structure called a Tur\'an shadow, the construction of whichleads to fast algorithms for clique counting.  We design a practical heuristic, called TUR\'AN-SHADOW, based on thistheoretical algorithm, and test it on a large class of test graphs. In allcases,TUR\'AN-SHADOW has less than 2% error, in a fraction of the time used bywell-tuned exact algorithms. We do detailed comparisons with a range of othersampling algorithms, and find that TUR\'AN-SHADOW is generally much faster andmore accurate. For example, TUR\'AN-SHADOW estimates all cliques numbers up tosize 10 in social network with over a hundred million edges. This is done inless than three hours on a single commodity machine.

A Fast and Provable Method for Estimating Clique Counts Using Tur\'an's Theorem