Fast Enumeration of Large k-Plexes
Alessio Conte (University of Pisa);Donatella Firmani (Roma Tre University);Caterina Mordente (Be Think Solve Execute);Maurizio Patrignani (Roma Tre University);Riccardo Torlone (Roma Tre University)
Abstract
The k-plex is a formal yet flexible way of defining communities in any kind of network. It generalizes the notion of clique and is more appropriate in most real cases: while a node of a clique C is connected to all other nodes of C, a node of a k-plex may miss k connections. Unfortunately, computing all maximal k-plexes is a gruesome task and state of the art algorithms can only process small-size networks. In this paper we propose a new approach for enumerating large k-plexes in networks that speeds up the search of several orders of magnitude by leveraging: (i) methods for strongly reducing the search space and (ii) efficient techniques for the computation of maximal cliques. Several experiments show that our strategy is effective and is able to increase the size of the networks for which the computation of large k-plexes is feasible from a few hundred to several hundred thousand nodes.
