Mining frequent k-edge-connected subgraphs

摘要

The output of frequent pattern mining is a large amount of redundant frequent patterns, causing a hard problem in the process of data mining and knowledge discovery. Incorporating the information of edge connectivity into the gSpan algorithm, we propose an efficient algorithm for mining frequent k-edge-connected subgraphs in a given graph dataset. Exactly, when the DFS code tree goes through depth-first search, the k-edged connectivity of each node is examined using DIJKSTRA algorithm and Menger theorem firstly. Then, based on the established properties of edge connectivity, one edge extensions of graph G are pruned selectively. Finally, all the frequent k-edge-connected graphs are output through the decision rule. The experiments show its validity of output reduction and feature representation.