Engineering Algorithms for ℓ \ell -Isolated Maximal Clique Enumeration

Marco D’Elia, Irene Finocchi, Maurizio Patrignani · 2025

Read Engineering Algorithms for ℓ \ell -Isolated Maximal Clique Enumeration by Marco D’Elia, Irene Finocchi, Maurizio Patrignani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-03525.txt.

Introduction

Marco D'Elia, Irene Finocchi, and Maurizio Patrignani engineer faster ways to list well-isolated tight groups in large graphs. Maximal cliques, sets where everyone links to everyone else, explode in number even in sparse real networks. Isolated cliques, whose members link only lightly outward, are fewer and often more useful.

Building on a classic recursive enumerator, the team adds four pruning rules that cut search branches sure to fail the isolation test. Rules can run singly or stacked, and proofs confirm none discard a valid clique. Tuning the isolation dial filters out cliques tangled with the rest of the graph. Faster listing makes clique analysis practical for community and fraud hunting in big networks.

Catalog record

CREATORMarco D’Elia, Irene Finocchi, Maurizio Patrignani
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-03525

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Engineering Algorithms for ℓ \ell -Isolated Maximal Clique Enumeration Marco D’Elia, Irene Finocchi, Maurizio Patrignani Abstract Maximal cliques play a fundamental role in numerous application domains, where their enumeration can prove extremely useful. Yet their sheer number, even in sparse real-world graphs, can make them impractical to be exploited effectively. To address this issue, one approach is to enumerate ℓ \ell -isolated maximal cliques, whose vertices have (on average) less than ℓ \ell edges toward the rest of the graph. By tuning parameter ℓ \ell , the degree of isolation can be controlled, and cliques that are overly connected to the outside are filtered out. Building on Tomita et al. ’s very practical recursive algorithm for maximal clique enumeration, we propose four pruning heuristics, applicable individually or in combination, that discard recursive search branches that are guaranteed not to yield ℓ \ell -isolated maximal cliques. Besides proving correctness, we characterize both the pruning power and the computational cost of these heuristics, and we conduct an extensive experimental study comparing our methods with Tomita’s baseline and with a state-of-the-art approach. Results show that two of our heuristics offer substantial efficiency improvements, especially on real-world graphs with social network properties. Roma Tre University, Rome, [email protected]://orcid.org/0009-0008-6266-3324 Luiss Guido Carli, Rome, Italy [email protected]://0000-0002-6394-6798 Roma Tre University, Rome, [email protected]://orcid.org/0000-0001-9806-7411 We thank Robert Bredereck and Manuel Sorge for providing the code used in [ 13 ] . We thank Tommaso Caiazzi and Simone Romanelli for interesting conversations. keywords Maximal cliques, isolated cliques, enumeration algorithms, clique summarization, algorithm engineering ccs Theory of computation Design and analysis of algorithms ccs Mathematics of computing Graph algorithms ccs Mathematics of computing Graph theory † † runningauthor: M. D’Elia et al. † † runningtitle: Engineering Algorithms for \ell -Isolated Maximal Clique Enumeration † † funding: This research was supported in part by MUR PRIN Projects EXPAND and NextGRAAL [grant numbers 2022TS4Y3N and 2022ME9Z78]. 1 Introduction Cliques capture dense, highly-connected network structures. Their enumeration is important in many application domains, such as Web mining, bioinformatics, computational chemistry, social and financial network analysis. In particular, enumerating maximal cliques — those that cannot be extended by another vertex — helps reveal the graph’s structure by uncovering tightly connected groups of vertices that share meaningful relationships. From both theoretical and practical perspectives, the problem presents significant challenges. The set of maximal cliques includes indeed also maximum cliques, but computing a maximum clique is a well-known \mathsf{NP} -hard problem [ 16 ] , as well as \mathsf{W} [1]-hard [ 7 , 6 ] , and hard to approximate within a factor of n^{1-\epsilon} [ 12 , 29 ] . In general, the number of maximal cliques in an n -vertex graph can be exponential in n [ 20 ] . Hence, not only their enumeration requires considerable time, but navigating such a large number of structures is also difficult. Imposing additional constraints may pinpoint a subset of domain-relevant structures, substantially reduce the number of enumerated cliques, and enable more effective utilization. We refer to [ 8 ] for a taxonomic survey of different summarization approaches. In contexts where cliques with weak connections to the rest of the graph are more meaningful than those strongly intertwined with it, the concept of \ell -isolation may prove particularly useful. First introduced in [ 14 , 15 ] , \ell -isolation requires that the number of edges leaving a clique of size k does not exceed \ell\cdot k . In the same works, the authors proposed an \mathsf{FPT} algorithm in the isolation factor \ell to enumerate all \ell -isolated maximal cliques. It was also shown that \ell must be constant to achieve linear-time enumeration, since otherwise one can construct instances admitting a superlinear number of \ell -isolated maximal cliques. In [ 17 ] , two additional isolation principles were introduced, namely max- and min-isolation. A systematic comparison of different isolation notions, complemented by an experimental evaluation on synthetic and financial networks, was presented in [ 13 ] , underscoring the importance of isolated clique enumeration for network analysis. Isolation concepts have been also explored in temporal networks [ 19 , 11 ] , and applied to practical scenarios such as web structure mining [ 27 ] , hierarchical representations of scale-free networks [ 22 ] , and network contraction via isolated cliques [ 25 ] . Alternative isolation models have also been proposed, including \tau -isolation based on coreness [ 21 ] , as well as variants for stars [ 26 ] , bicliques [ 1 ] , and even approaches inspired by quantum algorithms [ 10 ] . Our contribution. In this paper, building upon the well-known Bron-Kerbosch algorithm [ 4 ] for maximal clique enumeration, improved by a pivoting strategy introduced by Tomita et al. [ 23 , 24 ] , we first design four pruning heuristics aimed at reducing the search space, proving their correctness. The heuristics, that can be applied individually or in combination, allow the enumeration algorithm to focus only on promising parts of the search tree, discarding branches that are guaranteed not to yield \ell -isolated maximal cliques. Following a theoretical characterization of the heuristics’ pruning power and computational cost, which turn out to be inversely proportional, we conduct an extensive experimental study assessing their practical impact. Our analysis addresses both real and synthetic instances and contributes along several dimensions: • It sheds light on the properties of \ell -isolated cliques relative to the full set of maximal cliques in real-world graphs. This can be particularly useful for guiding the choice of parameter \ell . • It gives insights into the relative power of our pruning strategies and of their combinations, identifying the most effective ones. • It compares our approach with a carefully tuned baseline algorithm [ 23 , 24 ] and with a top-down state-of-the-art approach to the problem [ 13 ] . Overall, two of our variants offer substantial efficiency improvements over the state of the art, by as much as a factor of 4, especially when used on real-world graphs that exhibit social network properties. Paper organization. The rest of this paper is organized as follows. We provide preliminary definitions and a description of the baseline enumeration algorithm in \cref sec:preliminaries. The pruning strategies are introduced and theoretically analyzed in \cref sec:enumeration. Our experimental setup and the main outcomes of our analysis are discussed in \cref sec:setup and \cref sec:experiments, respectively. We summarize our results and outline open problems in \cref sec:conclusions. 2 Preliminaries In this section we first introduce preliminary definitions and properties of \ell -isolation ( \cref ss:l-isolation), and then describe the maximal clique enumeration algorithm underlying our approach ( \cref ss:mce). Throughout the paper we consider finite simple graphs. For a graph G , let V=V(G) and E=E(G) denote its vertex and edge sets, with n=|V| and m=|E| their respective sizes. For a vertex v , let \delta(v) denote its degree and N(v)=\{u\mid(u,v)\in E\} its set of neighbors. Clearly, \delta(v)=|N(v)| . For any vertex subset I\subseteq V , let G[I] denote the subgraph of G induced by I , with vertex set V[I]=I and edge set E[I]=\{(u,v)\in E\mid u,v\in I\} consisting of edges with both endpoints in I . For a vertex v\in I , let \delta_{e}(v,I)

Read the complete text