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

黃冬梅　鄧　斌　趙丹楓

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

?

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

黃冬梅鄧斌趙丹楓

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

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

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

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

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

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

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

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

3) 進行實驗證明查詢算法的準確性和高效性。

1基本定義

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

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

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

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

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

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

圖1中，查詢源點為點A，點C與D到源點A的路徑步都為2，所以同屬一個源頂?shù)讓?。同樣，點E與F同屬一個源頂點層。而點B與D屬于不同的源頂點層。

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

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查詢，給定一個帶權(quán)不確定圖G=(V，E，P，W)，一個查詢源點V0∈V，查詢目標個數(shù)k≤|E|，找到一個擁有k個元素的頂點集合Sk(V0)={v1,…,vk}，?Vi∈Sk(V0)，?Vu∈ESk(V0)，滿足條件的dW×P(Vi)≤dW×P(Vu)。

2SubDistK算法

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

2.1查詢定理

定理1鄰步定理，帶權(quán)不確定圖G=(V，E，P，W)，查詢源點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表明與查詢源點的連接路徑中，兩個相鄰頂點中路徑步越長，則ProWeiDist距離越大。

定理2層次局部性定理，給定帶權(quán)不確定圖G=(V，E，P，W)，查詢源點V0，如果存在兩個源頂點層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)不確定圖中的兩個相鄰源頂點層，外層的層距離半徑要大于里層。

2.2方法概述

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

2.3算法步驟

算法1SubDistK

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

查詢源點V0∈V

參數(shù)k≤|E|

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

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

① L=0，S=?;

/*初始化訪問標識*/

② L++; visited=false;

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

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

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

④ while(|σL|+Sum

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

⑤ for(Vi∈σL)

/*頂點加入集合S*/

⑥ insertTo(S，Vi)；

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

⑦ OpcWeiDist；

⑧ visited=true;

⑨ end for

⑩ /*增加路徑步*/

/*S按照距離頂點進行排序*/

算法2OpcWeiDist

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

輸出：dW×P(V0, Vi)

/*計算路徑步*/

① P=L(V0, Vi)

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

② switch(P)

/*頂點直接相連*/

③ case 1:

/*頂點間接相連*/

⑤ case n>1:

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

/*頂點不相連*/

⑦ case ∞：

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

⑨ end switch

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

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

2.4實例分析

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

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

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

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

3算法優(yōu)化

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

3.1優(yōu)化方法

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

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

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

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

3.2優(yōu)化算法

算法3ImpSubDistK

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

查詢源點V0∈V

參數(shù)k≤|E|

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

/*初始化精簡子圖g*和相鄰點距離集合δ */

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

② L=0，S=?;

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

④ while(|σL|+Sum

⑤ for(Vi∈σL)

⑥ if(L==1)

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

⑧ else if

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

/*獲得相鄰邊距離并導入到距離集合中*/

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

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

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

4實驗

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

4.1實驗環(huán)境

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

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

4.2實驗方法

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

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

4.3結(jié)果分析

實驗一只有參數(shù)k變化時，目標頂點數(shù)與中間候選集合元素個數(shù)的比例變化。

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

圖5　隨k增加的目標頂點與候選集合的比例

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

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

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

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

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

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

5結(jié)語

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

參考文獻

[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.

中圖分類號TP311

文獻標識碼A

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

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