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

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 monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Mining dense subgraphs is an important primitive across a spectrum ofgraph-mining tasks. In this work, we formally establish that two recurringcharacteristics of real-world graphs, namely heavy-tailed degree distributionsand large clustering coefficients, imply the existence of substantially largevertex neighborhoods with high edge-density. This observation suggests a verysimple approach for extracting large quasi-cliques: simply scan the vertexneighborhoods, compute the clustering coefficient of each vertex, and outputthe best such subgraph. The implementation of such a method requires countingthe triangles in a graph, which is a well-studied problem in graph mining. Whenempirically tested across a number of real-world graphs, this approach revealsa surprise: vertex neighborhoods include maximal cliques of non-trivial sizes,and the density of the best neighborhood often compares favorably to subgraphsproduced by dedicated algorithms for maximizing subgraph density. For graphswith small clustering coefficients, we demonstrate that small vertexneighborhoods can be refined using a local-search method to ``grow'' largercliques and near-cliques. Our results indicate that contrary to worst-casetheoretical results, mining cliques and quasi-cliques of non-trivial sizes fromreal-world graphs is often not a difficult problem, and provides motivation forfurther work geared towards a better explanation of these empirical successes.

Mining Large Quasi-cliques with Quality Guarantees from Vertex Neighborhoods