Fast Enumeration of Large k­Plexes

author: Donatella Firmani, Roma Tre University
published: Oct. 9, 2017,   recorded: August 2017,   views: 912

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.
  Delicious Bibliography


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.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: