Fast Enumeration of Large kPlexes
published: Oct. 9, 2017, recorded: August 2017, views: 8
Report a problem or upload filesIf 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.
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 pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !