不确定随机网络Top-k最近节点查询算法

连春月，李孝忠，牛浩浩

(天津科技大学计算机科学与信息工程学院，天津 300457)

实际生活中，会遇到许多非确定的现象．为了研究这类非确定的现象，17世纪诞生了概率论．概率论基于大量的历史数据，有效解决了很多统计问题．但是，有时因为各种原因无法获得足够多的数据，这时使用概率论解决问题就很难办到．为了解决这类问题，Liu B于2007年提出了不确定理论[1]，并于2010年对不确定理论进行重新定义[2]，为小样本数据、甚至是无样本数据的统计提供了新的理论基础．

经过多年研究与实践，不确定理论得到了充分的发展与广泛的应用．2013年，高原[3]详细研究了不确定网络的最短路径问题；2014年，Zhou等[4]研究了不确定网络的最短路径的逆不确定分布问题；2015年，Zhou等[5]给出了不确定网络的最小生成树的路径最优条件．

对于一个复杂网络，某些弧的权重可以通过对历史数据进行统计分析得到，而某些弧由于没有历史数据或者历史数据无效，导致其权重不能通过概率统计得到，只能利用专家的经验数据，得到不确定弧的权重的不确定分布函数．

2013年，为了解决这类既有非确定因素，又有不确定因素的现象，Liu Y[6]开创了机会理论．2014年，Liu B[7]首次将机会理论引入不确定网络，提出不确定随机网络的概念．2015年，盛玉红[8]对不确定随机网络的最短路径问题、最小生成树问题和最大流问题进行研究，提出理想机会分布函数的概念并利用其求解了上述问题．

关于非确定性数据的Top-k查询问题，学者们提出了各种计算方法，包括U-topK[9]、U-kRanks[10]，PT-k[11]，Global-topK[12]等．Li 等[13]提出了基于权值参数的排名函数，实现了排名分值与概率平衡．2016年，郭长友等[14]首次将不确定理论应用到不确定数据的Top-k查询计算中．

非确定数据的 Top-k查询在 P2P系统、电缆铺设等方面已经有了实际应用，但不确定数据和随机数据同时存在的Top-k查询方面的研究并不多．本文基于现有研究成果，将包含不确定数据和随机数据的问题转化为不确定随机网络，并在深度优先遍历的算法上，提出在一定机会测度的情况下，寻找距离某个节点最近的k个节点的算法，能有效解决在经验数据和小样本数据混杂情况下的节点查询问题．

1 相关概念

1.1 不确定理论[1]

定义1设Γ为非空集合，L是Γ上的σ-代数，任意的Λ∈L称为一个事件．如果从L到实数集R的集函数M满足以下条件：

公理 1(规范性) 对于全集Γ，有M{Γ}=1；

公理 2(对偶性) 对于任意的事件Λ∈L，有M{Λ}+M{Λc}=1；

公理 3(次可列可加性) 对于可数的事件序列M{Λ}，有

则称集函数 M 为Γ上的不确定测度，三元组(Γ,L, M)称为一个不确定空间．

为了研究乘积空间上的不确定测度，Liu B提出了乘积公理[1]：

公理 4设(Γi,Li,Mi)为一列不确定空间，则乘积不确定测度M为

不确定变量的定义是由抽象的不确定空间和Borel集描述的．如果仅从定义出发，在理解和应用不确定变量时都会遇到困难，为了更好地理解不确定变量，给出如下不确定分布的概念．

定义 4若不确定变量ξ具有不确定分布

其中 a和 b为常数，则ξ为线性的不确定变量，记为L( a, b)．

定义 5若对于任意的 α∈ (0,1)，不确定变量ξ的不确定分布Φ(x)的反函数 Φ-1(α)存在且唯一，则称Φ(x)为正则分布，称ξ为正则不确定变量．

定义 6若不确定变量ξ具有正则分布Φ(x)，则其反函数Φ-1(α)称为ξ的逆不确定分布．

例 1根据定义 4—定义 6，线性不确定变量L( a, b)的逆不确定分布为

1.2 机会理论[6]

定义 7设(Γ,L,M)× (Ω,A, Pr)是一个机会空间，Θ是L×A的一个事件，那么事件Θ的机会测度为

定义 8从机会空间(Γ ,L ,M )× (Ω,A, Pr)到实数集 R的可测函数ξ称为不确定随机变量，即对于任意的Borel实数集Β，集合

是L×A中的一个事件．定义 9设 f:Rn→R是一个可测函数，ξ1,ξ2,…,ξn是机会空间(Γ,L,M)×(Ω,A, Pr)上的一列不确定随机变量，那么对任意的(γ,ω)∈Γ×Ω，ξ=f(ξ1,ξ2,…,ξn)是由

所确定的一个不确定随机变量．

定义10η1,η2,…,ηm是一系列独立的随机变量，概率分布分别为Ψ1,Ψ2,…,Ψm，τ1,τ2,…,τn是一列不确定变量，不确定分布分别为ϒ1,ϒ2,… ,ϒn，那么不确定随机变量

有一个机会分布

其中，对任意的实数y1, y2,…,ym，F(x, y1,y2,…,ym)是不确定变量f(η1,η2,…,ηm,τ1,τ2,…τn)的不确定分布，它可由其反函数F-1(α;y, y,…,y)=f(y,y,…,12m12y,ϒ-1(α) ,ϒ-1(α),…,ϒ-1(α))决定，条件是f为对于m12nτ1,τ2,…,τn的单增函数．

例 2设η是一个随机变量，其概率分布为Ψ，τ是一个不确定变量，其不确定分布为ϒ．那么，ξ= η+ τ是一个不确定随机变量，ξ的机会分布为

其中，y是随机变量η的任一实现．

2 不确定随机网络下的Top-k查询算法

2.1 不确定随机网络

N是节点集合，U是不确定弧的集合，R是随机弧的集合，W 是不确定权重和随机权重的集合，那么四元组(N，U，R，W)被称为一个不确定随机网络．

例3图1是有4个节点的不确定随机网络．其中，随机权重ηAB、ηCD的概率分布分别为ΨAB、ΨCD．不确定权重τBC具有正则的不确定分布ϒBC．各边的权重的分布函数见表1．

图1 4节点不确定随机网络Fig. 1 Uncertain random network with 4 nodes

表1 图1网络中各边的权重的分布函数Tab. 1 Distribution function of the edge’s weight of figure 1

ΨAB，ΨCD的概率分布函数分别为

ϒBC的不确定分布为

则权重的机会分布函数为

计算可得

假设机会测度Φ (x) =0.95，计算得权重x=25.7．

2.2 Top-k最近节点查询算法

给定不确定随机网络G，节点间的权重的机会分布函数为Φ，则节点间的路径长度机会分布函数D＝Φ，即将节点间的权重建模为节点间的路径长度．基于节点间的路径长度，提出以下的不确定随机网络Top-k最近节点查询算法．

输入：不确定随机网络 G＝(N，U，R，W)，选择的最近节点个数k，初始节点p，机会测度α．

输出：当机会测度为α时，与 p最近的k个节点，以及对应路径．

具体算法如下：

(1)计算所有节点间 i，j间的路径，初始节点为：i＝1，j＝2，并将 i标记为已访问；

(2)从N中取出非i节点k，若两点间有路径，将k标记为已访问；

(3)若k＝j，将所有已访问节点组成的路径放入路径集合D中，回溯至上一个已访问节点，重复步骤(2)；否则，重复步骤(2)；

(4)若 k≥n，j++，重复步骤(1)—(3)，直至 j＝n；

(5)若 j＞n，j- -，i++，重复步骤(1)—(4)，直至 i＝n；

(6)计算D中所有路径的机会分布函数；

(7)计算当机会测度为α时，点 p到所有节点的路径长度；

(8)找到距离点 p最近的k个点及对应路径，算法结束．

算法中步骤(2)—(3)部分的代码如下：

function FindPath(matrix，startNode，endNode){

result[nPos]＝startNode.key；//将当前节点放入结果集

Mark[startNode.key]＝true；//标记为已访问nPos++；

while(nPos !＝0){

var tempVal＝result[nPos-1]；//获取结果集最后

一个元素

if(tempVal＝＝endNode.key){//如果当前节点为

结束节点，将结果集中的节点放入路径结果集中

for(let j＝0；j＜nPos；j++){

resultPath[pathNum][j]＝result[j]；

}

nPos- -；//回溯至目标节点的上一个节点

result[nPos]＝0；

pathNum++；//新增路径数目

Mark[endNode.key]＝false；

break；

}；

while(startNode.flag＜matrix.length){

if(matrix[tempVal][startNode.flag]＝＝1){

if(Mark[startNode.flag]＝＝false){

var tempNode＝new Node()；

tempNode.key＝startNode.flag；

tempNode.flag＝0；

FindPath(matrix，tempNode，endNode)；

}

}

startNode.flag++；

}

if(startNode.flag＝＝matrix.length){

nPos- -；

startNode.flag＝0；

Mark[startNode.key]＝false；

break；

}

}

为了更好地理解算法，用例4进行简要说明．

例 4有 5个节点的不确定随机网络，如图 2所示．其中τAB、τBD、τDE是不确定权重，且分别具有正则的不确定分布ϒAB、ϒBD、ϒDE；ηAE、ηBC、ηCD是随机权重，分别具有概率分布ΨAE、ΨBC、ΨCD，网络中各边的权重的分布函数见表 2．求距离节点 A最近的3个节点．

图2 5节点不确定随机网络Fig. 2 Uncertain random network with 5 nodes

表2 图2网络中各边的权重的分布函数Tab. 2 Distribution function of the edge’s weight of figure 2

能够得到任意两点间的路径长度机会分布函数

其中F( x,yij,(i,j)∈R)由它的逆不确定分布确定：

当机会测度α＝0.9时，计算出任意两点间的最小路径长度，计算结果见表3．

表3 α＝0.9时节点间路径长度Tab. 3 Path length between nodes when α＝0.9

当机会测度α＝0.8时，计算出任意两点间的最小路径长度，计算结果见表4．

表4 α＝0.8时节点间路径长度Tab. 4 Path length between nodes when α＝0.8

所以，当机会测度α＝0.9，k＝3时，距离节点A最近的 3个点分别为 E、B、C．当机会测度α＝0.8，k＝3时，距离节点A最近的3个点分别为E、B、D．

当机会测度变化时，查询到的最短路径节点也可能发生变化，所以需要根据现实需求来指定机会测度，以得到预期结果．

3 结 语

本文提出了不确定随机网络的 Top-k最近节点查询问题，并使用机会理论求解该问题，设计不确定随机网络在一定机会测度条件下的 Top-k查询算法．此算法能正确求解不确定随机网络的Top-k查询问题，在网络节点数目较小、不确定随机分布较简单时的效率较高；一旦网络节点数目众多、网络非常复杂时，则计算的时间复杂度会较高．如何对算法进行改进，以提高算法的计算效率是下一步的研究方向．