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

Conference Contribution

Scharwächter, E., Müller, E., Donges, J., Hassani, M. & Seidl, T. (2017). Detecting change processes in dynamic networks by frequent graph evolution rule mining. 16th IEEE International Conference on Data Mining, ICDM 2016; Barcelona, Catalonia; Spain; 12 December 2016 through 15 December 2016 (pp. 1191-1196). Piscataway: Institute of Electrical and Electronics Engineers (IEEE). In Scopus Cited 0 times.

Read more: DOI     

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.