SWFTPMiner: Mining Weighted Frequent Patterns from Graph Traversals with Noisy Information

摘要

To solve the problem of mining weighted frequent traversal patterns (WFTPs) with noisy weight information from weighted directed graph (WDG), an effective algorithm called SWFTPMiner (Statistical theory-based Weighted Frequent Traversal Patterns Miner) is developed. It first adopts statistical notion called Confidence Interval (CI) to delete the vertices with noisy weights from the traversal database (TDB), which reduce remarkably the size of TDB and the number of candidate patterns. Then the algorithm explores two mining strategies, respectively called level-wise strategy and divide-and-conquer strategy, to mine the WFTPs in mining process. Experimental results show: (1) Taking CI into consideration, we can discover more reliable WFTPs. (2) Algorithm SWFTPMiner is effective and scalable. The algorithm can be applied to various applications which can be modeled as a WDG.