不确定图上的kNN查询处理

摘要：

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

关键词：不确定图、可能世界、SimRank、kNN、子图

所属期刊栏目：48

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金项目61070056,61033010;"核高基"国家科技重大专项基金项目2010zx01042-001-002-002;教育部新世纪优秀人才支持计划基金项目NECT-09-823

在线出版日期：2012-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1850-1858