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

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

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    4 Citaten (Scopus)
    1 Downloads (Pure)


    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.

    Originele taal-2Engels
    Titel16th IEEE International Conference on Data Mining, ICDM 2016; Barcelona, Catalonia; Spain; 12 December 2016 through 15 December 2016
    Plaats van productiePiscataway
    UitgeverijInstitute of Electrical and Electronics Engineers
    Aantal pagina's6
    ISBN van elektronische versie978-1-5090-5473-2
    ISBN van geprinte versie978-1-5090-5474-9
    StatusGepubliceerd - 31 jan 2017
    Evenement16th IEEE International Conference on Data Mining, ICDM 2016 - Barcelona, Catalonia, Spanje
    Duur: 12 dec 201615 dec 2016


    Congres16th IEEE International Conference on Data Mining, ICDM 2016
    StadBarcelona, Catalonia

    Citeer dit