Algorithms for mining the coevolving relational motifs in dynamic networks

Rezwan Ahmed, George Karypis

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Computational methods and tools that can efficiently and effectively analyze the temporal changes in dynamic complex relational networks enable us to gain significant insights regarding the entity relations and their evolution. This article introduces a new class of dynamic graph patterns, referred to as coevolving relational motifs (CRMs), which are designed to identify recurring sets of entities whose relations change in a consistent way over time. CRMs can provide evidence to the existence of, possibly unknown, coordination mechanisms by identifying the relational motifs that evolve in a similar and highly conserved fashion. We developed an algorithm to efficiently analyze the frequent relational changes between the entities of the dynamic networks and capture all frequent coevolutions as CRMs. Our algorithm follows a depth-first exploration of the frequent CRM lattice and incorporates canonical labeling for redundancy elimination. Experimental results based on multiple real world dynamic networks show that the method is able to efficiently identify CRMs. In addition, a qualitative analysis of the results shows that the discovered patterns can be used as features to characterize the dynamic network.

Original languageEnglish (US)
Article number4
JournalACM Transactions on Knowledge Discovery from Data
Volume10
Issue number1
DOIs
StatePublished - Jul 1 2015

Keywords

  • Algorithms
  • Dynamic networks
  • Evolving pattern mining
  • G.2.2 [graph theory]: Graph mining
  • I.2.8 [problem solving, control methods, and search]: Graph mining
  • Network evolution

Fingerprint Dive into the research topics of 'Algorithms for mining the coevolving relational motifs in dynamic networks'. Together they form a unique fingerprint.

Cite this