WalDis: Mining Discriminative Patterns within Dynamic Graphs

VACULÍK, Karel and Lubomír POPELÍNSKÝ. WalDis: Mining Discriminative Patterns within Dynamic Graphs. Online. In IDEAS '18 Proceedings of the 22nd International Database Engineering & Applications Symposium. NY, USA: ACM New York, 2018, p. 95-102. ISBN 978-1-4503-6527-7. Available from: https://dx.doi.org/10.1145/3216122.3216172.

Basic information

• Original name: WalDis: Mining Discriminative Patterns within Dynamic Graphs
• Authors: VACULÍK, Karel (203 Czech Republic, guarantor, belonging to the institution) and Lubomír POPELÍNSKÝ (203 Czech Republic, belonging to the institution).
• Edition: NY, USA, IDEAS '18 Proceedings of the 22nd International Database Engineering & Applications Symposium, p. 95-102, 8 pp. 2018.
• Publisher: ACM New York

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: United States of America
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: electronic version available online
• WWW: URL
• RIV identification code: RIV/00216224:14330/18:00103236
• Organization unit: Faculty of Informatics
• ISBN: 978-1-4503-6527-7
• Doi: http://dx.doi.org/10.1145/3216122.3216172
• Keywords in English: data mining;discriminative patterns;dynamic graphs;graph mining;pattern mining;random walk
• Tags: firank_B
• Tags: International impact, Reviewed

Abstract

Real-world networks typically evolve through time, which means there are various events occurring, such as edge additions or attribute changes. In order to understand the events, one must be able to discriminate between different events. Existing approaches typically discriminate whole graphs, which are, in addition, mostly static. We propose a new algorithm WalDis for mining discriminate patterns of events in dynamic graphs. This algorithm uses sampling by random walks and greedy approaches in order to keep the performance high. Furthermore, it does not require the time to be discretized as other algorithms commonly do. We have evaluated the algorithm on three real-world graph datasets.

Links

• MUNI/A/0854/2017, interní kód MU: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VII.

Investor: Masaryk University, Category A

• MUNI/A/1038/2017, interní kód MU: Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 18

Investor: Masaryk University, Category A