论文部分内容阅读
现实世界中，很多实际问题都更适合于用“图”进行建模。在图挖掘领域，对象相似度作为一个重要课题，被广泛应用在链接预测、欺诈检测、协同过滤、近邻查询等众多实际问题中。在传统确定图上，节点相似度的研究受到了广泛关注并取得了很多成果。但是，确定图上对象相似度的定义和计算无法直接应用于概率图。 在可能世界模型下，概率图可以衍生出指数个可能世界实例，昂贵的计算代价是概率图上对象相似度计算面临的重要问题。目前，概率图上对象相似度计算的已有研究成果存在如下缺陷:一类算法是针对特殊图的特定算法，无法应用于一般图。这些特殊图有两种情况，或者所有概率相等，或者边分组出现，每组具有相同的概率。第二类算法是近似算法，使用抽样算法或者基于聚类的分组算法进行近似计算，虽然可以应用在一般图上，但是无法给出精确结果。第三类算法是枚举可能世界的Naive算法，算法的时间复杂度是指数级，无法应用在实际查询中。 本文主要研究概率图上的对象相似度计算。在可能世界模型下，本文首先给出了概率图上的期望SimRank定义。基于期望转移矩阵，期望SimRank的计算可以转换为确定图上SimRank的计算，因此期望SimRank计算的关键就是概率图上期望转移矩阵的计算。在期望转移矩阵的计算上，本文提出了子图划分方法，将大图划分为子图分而治之。在子图上，依次提出了完全二叉树算法CBT(Complete Binary Tree)算法、动态规划算法DP(Dynamic Programming)、增量动态规划算法IDP(Incremental Dynamic Programming)，将算法时间复杂度从指数降为多项式。其中，IDP在所有算法中性能最优，并可适用于动态图的更新。最后，通过链接预测实验和性能对比实验，证明了期望SimRank衡量对象相似度的有效性，验证了所提出算法的高效性和可扩展性。