{"ID":3083857,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T07:39:45.869976485Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.05809","arxiv_id":"2606.05809","title":"Detecting Large Quasi-cliques on Dynamic Networks","abstract":"Motivated by the problem of detecting large and cohesive groups of vertices in real networks, the task of finding large \\emph{quasi-cliques} has attracted considerable attention across different research areas. From a computational complexity perspective, strong inapproximability results are known for this problem, yet several heuristics have been proposed to identify large quasi-cliques in real-world networks. Recently, [Pang \\emph{et al.}, (WWW 2024)] introduced a similarity-based approach that represents the current state of the art. In this work, we extend that approach to \\emph{dynamic} networks, thereby addressing an open problem posed by [Pang \\emph{et al.}, (WWW 2024)]. We first present a Baseline fully dynamic algorithm where edges of the network can be both inserted and deleted. The algorithm exactly maintains the same quasi-clique returned by the algorithm by Pang et al. on the current graph, with update time $\\widetilde{O}(Δ)$, where $Δ$ is the maximum degree. We then focus on the practically relevant incremental case, where only edge insertions are allowed, and design an algorithm with $O(\\log Δ)$ update time. This method leverages a novel technique for dynamically maintaining accurate estimates of vertex $γ$-degrees, a core component of framework by Pang et al., and achieves up to $207\\times$ speed-up over the Baseline while preserving comparable solution quality. Finally, we extend the approach to the fully dynamic setting, supporting both insertions and deletions, obtaining up to $21\\times$ speed-up with limited and acceptable loss in quasi-clique size and density. We provide a formal analysis of our algorithms and validate them through an extensive set of experiments on real-world datasets.","short_abstract":"Motivated by the problem of detecting large and cohesive groups of vertices in real networks, the task of finding large \\emph{quasi-cliques} has attracted considerable attention across different research areas. From a computational complexity perspective, strong inapproximability results are known for this problem, yet...","url_abs":"https://arxiv.org/abs/2606.05809","url_pdf":"https://arxiv.org/pdf/2606.05809v1","authors":"[\"Luciano Gualà\",\"Simone Pellegrini\",\"Luca Pepè Sciarria\",\"Alessandro Straziota\"]","published":"2026-06-04T07:39:52Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}