Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Structural Change Pattern Mining Based on Constrained Maximal k-Plex Search
verfasst von : Yoshiaki Okubo, Makoto Haraguchi, Etsuji Tomita
Erschienen in: Discovery Science
Verlag: Springer Berlin Heidelberg
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
We discuss in this paper a problem of mining structural change patterns. Given a pair of graphs before and after some change, a
structural change pattern
is extracted as a vertex set
X
which is pseudo-independent set before the change but a pseudo-clique after the change. In order to detect this kind of patterns more interesting,
X
is particularly required to have many outgoing edges from
X
before the change, while to have few outgoing edges after the change. We formalize such an
X
as a maximal
k
-plex in the combined graph defined from the given graphs. An effective algorithm for extracting them is designed as a constrained maximal
k
-plex enumerator with a pruning mechanism based on
right candidate control
. Our experimental results show an example of structural change pattern actually detected. Moreover, it is shown that the pruning mechanism and the use of combined graph are very effective for efficient computation.