A genetic algorithm for discriminative graph pattern mining

D 2019

A genetic algorithm for discriminative graph pattern mining

VACULÍK, Karel and Lubomír POPELÍNSKÝ

Basic information

Original name

A genetic algorithm for discriminative graph pattern mining

Authors

VACULÍK, Karel (203 Czech Republic, belonging to the institution) and Lubomír POPELÍNSKÝ (203 Czech Republic, belonging to the institution)

Edition

New York, Proceedings of the 23rd International Database Applications & Engineering Symposium, IDEAS 2019, Athens, Greece, p. 461-462, 2 pp. 2019

Publisher

ACM

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10200 1.2 Computer and information sciences

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/19:00110952

Organization unit

Faculty of Informatics

ISBN

978-1-4503-6249-8

DOI

http://dx.doi.org/10.1145/3331076.3331113

UT WoS

000810167700045

Keywords (in Czech)

data mining; graph mining; dynamic graphs; pattern mining; discriminative patterns; random walk; genetic algorithm

Keywords in English

data mining; graph mining; dynamic graphs; pattern mining; discriminative patterns; random walk; genetic algorithm

Abstract

V originále

Real-world networks typically evolve through time, which means there are various events occurring, such as edge additions or at- tribute changes. We propose a new algorithm for mining discriminative patterns of events in such dynamic graphs. This is dierent from other approaches, which typically discriminate whole static graphs while we focus on subgraphs that represent local events. Three tools have been employed The algorithm uses random walks and a nested genetic algo- rithm to nd the patterns through inexact matching. Furthermore, it does not require the time to be discretized as other algorithms commonly do. We have evaluated the algorithm on real-world graph data like DBLP and Enron. We show that the method outperforms baseline algorithm for all data sets and that the increase of accuracy is quite high, between 2.5for NIPS vs. KDD from DBLP dataset and 30% for Enron dataset. We also discus possible extensions of the algorithm.

Links

MUNI/A/1018/2018, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VIII.

Investor: Masaryk University, Category A

Citovat

VACULÍK, Karel and Lubomír POPELÍNSKÝ. A genetic algorithm for discriminative graph pattern mining. Online. In Bipin C. Desai and Dimosthenis Anagnostopoulos and Yannis Manolopoulos and Mara Nikolaidou. Proceedings of the 23rd International Database Applications & Engineering Symposium, IDEAS 2019, Athens, Greece. New York: ACM, 2019, p. 461-462. ISBN 978-1-4503-6249-8. Available from: https://dx.doi.org/10.1145/3331076.3331113.

@inproceedings{1569319,
   author = {Vaculík, Karel and Popelínský, Lubomír},
   address = {New York},
   booktitle = {Proceedings of the 23rd International Database Applications & Engineering Symposium, IDEAS 2019, Athens, Greece},
   doi = {http://dx.doi.org/10.1145/3331076.3331113},
   editor = {Bipin C. Desai and Dimosthenis Anagnostopoulos and Yannis Manolopoulos and Mara Nikolaidou},
   keywords = {data mining; graph mining; dynamic graphs; pattern mining; discriminative patterns; random walk; genetic algorithm},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {New York},
   isbn = {978-1-4503-6249-8},
   pages = {461-462},
   publisher = {ACM},
   title = {A genetic algorithm for discriminative graph pattern mining},
   year = {2019}
}

TY  - JOUR
ID  - 1569319
AU  - Vaculík, Karel - Popelínský, Lubomír
PY  - 2019
TI  - A genetic algorithm for discriminative graph pattern mining
PB  - ACM
CY  - New York
SN  - 9781450362498
KW  - data mining
KW  - graph mining
KW  - dynamic graphs
KW  - pattern mining
KW  - discriminative patterns
KW  - random walk
KW  - genetic algorithm
N2  - Real-world networks typically evolve through time, which means there are various events occurring, such as edge additions or at- tribute changes. We propose a new algorithm for mining discriminative patterns of events in such dynamic graphs. This is dierent from other approaches, which typically discriminate whole static graphs while we focus on subgraphs that represent local events. Three tools have been employed The algorithm uses random walks and a nested genetic algo- rithm to nd the patterns through inexact matching. Furthermore, it does not require the time to be discretized as other algorithms commonly do. We have evaluated the algorithm on real-world graph data like DBLP and Enron. We show that the method outperforms baseline algorithm for all data sets and that the increase of accuracy is quite high, between 2.5for NIPS vs. KDD from DBLP dataset and 30% for Enron dataset. We also discus possible extensions of the algorithm.
ER  -

VACULÍK, Karel and Lubomír POPELÍNSKÝ. A genetic algorithm for discriminative graph pattern mining. Online. In Bipin C. Desai and Dimosthenis Anagnostopoulos and Yannis Manolopoulos and Mara Nikolaidou. \textit{Proceedings of the 23rd International Database Applications \&{} Engineering Symposium, IDEAS 2019, Athens, Greece}. New York: ACM, 2019, p.~461-462. ISBN~978-1-4503-6249-8. Available from: https://dx.doi.org/10.1145/3331076.3331113.

Detailed Information on Publication Record