JOURNAL OF COMPUTERS (JCP)

ISSN : 1796-203X

Volume : 3 Issue : 10 Date : October 2008

**Mining Frequent Subgraph by Incidence Matrix Normalization**

Jia Wu and Ling Chen

Page(s): 109-115

Full Text: PDF (456 KB)

**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

ISSN : 1796-203X

Volume : 3 Issue : 10 Date : October 2008

Page(s): 109-115

Full Text: PDF (456 KB)

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.