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

    4 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
    CountrySpain
    CityBarcelona, Catalonia
    Period12/12/1615/12/16

    Cite this