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 𝑘-plex is one of the arguably most studied pseudo-clique model. A 𝑘-plex of size 𝑛 is a subgraph where any vertex is adjacent to at least (𝑛-𝑘) vertices. Unfortunately, some maximal 𝑘-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 𝑘-plex model, called cohesive 𝑘-plex, which is more appropriate for modeling closelyinteracting communities. Then, we reduce the problem of enumerating maximal (cohesive) 𝑘-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.