Discovering frequent induced subgraphs from directed networks

Sen Zhang, Zhihui Du, Jason T.L. Wang, Haodi Jiang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Directed networks find many applications in computer science, social science and biomedicine, among others. In this paper we propose a new graph mining algorithm that is capable of locating all frequent induced subgraphs in a given set of directed networks. We present an incremental coding scheme for representing the canonical form of a graph, study its properties, and develop new techniques for pattern generation suitable for directed networks. We prove that our algorithm is complete, meaning that no qualified pattern is missed by the algorithm. Furthermore, our algorithm is correct in the sense that all patterns found by the algorithm are frequent induced subgraphs in the given networks. Experimental results based on synthetic data and gene regulatory networks show the good performance of our algorithm, and its application in network inference.

Original languageEnglish (US)
Pages (from-to)1279-1296
Number of pages18
JournalIntelligent Data Analysis
Issue number6
StatePublished - 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


  • Apriori algorithm
  • graph mining
  • network inference
  • structural pattern discovery


Dive into the research topics of 'Discovering frequent induced subgraphs from directed networks'. Together they form a unique fingerprint.

Cite this