Mining frequent approximate patterns in large networks

摘要

Frequent pattern mining (FPM) algorithms are often based on graph isomorphism in order to identify common pattern occurrences. Recent research works, however, have focused on cases in which patterns can differ from their occurrences. Such cases have great potential for the analysis of noisy network data. Most existing FPM algorithms consider differences in edges and their labels, but none of them so far has considered the structural differences of vertices and their labels. Discerning how to identify cases that differ from the initial pattern by any number of vertices, edges, or labels has become the main challenge of recent research works. As a solution, we suggest a novel FMP algorithm named mining frequent approximate patterns (MFAPs) with two central new characteristics. First, we begin by using the inexact matching technique, which allows for structural differences in edge, vertices, and labels. Second, we follow the approximate matching with a focus on mining patterns within the directed graph, as opposed to the more commonly explored case of patterns being mined from the undirected graph. Our results illustrate the effectiveness of this new MFAP algorithm in identifying patterns within an optimized time.