从不确定图中挖掘频繁子图模式.pdf

文档介绍：ISSN 1000-9825, CODEN RUXUEW E-mail: ******@iscas.
Journal of Software, , , November 2009, −2976
doi: . Tel/Fax: [phone]
© by Institute of Software, the Chinese Academy of Sciences. All rights reserved.

∗
从不确定图中挖掘频繁子图模式
邹兆年, 李建中+, 高宏, 张硕
(哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨 150001)
Mining Frequent Subgraph Patterns from Uncertain Graphs
ZOU Zhao-Nian, LI Jian-Zhong+, GAO Hong, ZHANG Shuo
(School puter Science and Technology, Harbin Institute of Technology, Harbin 150001, China)
+ Corresponding author: E-mail: ******@hit., .
Zou ZN, Li JZ, Gao H, Zhang S. Mining frequent subgraph patterns from uncertain graphs. Journal of
Software, 2009,20(11):2965−2976. /1000-9825/
Abstract: This paper studies uncertain graph data mining and especially investigates the problem of mining
frequent subgraph patterns from uncertain graph data. A data model is introduced for representing uncertainties in
graphs, and an expected support is employed to evaluate the significance of subgraph patterns. By using the apriori
property of expected support, a depth-first search-based mining algorithm is proposed with an efficient method for
computing expected supports and a technique for pruning search space, which reduces the number of subgraph
isomorphism testings needed puting expected support from the exponential scale to the linear scale.
Experimental results show that the proposed algorithm is 3 to 5 orders of magnitude faster than a naïve depth-first
search algorithm, and is efficient and scalable.
Key words: uncertain graph; graph mining; frequent subgraph pattern
摘要: 研究不确定图数据的挖掘,
示图的不确定性, Apriori 性质,给出了一种基于
,使得计算子图模式的
,该算法比简单的深度优先搜索算法
快 3~5 个数量级,有很高的效率和可扩展性.
关键词: 不确定图;图挖掘;频繁子图模式
中图法分类号: TP311 文献标识码: A
近年来,科研领域积累了大量用图来建模的数据(简称图数据),如化合物分子结构、传