不确定图上的kNN查询处理

摘要

在现实中的许多领域产生大量不确定的图结构的数据,例如分子化合物、蛋白质交互网络等。同时现实中有很多应用例如推荐系统中的推荐过滤、欺诈检测和社会网络的链接预测等,需要查询给定节点的k个最相似节点,针对这一问题,提出了用基于SimRank度量的方法来求解。由于图的动态演变和不确定性导致用现有的SimRank计算方法求k个最近邻的代价昂贵,因此提出一个有效算法,在保证一定准确性的前提下,通过引入路径阈值,算法只需考虑查询点的邻居区域无需考虑整个图从而达到明显的剪枝效果,该方法在确定图和不确定图上都可以适用。在此基础上为了进一步提高效率,算法在不确定图上引入采样技术。最后从理论、实验说明验证了算法的高效性和有效性。