智能与分布计算实验室

TGP: Mining Top-K Frequent Closed Graph Pattern without Minimum Support

出版社:
  • 会议名称:The International Conference on Advanced Data Mining and Applications (ADMA 2010)
  • 举办地点:Chongqing,China
  • 举办日期:November 19-21, 2010
  • 页数:537-548
摘要内容:

In this paper, we propose a new mining task: mining top-k frequent closed graph patterns without minimum support. Most previous frequent graph pattern mining works require the specification of a minimum support threshold. However it is difficult for users to set a suitable value sometimes. We develop an efficient algorithm, called TGP, to mine patterns without minimum support. A new structure called Lexicographic Pattern Net is designed to store graph patterns, which makes the closed pattern verification more efficient and speeds up raising support threshold dynamically. In addition, Lexicographic Pattern Net can be stored in the file through serialization, so it doesn’t need generate candidate patterns again in the next mining. It is found in the preliminary experiments that TGP can find top-k frequent closed graph patterns completely and accurately. Furthermore, TGP can be extended to mine other kinds of graphs or dynamic graph streams easily.

关键词:
  • data mining;top-k frequent closed graph pattern