Mining Coevolving Induced Relational Motifs in Dynamic Networks

Rezwan Ahmed and George Karypis
Workshop on Dynamic Networks (SDM-Networks), SIAM Data mining Conference, 2015
Download Paper
Abstract
A fundamental task associated with the analysis of a dynamic network is to study and understand how the network changes over time. Co-evolution of patterns, where all the relations among a set of entities change in a consistent way over time, can provide evidence of possibly unknown coordination mechanism among the entities of a dynamic network. This paper introduces a new class of dynamic network patterns, referred to as coevolving induced relational motifs (CIRMs), which are designed to identify a recurring set of nodes whose complete set of intra-relations undergo some changes in a consistent way over time. We develop an algorithm to analyze all relational changes between entities and find all frequent coevolving induced relational motifs. Experimental results based on multiple dynamic networks derived from real world datasets show that the algorithm is able to identify all frequent CIRMs in small amount of time. In addition, a qualitative analysis of the results shows that the discovered CIRMs are able to capture network characteristics that can be used as features for modeling the underlying dynamic network in the context of a classification task.
Research topics: Data mining | Graph mining