Detecting change processes in dynamic networks by frequent graph evolution rule mining

E. Scharwächter, E. Müller, J. Donges, M. Hassani, T. Seidl

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)
1 Downloads (Pure)

Abstract

The analysis of the temporal evolution of dynamic networks is a key challenge for understanding complex processes hidden in graph structured data. Graph evolution rules capture such processes on the level of small subgraphs by describing frequently occurring structural changes within a network. Existing rule discovery methods make restrictive assumptions on the change processes present in networks. We propose EvoMine, a frequent graph evolution rule mining method that, for the first time, supports networks with edge insertions and deletions as well as node and edge relabelings. EvoMine defines embedding-based and event-based support as two novel measures to assess the frequency of rules. These measures are based on novel mappings from dynamic networks to databases of union graphs that retain all evolution information relevant for rule mining. Using these mappings the rule mining problem can be solved by frequent subgraph mining. We evaluate our approach and two baseline algorithms on several real datasets. To the best of our knowledge, this is the first empirical comparison of rule mining algorithms for dynamic networks.

Original languageEnglish
Title of host publication16th IEEE International Conference on Data Mining, ICDM 2016; Barcelona, Catalonia; Spain; 12 December 2016 through 15 December 2016
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Pages1191-1196
Number of pages6
ISBN (Electronic)978-1-5090-5473-2
ISBN (Print)978-1-5090-5474-9
DOIs
Publication statusPublished - 31 Jan 2017
Event16th IEEE International Conference on Data Mining, ICDM 2016 - Barcelona, Catalonia, Spain
Duration: 12 Dec 201615 Dec 2016

Conference

Conference16th IEEE International Conference on Data Mining, ICDM 2016
Country/TerritorySpain
CityBarcelona, Catalonia
Period12/12/1615/12/16

Cite this