Incremental Discovery of Top-k Correlative Subgraphs

Although data mining is a research area with important contributions, there is relatively limited work on correlation mining from graph databases. In this paper, we formulate the problem of mining the next most correlated graph in a graph database given the top-k correlated graphs, with respect to a query graph q. In order to solve the above problem, we take advantage of the search tree, produced by the top-k graphs. However, the search tree poses significantly difficulties, due to its size. Mainly relied on the TopCor algorithm, we make use of the algorithm´s findings and rules, we derive two termination conditions and we devise a new algorithm to address the above problem, iTopCor. Our experimental results demonstrate the efficiency of the algorithm with respect to TopCor, especially when the data set is large or when many sub graph isomorphism tests are involved.