Efficient mining of interesting weighted patterns from directed graph traversals

Abstract

Data mining for traversal patterns has been found useful in many applications. Traditional methods of traversal patterns mining only considered unweighted traversals. The support measure in weighted cases no longer satisfies the anti-monotone property and previous algorithms cannot be applied. In this paper, a transformational model between EWDG (Edge-Weighted Directed Graph) and VWDG (Vertex-Weighted Directed Graph) is proposed. Based on the model, we explore the problem of mining interesting patterns – frequent patterns and closed frequent patterns form traversals on WDG and propose two algorithms respectively called WTFPMiner (Weighted Traversal Frequent Patterns Miner) and CWTFPMiner (Closed Weighted Traversal Frequent Patterns Miner). WTFPMiner devises a novel property between weighted patterns – scalable property, which is similar to the well-known downward closure property, to convert weighted pattern mining problem into corresponding pattern scalability decision problem, and finally exploits this property to mine the weighted frequent patterns efficiently from traversals on WDG. Based on an improved model of weighted support, algorithm CWTFPMiner adopts a divide-and-conquer paradigm in a pattern growth manner to mine closed weighted frequent patterns efficiently from the traversals on weighted directed graph. It incorporates the closure property with weight constrain to dramatically reduce search space and extracts succinct and lossless patterns from traversal transactions of WDG. Our performance study shows that the two algorithms are efficient and scalable for the problem of mining frequent patterns based on weighted directed graph traversals. Moreover, they can be applied in diversiform environments which can be modeled as a WDG.