Detecting Change Processes in Dynamic Networks by Frequent Graph Evolution Rule Mining

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 algorithmsfor dynamic networks.