Affiliations: [a] Department of Mathematics, Computer Science and Statistics, State University of New York (SUNY) College at Oneonta, New York, NY 13820, USA | [b] Department of Computer Science and Technology, Tsinghua University, Beijing, China | [c] Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA
Correspondence:
[*]
Corresponding author: Sen Zhang, Department of Mathematics, Computer Science and Statistics, State University of New York (SUNY) College at Oneonta, New York, NY 13820, USA. E-mail: zhangs@oneonta.edu.
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.
