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

Abstract

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
Volume22
Issue number6
DOIs
StatePublished - 2018

All Science Journal Classification (ASJC) codes

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

Keywords

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

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

Cite this