A Declarative Framework for Maximal k-plex Enumeration Problems

It is widely accepted that an ideal community in networks is the one whose structure is closest to a (maximal) clique. However, in most real-world graphs the clique model is too restrictive, as it requires complete pairwise interactions. More relaxed cohesive subgraph models were then studied. A k-plex is one of the arguably most studied pseudo-clique model. A k-plex of size n is a subgraph where any vertex is adjacent to at least (n - k) vertices. Unfortunately, some maximal k-plexes, by involving irrelevant subgraphs, are far from designing meaningful communities in real-world networks. In this paper, we first introduce a novel variant of k-plex model, called cohesive k-plex, which is more appropriate for modeling closely-interacting communities. Then, we reduce the problem of enumerating maximal (cohesive) k-plexes in a graph to those of enumerating the models of a formula in propositional logic. Afterwards, to make our approach more efficient, we provide a decomposition technique that is particularly suitable for deriving smaller and independent sub-problems easy to resolve. Lastly, our extensive experiments on various real-world graphs demonstrate the efficiency of the proposed approach w.r.t state-of-the-art algorithms.