黃冬梅　鄧　斌　趙丹楓

(上海海洋大學(xué)信息學(xué)院　上海 201306)

?

帶權(quán)不確定圖的K最近鄰查詢算法

黃冬梅鄧斌趙丹楓

(上海海洋大學(xué)信息學(xué)院上海 201306)

摘要社交、移動(dòng)等復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)接入的不確定性給數(shù)據(jù)查詢處理帶來了新的挑戰(zhàn)。K最近鄰查詢是社交、移動(dòng)網(wǎng)絡(luò)中經(jīng)常用到的操作。已有的方法首先將網(wǎng)絡(luò)映射為不確定圖，然后，考慮邊只含有概率信息的情況。討論了K最近鄰查詢方法，沒有考慮權(quán)重信息，具有局限性。針對(duì)這個(gè)問題，定義了帶權(quán)不確定子圖和ProWeiDist距離，兼顧權(quán)重和概率兩個(gè)要素,提出了針對(duì)帶權(quán)不確定圖的K最近鄰查詢算法，并對(duì)算法進(jìn)行優(yōu)化。實(shí)驗(yàn)結(jié)果表明，SubDistK算法能有效地解決K最近鄰查詢問題。

關(guān)鍵詞復(fù)雜網(wǎng)絡(luò)不確定數(shù)據(jù)K最近鄰查詢帶權(quán)不確定圖子圖

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引言

快速發(fā)展的社交、移動(dòng)等網(wǎng)絡(luò)，由于噪聲控制、隱私保護(hù)等原因，產(chǎn)生了大量的不確定數(shù)據(jù)[1,2]。針對(duì)不確定數(shù)據(jù)的建模有關(guān)系型數(shù)據(jù)[3]、流數(shù)據(jù)、半結(jié)構(gòu)化數(shù)據(jù)、移動(dòng)對(duì)象數(shù)據(jù)等[4]。在蛋白質(zhì)網(wǎng)絡(luò)、社交領(lǐng)域中，圖模型更加適合不確定數(shù)據(jù)的建模研究[5,6]。其中，查詢對(duì)象作為圖的節(jié)點(diǎn)，對(duì)象之間的關(guān)系作為頂點(diǎn)之間的邊，數(shù)據(jù)間的不確定性成為邊的概率函數(shù)。在社交網(wǎng)絡(luò)中[7]，每位用戶構(gòu)成無向圖的一個(gè)頂點(diǎn)，用戶之間的關(guān)系構(gòu)成頂點(diǎn)之間的邊。在圖中的每條邊上加入概率信息構(gòu)成不確定圖，是不確定數(shù)據(jù)領(lǐng)域研究的一種常用方法。文獻(xiàn)[8]提出不確定圖的“可能世界”語義模型，不確定圖中每條邊都附帶一個(gè)介于0和1之間的實(shí)數(shù)，以表示邊存在的概率，邊的存在概率是相互獨(dú)立的。文獻(xiàn)[9]基于不確定圖數(shù)據(jù)庫(kù)提出概率top-k子圖匹配查詢，在查詢過程中，為附帶概率信息的鄰居子圖設(shè)計(jì)索引結(jié)構(gòu)，在索引結(jié)構(gòu)的基礎(chǔ)上進(jìn)行查詢。

K最近鄰查詢(KNN查詢)作為一種重要的查詢技術(shù)，旨在給定查詢點(diǎn)、查詢對(duì)象集合、范圍約束集合以及方向，找到與查詢點(diǎn)距離最近的k個(gè)對(duì)象[10-12]。針對(duì)不確定數(shù)據(jù)的K最近鄰查詢得到了國(guó)內(nèi)外越來越多人的研究[13-20]。文獻(xiàn)[13]針對(duì)蛋白質(zhì)網(wǎng)絡(luò)定義了三種衡量遠(yuǎn)近的距離概念，分別為中位距離、大多數(shù)距離和期望可信賴距離，應(yīng)用KNN查詢找到相互作用關(guān)系密切的蛋白質(zhì)群。文獻(xiàn)[14]在可能世界語義基礎(chǔ)上，提出SimRank度量方法，解決由于不確定圖動(dòng)態(tài)演變導(dǎo)致的求k個(gè)近鄰開銷過大的問題。文獻(xiàn)[15]定義最短距離概念，提出基于子圖擴(kuò)展的處理算法。

目前對(duì)不確定圖的KNN查詢研究還主要局限于不確定圖只含有概率信息的情況，沒有考慮到權(quán)重因素。在復(fù)雜網(wǎng)絡(luò)如社交網(wǎng)絡(luò)中，僅僅用傳統(tǒng)的不確定圖來定義是不恰當(dāng)?shù)?。例如，交友網(wǎng)站的好友推薦系統(tǒng)中，用戶代表圖的節(jié)點(diǎn)，系統(tǒng)根據(jù)用戶的籍貫、學(xué)校、職業(yè)、興趣等因素評(píng)估用戶間的親密關(guān)系，這種好友關(guān)系存在的可能性是不確定的，在圖中用頂點(diǎn)間邊的概率表示。但是，用戶在一段時(shí)間內(nèi)的關(guān)注和聯(lián)系次數(shù)是確定的，如果在推薦好友的過程中不考慮關(guān)注和聯(lián)系次數(shù)，查詢結(jié)果的準(zhǔn)確性會(huì)受到影響。因此，需要對(duì)傳統(tǒng)的不確定圖進(jìn)行改進(jìn)，加入權(quán)重的概念。在社交領(lǐng)域中，體現(xiàn)為用戶間一段時(shí)間的互動(dòng)次數(shù)；在蛋白質(zhì)交互領(lǐng)域中[13]，體現(xiàn)為之間產(chǎn)生化學(xué)反應(yīng)的次數(shù)。這樣，不確定圖中，邊不僅含有關(guān)系代表不確定性的概率，還有可以確定的互動(dòng)次數(shù)的權(quán)重。

本文針對(duì)帶有權(quán)重的不確定圖的查詢問題，進(jìn)行了以下三點(diǎn)研究：

1) 提出了一種帶權(quán)不確定圖上的KNN查詢：GrapKDist查詢；

2) 針對(duì)GrapKDist查詢提出了SubDistK算法，并進(jìn)行優(yōu)化；

3) 進(jìn)行實(shí)驗(yàn)證明查詢算法的準(zhǔn)確性和高效性。

1基本定義

定義1帶權(quán)不確定圖[13]，是一個(gè)四元組G=(V，E，P，W)，其中V是無向圖的頂點(diǎn)集合，E=V×V ,為邊的集合；P和W分別為邊的概率和權(quán)重函數(shù)。?e∈E，P(e)表示邊e的概率，W(e)表示邊e的權(quán)重。

圖1是一張帶權(quán)不確定圖，共有6個(gè)頂點(diǎn)和6條邊，每條邊附帶一個(gè)概率值和權(quán)重值。每條邊的概率和權(quán)重值相互獨(dú)立。

圖1　帶權(quán)不確定圖

定義2路徑步L(s, t)，帶權(quán)不確定圖G=(V，E，P，W)中任意兩個(gè)不同頂點(diǎn)s,t∈V，s與t的最短連接路徑中頂點(diǎn)組成的集合Ew，L(s, t)=|Ew|-1。

圖1中，L(A,C)=2，L(A,E)=3，在圖2中，由于點(diǎn)F與A無連接路徑，所以L(A,F)=∞。

定義3源頂點(diǎn)層σ，為一個(gè)頂點(diǎn)集合，給定帶權(quán)不確定圖G=(V，E，P，W)和查詢?cè)袋c(diǎn)V0，集合中任意兩個(gè)不同頂點(diǎn)s,t∈V，滿足L(V0, s)= L(V0, t)和|σ|<|E|。

圖1中，查詢?cè)袋c(diǎn)為點(diǎn)A，點(diǎn)C與D到源點(diǎn)A的路徑步都為2，所以同屬一個(gè)源頂?shù)讓印Ｍ瑯?，點(diǎn)E與F同屬一個(gè)源頂點(diǎn)層。而點(diǎn)B與D屬于不同的源頂點(diǎn)層。

定義4ProWeiDist距離，給定帶權(quán)不確定圖G=(V，E，P，W)，查詢?cè)袋c(diǎn)V0，任意頂點(diǎn)Vi∈VV0，dw×p(V0,Vi)衡量頂點(diǎn)Vi與源點(diǎn)V0之間的遠(yuǎn)近關(guān)系。距離計(jì)算方法如下：

ifL(V0,Vi)=1

ifL(V0,Vi)>1&&L(Vk,Vi)=1

ifL(V0,Vi)=∞

dW×P(V0,Vi)=∞

(1)

Ifm=0Rσm=1;

Ifm>0，V∈σm-1Vl∈σm

(2)

定義6帶權(quán)不確定圖的K最近鄰查詢：GrapKDist查詢，給定一個(gè)帶權(quán)不確定圖G=(V，E，P，W)，一個(gè)查詢?cè)袋c(diǎn)V0∈V，查詢目標(biāo)個(gè)數(shù)k≤|E|，找到一個(gè)擁有k個(gè)元素的頂點(diǎn)集合Sk(V0)={v1,…,vk}，?Vi∈Sk(V0)，?Vu∈ESk(V0)，滿足條件的dW×P(Vi)≤dW×P(Vu)。

2SubDistK算法

本節(jié)主要針對(duì)查詢問題提出兩個(gè)定理，并予以證明。依據(jù)定理設(shè)計(jì)查詢方法，在方法基礎(chǔ)上提出了兩個(gè)查詢算法。根據(jù)算法進(jìn)行了實(shí)例運(yùn)算。

2.1查詢定理

定理1鄰步定理，帶權(quán)不確定圖G=(V，E，P，W)，查詢?cè)袋c(diǎn)V0，?A,B∈V，且滿足L(V0,B)=L(V0,A)+1，則存在dW×P(B)>dW×P(A)。

證明：

由式(1)和條件L(V0,B)=L(V0,A)+1可得:

(3)

由0

(4)

由式(4)可得：

(5)

結(jié)合式(3)、式(5)可得：

dW×P(B)>dW×P(A)

(6)

定理1表明與查詢?cè)袋c(diǎn)的連接路徑中，兩個(gè)相鄰頂點(diǎn)中路徑步越長(zhǎng)，則ProWeiDist距離越大。

定理2層次局部性定理，給定帶權(quán)不確定圖G=(V，E，P，W)，查詢?cè)袋c(diǎn)V0，如果存在兩個(gè)源頂點(diǎn)層dW×P(si)>dW×P(ti)與σ2，σ1={s1,s2,…,si,…,sn}，σ2={t1,t2,…,ti,…,tm}，滿足條件L(V0,si)=L(V0,ti)+1，則存在R1>R2。

證明：

由條件L(V0,si)=L(V0,ti)+1和定理1可得：

dW×P(si)>dW×P(ti)

(7)

由式(7)可得：

(8)

式(8)結(jié)合式(2)可得：

R1>R2

層次局部性定理說明在帶權(quán)不確定圖中的兩個(gè)相鄰源頂點(diǎn)層，外層的層距離半徑要大于里層。

2.2方法概述

帶權(quán)不確定圖中邊同時(shí)含有權(quán)重和概率，鄰接矩陣不適于作為存儲(chǔ)結(jié)構(gòu)，因此用鄰接鏈表存儲(chǔ)網(wǎng)絡(luò)。把圖中所有頂點(diǎn)按照與查詢?cè)袋c(diǎn)的路徑步大小劃分為不同的源頂點(diǎn)層。 根據(jù)層次局部性定理，與查詢?cè)袋c(diǎn)關(guān)系密切的點(diǎn)一般位于路徑步較小的層次中。首先遍歷離源點(diǎn)步長(zhǎng)為1的層，對(duì)層中節(jié)點(diǎn)添加已訪問標(biāo)識(shí)；然后依次增加路徑步值，直到已訪問頂點(diǎn)總數(shù)與新源頂點(diǎn)層的和超過參數(shù)k；最后形成帶權(quán)不確定子圖，在子圖中，根據(jù)訪問標(biāo)識(shí)計(jì)和頂點(diǎn)路徑步的不同情況，調(diào)用式(1)計(jì)算ProWeiDist距離。依據(jù)距離大小選擇k個(gè)節(jié)點(diǎn)作為最后的結(jié)果。

2.3算法步驟

算法1SubDistK

輸入：帶權(quán)不確定圖G=(V，E，P，W)

查詢?cè)袋c(diǎn)V0∈V

參數(shù)k≤|E|

輸出：結(jié)果集合Sk

/*初始化路徑步L和中間候選集合S*/

① L=0，S=?;

/*初始化訪問標(biāo)識(shí)*/

② L++; visited=false;

/*遍歷總頂點(diǎn)數(shù)為Sum*/

③ 從V0遍歷圖G；Sum=0;

/*即將訪問的源頂點(diǎn)層σL和已遍歷數(shù)不超過k*/

④ while(|σL|+Sum

/*根據(jù)路徑步值來遍歷節(jié)點(diǎn)*/

⑤ for(Vi∈σL)

/*頂點(diǎn)加入集合S*/

⑥ insertTo(S，Vi)；

/*調(diào)用OpcWeiDist 算法*/

⑦ OpcWeiDist；

⑧ visited=true;

⑨ end for

⑩ /*增加路徑步*/

/*S按照距離頂點(diǎn)進(jìn)行排序*/

算法2OpcWeiDist

輸入：包含Vi，V0的帶權(quán)不確定子圖g

輸出：dW×P(V0, Vi)

/*計(jì)算路徑步*/

① P=L(V0, Vi)

/*根據(jù)頂點(diǎn)間路徑步值不同情況計(jì)算*/

② switch(P)

/*頂點(diǎn)直接相連*/

③ case 1:

/*頂點(diǎn)間接相連*/

⑤ case n>1:

/*遞歸調(diào)用OpcWeiDist 算法，L(Vk,Vi)=1*/

/*頂點(diǎn)不相連*/

⑦ case ∞：

⑧ dW×P(V0, Vi)=∞；

⑨ end switch

⑩ Output(dW×P(V0, Vi));

KNN查詢算法主要包括兩個(gè)算法，SubDistK算法旨在給定帶權(quán)不確定圖，查找滿足要求的k個(gè)節(jié)點(diǎn)。期間調(diào)用OpcWeiDist算法，計(jì)算被訪問節(jié)點(diǎn)與查詢?cè)袋c(diǎn)的ProWeiDist距離。 SubDistK算法的時(shí)間復(fù)雜度為O(N3)?？臻g復(fù)雜度為O(N)，OpcWeiDist算法的時(shí)間復(fù)雜度為O(N2)。

2.4實(shí)例分析

社交網(wǎng)絡(luò)中用戶關(guān)系網(wǎng)可以用帶權(quán)不確定圖表示：每一位用戶構(gòu)成圖中的一個(gè)頂點(diǎn)；用戶間的好友關(guān)系對(duì)應(yīng)頂點(diǎn)之間的邊，好友關(guān)系是相互的，所以邊不帶有方向；根據(jù)用戶的個(gè)人信息如職業(yè)、興趣愛好等不確定數(shù)據(jù)得出的好友關(guān)系成立的可能性表示為邊的概率值；把用戶在一段時(shí)間內(nèi)相互關(guān)注和聯(lián)系的次數(shù)作為邊的權(quán)重值。圖2是一張社交網(wǎng)絡(luò)用戶關(guān)系圖，P表示用戶間好友關(guān)系存在的概率，W表示用戶在一個(gè)月內(nèi)聯(lián)絡(luò)的次數(shù)。需要查找與用戶A親密度最高的4個(gè)用戶。

圖2　社交網(wǎng)絡(luò)用戶關(guān)系圖

根據(jù)查詢算法，與點(diǎn)A路徑步為1的節(jié)點(diǎn)為B、C，構(gòu)成第一個(gè)源頂點(diǎn)層σ1,dW×P(A,B)=2.60，dW×P(A,C)=2.05；由于|σ1|=2，小于查找目標(biāo)數(shù)，因此擴(kuò)大路徑步值，遍歷第二個(gè)源定點(diǎn)層中的節(jié)點(diǎn)D、F、L，dW×P(B，F(xiàn))=1.49，dW×P(B，L)=2.09，dW×P(C，F(xiàn))=3.50，dW×P(C，D)=1.29，經(jīng)過兩層遍歷，中間集合S已經(jīng)有5個(gè)元素，超過了查詢參數(shù)k，因此終止遍歷過程，獲得一張帶權(quán)不確定子圖，如圖3所示。計(jì)算集合中每個(gè)節(jié)點(diǎn)與源點(diǎn)的距離dW×P(A，B)=2.60，dW×P(A，C)=2.05，dW×P(A，D)=2.64，dW×P(A，F(xiàn))有兩個(gè)值，分別為7.18和3.87，取最小值3.87。dW×P(A，L)=5.43，選取距離值最小的四個(gè)節(jié)點(diǎn)，依次是C，B，D，F(xiàn)。因此得出結(jié)論與用戶A關(guān)系最近的用戶為用戶C，B，D，F(xiàn)。

圖3　社交網(wǎng)絡(luò)用戶關(guān)系子圖

3算法優(yōu)化

本節(jié)從空間復(fù)雜度和時(shí)間復(fù)雜度兩個(gè)方面對(duì)算法進(jìn)行優(yōu)化，提出精簡(jiǎn)帶權(quán)不確定子圖，用實(shí)例進(jìn)行優(yōu)化分析，并給出優(yōu)化后的算法。

3.1優(yōu)化方法

在空間復(fù)雜度方面，帶權(quán)不確定子圖用來存儲(chǔ)全部頂點(diǎn)和遍歷經(jīng)過的邊，節(jié)約了其他無用邊的存儲(chǔ)空間。但是在復(fù)雜網(wǎng)絡(luò)中，頂點(diǎn)的數(shù)量龐大。依據(jù)SubDistK算法，遍歷過程中沒有經(jīng)過的節(jié)點(diǎn)沒有成為查詢目標(biāo)的可能性，因此可以在子圖中刪除這些節(jié)點(diǎn)，極大地降低算法的空間復(fù)雜度。圖3的所有節(jié)點(diǎn)中，只有B、C、D、F、L是候選節(jié)點(diǎn)，其他節(jié)點(diǎn)都可以省去，形成精簡(jiǎn)帶權(quán)不確定子圖，如圖4所示。

圖4　社交網(wǎng)絡(luò)用戶關(guān)系精簡(jiǎn)子圖

在時(shí)間復(fù)雜度方面，由于查詢執(zhí)行時(shí)間主要在計(jì)算子圖中頂點(diǎn)與查詢?cè)袋c(diǎn)的ProWeiDist距離，圖的節(jié)點(diǎn)和邊都比較復(fù)雜，會(huì)出現(xiàn)多個(gè)節(jié)點(diǎn)共用一條邊的情況。在現(xiàn)實(shí)生活中，一個(gè)人成為多人的中間好友的情況是經(jīng)常存在的。在距離計(jì)算中，減少遍歷過程中重復(fù)邊的計(jì)算，簡(jiǎn)化計(jì)算過程，有利于降低算法的時(shí)間復(fù)雜度。

圖4中節(jié)點(diǎn)L、F在與A點(diǎn)的連接路徑中共用了A-B邊，節(jié)點(diǎn)D、F在與A點(diǎn)的連接路徑中共用了A-C邊。在計(jì)算L與A點(diǎn)的距離計(jì)算過程中，可以減少重復(fù)計(jì)算A-B邊距離的步驟。同樣dW×P(A,D)與dW×P(A,F)也可以利用之前計(jì)算得到的dW×P(A,C)，在第二部分的算法示例中，第一層遍歷的邊的最可能權(quán)重距離在第二層遍歷中都會(huì)用到，在應(yīng)用式(1)時(shí)可以利用。

3.2優(yōu)化算法

算法3ImpSubDistK

輸入：帶權(quán)不確定圖G=(V，E，P，W)

查詢?cè)袋c(diǎn)V0∈V

參數(shù)k≤|E|

輸出：結(jié)果集合Sk

/*初始化精簡(jiǎn)子圖g*和相鄰點(diǎn)距離集合δ */

① g*=(V*，E*，P*，W*)；V*= ?，E*=?；δ =?；

② L=0，S=?;

③ L++; visited=false; Sum=0;

④ while(|σL|+Sum

⑤ for(Vi∈σL)

⑥ if(L==1)

⑦ 應(yīng)用式(1);得dW*P(V0,Vi);

⑧ else if

⑨ ?Vk(Vk∈σL-1&&L(Vk,Vi)==1)

/*獲得相鄰邊距離并導(dǎo)入到距離集合中*/

⑩ dW×P(Vk,Vi)，insertTo(δ，dW×P(Vk,Vi));

/*把已訪問的節(jié)點(diǎn)信息加入到精簡(jiǎn)子圖中*/

ImpSubDistK算法是在SubDistK算法的基礎(chǔ)上進(jìn)行優(yōu)化，節(jié)省存儲(chǔ)空間，提高查詢效率。改進(jìn)后的算法空間復(fù)雜度為O(log2N)，時(shí)間復(fù)雜度為為O(N)。

4實(shí)驗(yàn)

實(shí)驗(yàn)部分利用社交網(wǎng)絡(luò)真實(shí)數(shù)據(jù)構(gòu)建帶權(quán)不確定圖，進(jìn)行多組實(shí)驗(yàn)，從三個(gè)方面驗(yàn)證算法的準(zhǔn)確度和效率，并分析實(shí)驗(yàn)結(jié)果。

4.1實(shí)驗(yàn)環(huán)境

為了證明SubDistK算法在GrapKDist查詢過程中的準(zhǔn)確性和高效性，本文以社交網(wǎng)絡(luò)中用戶關(guān)系網(wǎng)絡(luò)為帶權(quán)不確定圖原型，設(shè)計(jì)多組對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)采用ego-Facebook社交網(wǎng)絡(luò)數(shù)據(jù)。實(shí)驗(yàn)算法代碼采用C++編程語言編寫，程序運(yùn)行在3.2 GHz的雙核處理器上，實(shí)驗(yàn)平臺(tái)為Win7 64位系統(tǒng)，4 GB內(nèi)存。

實(shí)驗(yàn)數(shù)據(jù)為Facebook社交圈，包含4093個(gè)節(jié)點(diǎn)，88 234條邊。該無向圖出于隱私保護(hù)經(jīng)過匿名化處理，用戶ID用新的值代替，用戶間的個(gè)人特征也經(jīng)過預(yù)處理。例如“政治派別=民主黨”也統(tǒng)一標(biāo)識(shí)為“政治派別=A黨”，概率描述用戶間好友關(guān)系成立的可能性，在0~1之間；權(quán)重為兩個(gè)用戶一個(gè)月之內(nèi)彼此在對(duì)方主頁(yè)進(jìn)行關(guān)注和留言的次數(shù)總和。

4.2實(shí)驗(yàn)方法

實(shí)驗(yàn)對(duì)比主要從3個(gè)方面來驗(yàn)證GrapKDist查詢的準(zhǔn)確率和效率：目標(biāo)頂點(diǎn)數(shù)與查詢中間候選集合的比例隨參數(shù)k的變化、查詢遍歷的頂點(diǎn)數(shù)占總頂點(diǎn)數(shù)的比例隨參數(shù)k的變化、查詢執(zhí)行時(shí)間隨參數(shù)k的變化。

由于在查詢過程中，遍歷過的頂點(diǎn)會(huì)形成一個(gè)精簡(jiǎn)帶權(quán)不確定子圖，直到子圖里的頂點(diǎn)數(shù)量超過要查詢的頂點(diǎn)數(shù)k。并且目標(biāo)頂點(diǎn)包含在這個(gè)中間候選集合中，如果候選集合的元素越多，在里面挑選目標(biāo)對(duì)象的準(zhǔn)確性會(huì)越高，目標(biāo)對(duì)象被查詢遺漏的可能性也就越低。這樣，目標(biāo)頂點(diǎn)數(shù)k與中間候選集合元素個(gè)數(shù)的比例可以衡量算法的準(zhǔn)確度。如果，這個(gè)比例在隨著參數(shù)k的變化一直保持在一個(gè)預(yù)期的閾值之下，那么說明查詢算法的準(zhǔn)確率達(dá)到我們的期望。查詢過程中并不會(huì)遍歷圖中所有頂點(diǎn)，遍歷的頂點(diǎn)越多，要計(jì)算的ProWeiDist距離的次數(shù)就越多；算法執(zhí)行時(shí)間就越長(zhǎng)，所耗費(fèi)的計(jì)算開銷就越大；另外查詢?nèi)绻軌蛞砸?guī)模較小的中間候選集合就能找到目標(biāo)頂點(diǎn)，就省去了遍歷無效頂點(diǎn)的過程，減少了無效距離的計(jì)算，因此查詢執(zhí)行時(shí)間、查詢頂點(diǎn)數(shù)、與查詢頂點(diǎn)數(shù)占總頂點(diǎn)數(shù)的比例，這三個(gè)指標(biāo)可以衡量查詢算法的效率。

4.3結(jié)果分析

實(shí)驗(yàn)一只有參數(shù)k變化時(shí)，目標(biāo)頂點(diǎn)數(shù)與中間候選集合元素個(gè)數(shù)的比例變化。

實(shí)驗(yàn)設(shè)定帶權(quán)不確定圖的規(guī)模不變，逐漸擴(kuò)大查詢目標(biāo)個(gè)數(shù)k，從最初的查找4個(gè)對(duì)象頂點(diǎn)到最終的110個(gè)對(duì)象，前5次每次增加為4，后9次每次增加為10，總共測(cè)得14組比例數(shù)據(jù)，比例變化如圖5所示。從圖中我們可以得知，在目標(biāo)頂點(diǎn)個(gè)數(shù)比較少的時(shí)候，遍歷的層次沒有變化，候選集合中包含了要查詢的目標(biāo)頂點(diǎn)，集合中的無效頂點(diǎn)逐漸減少，所以前期比例呈線性增長(zhǎng)。當(dāng)k逐漸增加時(shí)，以前遍歷的層無法容納所有的目標(biāo)頂點(diǎn)，必須再向外訪問新的頂點(diǎn)層，中間候選集合中的無效頂點(diǎn)瞬間增多，所以比例會(huì)突然出現(xiàn)比較大的下降。之后中間集合又會(huì)保持穩(wěn)定，隨著k增加，無效頂點(diǎn)較少，比例增加。整個(gè)過程中比例的變化趨勢(shì)呈現(xiàn)鋸齒狀，線性增加然后大幅度下降再增加，周而復(fù)始。從實(shí)驗(yàn)結(jié)果得出，算法的準(zhǔn)確率會(huì)不斷變化，在k剛剛超出候選集合的頂點(diǎn)數(shù)即訪問新一層時(shí)的準(zhǔn)確率最高。

圖5　隨k增加的目標(biāo)頂點(diǎn)與候選集合的比例

實(shí)驗(yàn)二只有參數(shù)k變化時(shí)，算法遍歷頂點(diǎn)數(shù)以及與總頂點(diǎn)數(shù)比例的變化。

該實(shí)驗(yàn)設(shè)定圖頂點(diǎn)總數(shù)不變，當(dāng)逐漸增加查詢目標(biāo)數(shù)k時(shí)，計(jì)算算法遍歷過的頂點(diǎn)數(shù)占總頂點(diǎn)數(shù)的比例。結(jié)果如圖6所示，隨著參數(shù)k的增加，訪問的層次數(shù)也會(huì)增加，因此遍歷的頂點(diǎn)數(shù)增加。比例線呈現(xiàn)“階梯”狀，這是因?yàn)樵诓樵冎?，?huì)以源點(diǎn)為“中心”向外層次性遍歷頂點(diǎn)。在第一個(gè)頂點(diǎn)層中，雖然參數(shù)k增加了，但是訪問的層次卻依然保持不變，所以遍歷的頂點(diǎn)數(shù)沒有變化。隨著k的進(jìn)一步增加到16，訪問層次擴(kuò)大，中間候選集合的規(guī)模變大，所以遍歷頂點(diǎn)數(shù)會(huì)進(jìn)一步增多。從圖中我們可以看到，剛開始時(shí)，頂點(diǎn)數(shù)比例值保持在一個(gè)非常低的水平，這是由于開始階段查詢目標(biāo)數(shù)少，并且總頂點(diǎn)數(shù)量大。中間一段過程中，比例的增長(zhǎng)相對(duì)平緩，并且低于0.1，當(dāng)k增加到110時(shí)，比例也不會(huì)超過0.055。說明在執(zhí)行算法查詢過程中，從訪問頂點(diǎn)數(shù)比例來看，算法效率都保持在一個(gè)非常好的效果。

圖6　帶權(quán)不確定圖中訪問頂點(diǎn)占總頂點(diǎn)數(shù)的比例

實(shí)驗(yàn)三只有參數(shù)k變化時(shí)，算法執(zhí)行時(shí)間的變化。

查詢的執(zhí)行時(shí)間集中于頂點(diǎn)的遍歷和ProWeiDist距離的計(jì)算方面上。而遍歷的頂點(diǎn)數(shù)比例隨參數(shù)k的變化在實(shí)驗(yàn)二已經(jīng)得出。頂點(diǎn)之間距離的計(jì)算時(shí)間也與頂點(diǎn)數(shù)有關(guān)系。因此查詢執(zhí)行時(shí)間隨參數(shù)值k的變化趨勢(shì)會(huì)和頂點(diǎn)比例變化有聯(lián)動(dòng)效果。實(shí)驗(yàn)結(jié)果如圖7所示，曲線為算法優(yōu)化前后的執(zhí)行時(shí)間，當(dāng)參數(shù)k在16以內(nèi)時(shí)，形成的帶權(quán)不確定子圖所含的邊比較少，是一個(gè)稀疏圖，執(zhí)行時(shí)間因此相差不大。k增加時(shí)，隨著遍歷新的頂點(diǎn)層時(shí)，訪問頂點(diǎn)數(shù)突然增多，需要進(jìn)行的距離計(jì)算會(huì)大大增加，時(shí)間曲線有比較明顯的增大。在同一層遍歷頂點(diǎn)時(shí)，雖然增加k，但是時(shí)間增長(zhǎng)平緩。當(dāng)進(jìn)一步增加查詢目標(biāo)數(shù)時(shí)，曲線又會(huì)有一個(gè)比較大的提高。當(dāng)k數(shù)值增加到110以后，新訪問的層所包含的頂點(diǎn)數(shù)量巨大，所包含的邊非常多，形成了一個(gè)規(guī)模很大的帶權(quán)不確定子圖，因此執(zhí)行時(shí)間有大幅度的增長(zhǎng)。從實(shí)驗(yàn)結(jié)果得出，SubDistK算法在k在100以下時(shí)的運(yùn)算時(shí)間比較小，且優(yōu)化后的算法比優(yōu)化前執(zhí)行時(shí)間更短。

圖7　SubDistK算法隨參數(shù)k變化的執(zhí)行時(shí)間

5結(jié)語

本文針對(duì)復(fù)雜網(wǎng)絡(luò)中同時(shí)含有概率和權(quán)重的數(shù)據(jù)查詢問題，通過帶權(quán)不確定圖對(duì)數(shù)據(jù)進(jìn)行建模，定義了 GrapKDist查詢，提出了SubDistK算法，通過三組實(shí)驗(yàn)證明了算法的有效性，解決了帶權(quán)不確定圖上的K最近鄰查詢問題。不足在于算法在k值在大于100時(shí)效率有所下降，這也是今后的研究方向。

參考文獻(xiàn)

[1] Qiao Shaojie,Li Tianrui,Yang Yan.Managing uncertainty in web-based social networks[J].Intertional Journal of Uncertianty,Fuzziness and Knowledge-Based System,2012,20(1):147-158.

[2] Zhu Fangzhou,Li Guohui,Zhao Xiaosong,et al.Probabilistic nearest neighbor queries of uncertain data via wireless data broadcast[J].Peer-to-Peer Networking and Applications,2013,6(4):363-379.

[3] Lima D M,Rodrigues J F.DeGraph-based relational data visualization[C]//Proceedings of the International Conference on Information Visualisation,2013.

[4] Wang Yijie,Li Xiaoyong,Qi Yafei,et al.Uncertain data queries Technologies[J].Journal of Computer Research and Development,2012,49(7):1460-1466.

[5] Asthana S,King O D,Gibbons F D,et al.Predicting protein complex membership using probabilistic network reliability[J].Genome Research,2004,14(3):1170-1175.

[6] Wang D Z,Michelakis E,Garofalakis M,et al.Bayesstore:managing large uncertain data repositories with probabilistic graphical models[J].Proc of the VLDB Endowment,2008,1(1):340-351.

[7] Liben-Nowell D,Kleinberg J.The link prediction problem for social networks[J].Journal of the American Society for Information Science and Technology,2007,58(7):1019-1031.

[8] Zhang Haijie,Jiang Shouxu,Zou Zhaonian.An efficient algorithm for top-k proximity query on uncertain graphs[J].Chinese Journal of Computers,2011,34(10):145-156.

[9] Zhang Shuo,Gao Hong,Li Jianzhong,et al.Efficient query processing on uncertain graph databaes[J].Chinese Journal of Computers,2009,23(10):2066-2079.

[10] Huang Jianhua,Ding Jianrui,Liu Jiafeng,et al.Citation-knn algorithm based on locally-weighting[J].Journal of Electronics and Information Technology,2013,35(3):627-632.

[11] Zhang Shichao.Nearest neighbor selection for iteratively knn imputation[J].Journal of System and Software,2012,85(11):2541-2552.

[12] Jiang Liangxiao,Cai Zhihua,Wang Dianhong.Bayesian citation-knn with distance weighting[J].International Journal of Machine Learning and Cybernetics,2014,5(2):193-199.

[13] Potamias M,Bonchi F,Gionis A,et al.k-nearest neighbors in uncertain graphs[J].Proc of the VLDB Endowment,2010,3(1):997-1008.

[14] Zhang Yinglong,Li Cuiping,Chen Hong,et al.K-nearest neighbors in uncertain graph[J].Journal of Computer Research and Development,2011,48(10):1850-1858.

[15] Zhang Xu,He Xiangnan,Jin Cheqing,et al.Processing k-nearest neighbors query over uncertain graphs[J].Journal of Computer Research and Development,2010,3(1):997-1008.

[16] Sun Yongjiao,Dong Han,Yuan Ye,et al.Knn queries method on uncertain data over P2P networks[J].Journal of Northeastern University,2012,33(5):632-635.

[17] Bekales G,Soliman M A,Ilyas I F.Efficient search for the top-k probable nearest neighbors in uncertain databases[J].Proc of the VLDB Endowment,2008,1(1):326-339.

[18] Kriegel H P,Kunath P,Renz M.Probabilistic nearest-neighbor query on uncertain objects[C]//Proc of DASFAA.Berlin:Springer,2007:809-824.

[19] Lian X,Chen L.Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data[J].The VLDB Journal,2009,18(3):787-808.

[20] Cheng R,Chen L,Chen J,et al.evaluating probability threshold k-nearest-neighbor queries over uncertain data[C]//Proc of Int on Extending Database Technology:Advances in Database Technology(EDBT).New York: ACM,2009:672-683.

中圖分類號(hào)TP311

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.02.050

收稿日期：2014-06-26。國(guó)家自然科學(xué)基金項(xiàng)目(61272098)。黃冬梅，教授，主研領(lǐng)域：海洋大數(shù)據(jù)，WebGis等。鄧斌，碩士生。趙丹楓，講師。