Algorithms for mining the coevolving relational motifs in dynamic networks

Rezwan Ahmed, George Karypis

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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
Issue number1
StatePublished - Jul 1 2015

Bibliographical note

Publisher Copyright:
© 2015 ACM.


  • 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


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

Cite this