Advertisement
Published in:
2014 | OriginalPaper | Chapter
Detecting Maximum k-Plex with Iterative Proper ℓ-Plex Search
Authors : Yoshiaki Okubo, Masanobu Matsudaira, Makoto Haraguchi
Published in: Discovery Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper, we are concerned with the notion of
k
-plex, a relaxation model of clique, where degree of relaxation is controlled by the parameter
k
. Particularly, we present an efficient algorithm for detecting a
maximum k-plex
in a given simple undirected graph. Existing algorithms for extracting a maximum
k
-plex do not work well for larger
k
-values because the number of
k
-plexes exponentially grows as
k
becomes larger. In order to design an efficient algorithm for the problem, we introduce a notion of
properness
of
k
-plex. Our algorithm tries to
iteratively
find a maximum proper ℓ-plex, decreasing the value of ℓ from
k
to 1. At each iteration stage, the maximum size of proper ℓ-plex found so far can work as an effective lower bound which makes our branch-and-bound pruning more powerful. Our experimental results for several benchmark graphs show that our algorithm can detect maximum
k
-plexes much faster than
SPLEX
, the existing most efficient algorithm.