黄冬梅　邓　斌　赵丹枫

(上海海洋大学信息学院　上海 201306)



带权不确定图的K最近邻查询算法

黄冬梅邓斌赵丹枫

(上海海洋大学信息学院上海 201306)

摘要社交、移动等复杂网络节点接入的不确定性给数据查询处理带来了新的挑战。K最近邻查询是社交、移动网络中经常用到的操作。已有的方法首先将网络映射为不确定图，然后，考虑边只含有概率信息的情况。讨论了K最近邻查询方法，没有考虑权重信息，具有局限性。针对这个问题，定义了带权不确定子图和ProWeiDist距离，兼顾权重和概率两个要素,提出了针对带权不确定图的K最近邻查询算法，并对算法进行优化。实验结果表明，SubDistK算法能有效地解决K最近邻查询问题。

关键词复杂网络不确定数据K最近邻查询带权不确定图子图

K-NEAREST NEIGHBOURS QUERY IN WEIGHTED UNCERTAIN GRAPH

Huang DongmeiDeng BinZhao Danfeng

(College of Information,Shanghai Ocean University,Shanghai 201306,China)

AbstractUncertainty of nodes accessing in complex social and mobile networks brings new challenge to data query and processing. K-nearest neighbours query is an operation frequently used over these complex networks. Existing methods map the network to uncertain graph first, and they consider the situation of containing the probability information only.Discussing the K-nearest neighbours query method but do not consider the weight information, therefore have limitations. In view of this problem, we defined the weighted uncertain subgraph and ProWeiDist distance, and proposed a K-nearest neighbours query algorithm targeted at the weighted uncertain graph by incorporating both probability and weight, and further optimised the algorithm. Experimental results demonstrated that the SubDistK algorithm can effectively solve K-Nearest neighbours query problem.

KeywordsComplex networkUncertain dataK-nearest neighbours queryWeighted uncertain graphSubgraph

0引言

快速发展的社交、移动等网络，由于噪声控制、隐私保护等原因，产生了大量的不确定数据[1,2]。针对不确定数据的建模有关系型数据[3]、流数据、半结构化数据、移动对象数据等[4]。在蛋白质网络、社交领域中，图模型更加适合不确定数据的建模研究[5,6]。其中，查询对象作为图的节点，对象之间的关系作为顶点之间的边，数据间的不确定性成为边的概率函数。在社交网络中[7]，每位用户构成无向图的一个顶点，用户之间的关系构成顶点之间的边。在图中的每条边上加入概率信息构成不确定图，是不确定数据领域研究的一种常用方法。文献[8]提出不确定图的“可能世界”语义模型，不确定图中每条边都附带一个介于0和1之间的实数，以表示边存在的概率，边的存在概率是相互独立的。……