English
Mining Frequent Subgraphs over Uncertain Graph Databases under Probabilistic Semantics
文件大小：
1029k
资源说明：本文介绍了一种在不确定性图数据库中挖掘频繁子图的方法，并采用了概率语义来评估子图出现的频率。文章中探讨了在现实应用中图数据往往带有不确定性的问题，但目前关于不确定图数据挖掘的研究工作却非常有限。针对这一问题，文章提出了一种新的测度方法——φ频繁概率，用于衡量子图的出现频率。
核心概念“φ频繁概率”定义为在给定的不确定性图数据库集合和两个实数参数0<φ,τ<1的情况下，用于寻找所有具有φ频繁概率至少为τ的子图。这里的φ和τ是概率阈值，用于确定一个子图在不确定性图数据库中出现的概率。
由于挖掘不确定性图数据库中频繁子图的问题被证明是NP-hard（非确定性多项式时间困难问题），而计算子图的φ频繁概率是#P-hard（#多项式时间困难问题），因此直接精确解决该问题在计算上是不现实的。为了解决这一难题，本文提出了一种近似挖掘算法，该算法能够高效地产生一个近似频繁子图集合Π，这个集合是(ε,δ)-近似的，其中0<ε<τ是误差容忍度，0<δ<1是置信界限。算法保证了两个性质：任何频繁子图S被包含在集合Π中的概率至少为((1−δ)/2)^s（s是S中边的数量）；任何不频繁子图且其φ频繁概率小于τ−ε被包含在Π中的概率最多为δ/2。
理论分析表明，为了获得至少包含概率为1−Δ的任何频繁子图，算法的输入参数δ必须被设置为最多1−2(1−Δ)^(1/|E_max|)，其中0<Δ<1，并且|E_max|是频繁子图中最大边数。通过在真实不确定图数据库上的广泛实验验证了所提出算法的实用效率和极高的近似质量。文章还提到，一个扩展摘要在ACM SIGKDD国际会议的知识发现和数据挖掘（KDD）2010年会上发表过。
这项研究工作由来自哈尔滨工业大学计算机科学与技术学院的Jianzhong Li、Zhaonian Zou和Hong Gao完成。他们提出的这种方法不仅为处理不确定性图数据提供了理论基础，也对数据挖掘领域的发展产生了积极的影响。该方法通过使用近似算法和概率分析来应对传统频繁子图挖掘在不确定性数据上的挑战，为不确定性图数据挖掘提供了新的思路和技术。
通过这项研究，作者们旨在促进不确定图数据的分析和理解，帮助从大规模的不确定数据中提取有价值的信息，并应用于如社交网络分析、生物信息学、化学信息学等众多领域，其中图形数据的不确定性是一个常见且关键的问题。这篇论文的技术贡献不仅在于它提出了一种新的挖掘技术，也在于它在理论和实践层面对频繁子图挖掘问题进行了全面的探讨。
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
