2014 | OriginalPaper | Buchkapitel
Detecting Maximum k-Plex with Iterative Proper ℓ-Plex Search
verfasst von : Yoshiaki Okubo, Masanobu Matsudaira, Makoto Haraguchi
Erschienen in: Discovery Science
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.