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

Mining cohesive subgraphs from a graph is a fundamental problem in graph dataanalysis. One notable cohesive structure is $\gamma$-quasi-clique (QC), whereeach vertex connects at least a fraction $\gamma$ of the other vertices inside.Enumerating maximal $\gamma$-quasi-cliques (MQCs) of a graph has been widelystudied. One common practice of finding all MQCs is to (1) find a set of QCscontaining all MQCs and then (2) filter out non-maximal QCs. While quite a fewalgorithms have been developed (which are branch-and-bound algorithms) forfinding a set of QCs that contains all MQCs, all focus on sharpening thepruning techniques and devote little effort to improving the branching part. Asa result, they provide no guarantee on pruning branches and all have theworst-case time complexity of $O^*(2^n)$, where $O^*$ suppresses thepolynomials and $n$ is the number of vertices in the graph. In this paper, wefocus on the problem of finding a set of QCs containing all MQCs but deviatefrom further sharpening the pruning techniques as existing methods do. We payattention to both the pruning and branching parts and develop new pruningtechniques and branching methods that would suit each other better towardspruning more branches both theoretically and practically. Specifically, wedevelop a new branch-and-bound algorithm called FastQC based on newly developedpruning techniques and branching methods, which improves the worst-case timecomplexity to $O^*(\alpha_k^n)$, where $\alpha_k$ is a positive real numberstrictly smaller than 2. Furthermore, we develop a divide-and-conquer strategyfor boosting the performance of FastQC. Finally, we conduct extensiveexperiments on both real and synthetic datasets, and the results show that ouralgorithms are up to two orders of magnitude faster than the state-of-the-arton real datasets.

Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach