Volume 3 Number 10 (Oct. 2008)
Home > Archive > 2008 > Volume 3 Number 10 (Oct. 2008) >
JCP 2008 Vol.3(10): 109-115 ISSN: 1796-203X
doi: 10.4304/jcp.3.10.109-115

Mining Frequent Subgraph by Incidence Matrix Normalization

Jia Wu, Ling Chen
1Department of Computer Science, Yangzhou University, Yangzhou, China

Abstract—Existing frequent subgraph mining algorithms can operate efficiently on graphs that are sparse, have vertices with low and bounded degrees, and contain welllabeled vertices and edges. However, there are a number of applications that lead to graphs that do not share these characteristics, for which these algorithms highly become inefficient. In this paper we propose a fast algorithm for mining frequent subgraphs in large database of labeled graphs. The algorithm uses incidence matrix to represent the labeled graphs and to detect their isomorphism. Starting from the frequent edges from the graph database, the algorithm searches the frequent subgraphs by adding frequent edges progressively. By normalizing the incidence matrix of the graph, the algorithm can effectively reduce the computational cost on verifying the isomorphism of the subgraphs. Experimental results show that the algorithm has higher speed and efficiency than that of other similar ones.

Index Terms—graph; incidence matrix; isomorphism; data mining

[PDF]

Cite: Jia Wu, Ling Chen, "Mining Frequent Subgraph by Incidence Matrix Normalization," Journal of Computers vol. 3, no. 10, pp.109-115, 2008.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Monthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Jul 19, 2019 News!

    Vol 14, No 7 has been published with online version   [Click]

  • Jun 21, 2019 News!

    Vol 14, No 6 has been published with online version   [Click]

  • Read more>>