Mining Top-K Frequent Correlated Subgraph Pairs in Graph Databases

In this paper, a novel algorithm called KFCP(top K Frequent Correlated subgraph Pairs mining) was proposed to discover top-k frequent correlated subgraph pairs from graph databases, the algorithm was composed of two steps: co-occurrence frequency matrix construction and top-k frequent correlated subgraph pairs extraction. We use matrix to represent the frequency of all subgraph pairs and compute their Pearson's correlation coefficient, then create a sorted list of subgraph pairs based on the absolute value of correlation coefficient. KFCP can find both positive and negative correlations without generating any candidate sets; the effectiveness of KFCP is assessed through our experiments with real-world datasets.