仲 悅，杜 明，周軍鋒

(東華大學(xué)，上海 201620)

0 引言

k步可達(dá)查詢用于研究在給定的數(shù)據(jù)圖上，起始點(diǎn)u是否能在路徑長(zhǎng)度不大于k的前提下到達(dá)目標(biāo)頂點(diǎn)v。該研究有著廣泛的用途[1-3]，例如在人際關(guān)系網(wǎng)絡(luò)圖[4]中，查詢兩個(gè)人能否通過(guò) k個(gè)中間好友構(gòu)成熟人關(guān)系；道路網(wǎng)絡(luò)[5]中，用以查詢用戶是否可以從一個(gè)起點(diǎn)經(jīng)過(guò)k條道路到達(dá)目的地等。

目前已有的 k步可達(dá)查詢研究都是基于確定圖[6-10]，然而不確定圖[11]在實(shí)際生活中隨處可見(jiàn)，此時(shí)兩個(gè)實(shí)體之間的聯(lián)系的強(qiáng)弱程度表現(xiàn)為邊上的概率權(quán)值。例如，在道路網(wǎng)絡(luò)中時(shí)常會(huì)出現(xiàn)擁堵的情況，而擁堵的嚴(yán)重程度可以用概率來(lái)刻畫，從而導(dǎo)致本來(lái)可達(dá)的路徑暫時(shí)性不可達(dá)；以及路由網(wǎng)絡(luò)中，傳感器測(cè)量誤差導(dǎo)致兩個(gè)路由之間的信號(hào)不穩(wěn)定也會(huì)產(chǎn)生不確定的邊。當(dāng)給定一個(gè)不確定圖，k步可達(dá)查詢不但要求兩點(diǎn)間可達(dá)，而且還要求出可達(dá)的概率。最樸素的方法是枚舉所有的可能世界及其出現(xiàn)概率，接著計(jì)算每一個(gè)可能世界上u到v的可達(dá)情況，將結(jié)果相加。而每一個(gè)可能世界由于邊的出現(xiàn)情況不同，無(wú)法用預(yù)先處理的索引對(duì)不同的可能世界進(jìn)行查詢。一個(gè)n條邊的不確定圖有2n個(gè)可能世界，呈指數(shù)級(jí)。因此，即使該方法能得到最精確的結(jié)果，當(dāng)數(shù)據(jù)圖達(dá)到比較大的規(guī)模后，這種枚舉法顯然無(wú)法進(jìn)行，不具有擴(kuò)展性。

針對(duì)上述問(wèn)題，本文提出一種兩階段查詢方法，用于加速不確定圖上k步可達(dá)查詢的處理。其基本思想是：對(duì)可達(dá)和不可達(dá)的查詢基于不同索引分別處理。對(duì)不可達(dá)查詢，提出基于頂點(diǎn)覆蓋的高效索引來(lái)快速檢測(cè)是否k步不可達(dá)。對(duì)可達(dá)查詢，構(gòu)建位向量索引提前存儲(chǔ)可能世界來(lái)加速判斷。其總體思想是根據(jù)大數(shù)定律用抽樣近似法進(jìn)行計(jì)算，再用較小的內(nèi)存提前存儲(chǔ)抽樣結(jié)果。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文提出的索引和查詢方法 kRP的高效性。

1 問(wèn)題定義及相關(guān)工作

1.1 問(wèn)題定義

給定一個(gè)有向無(wú)環(huán)不確定圖G=(V,E,P)，其中V是圖中所有頂點(diǎn)的集合，E是圖中邊的集合，(u,v)表示從頂點(diǎn)u出發(fā)到頂點(diǎn)v有一條邊，在有向圖中(u,v)和(v,u)是兩條不同的邊，P是所有邊上概率的集合，且P={pi|0＜pi≤1，pi為第i條邊上的概率權(quán)值}。

以下介紹不確定圖、可能世界等相關(guān)定義及問(wèn)題的定義。

定義 1 不確定圖在圖中，邊上有權(quán)值，權(quán)值范圍在(0,1)區(qū)間內(nèi)，且權(quán)值表達(dá)的含義為該邊出現(xiàn)的概率，將這樣的圖表示為G=(V,E,P)，如圖1。

圖1 不確定圖GFig. 1 Uncertain graph G

定義2 可能世界對(duì)于不確定圖G=(V,E,P)，若一個(gè)確定圖 G′=（V′,E′）滿足：（1）V′?V；（2）E′?E，則G′為G的一個(gè)可能世界。當(dāng)V′=V且E′=E的時(shí)候，G′稱為 G的完全圖。圖2是圖1的兩個(gè)可能世界。

圖2 不確定圖G的兩個(gè)可能世界Fig.2 Possible Worlds of Uncertain Graph G

定義3 k步可達(dá)在一個(gè)確定圖上，給定頂點(diǎn)u和頂點(diǎn)v，存在一條從u到v的路徑且路徑上的邊數(shù)不大于k，則稱u到v在k步以內(nèi)可達(dá)，結(jié)果為TRUE或FALSE。

問(wèn)題定義 給定一個(gè)不確定圖G、頂點(diǎn)u和頂點(diǎn)v，以及步數(shù)約束k，求u到v在k步以內(nèi)可達(dá)的概率值。

1.2 相關(guān)算法

1.2.1 確定圖上k步索引

確定圖上的 k步可達(dá)研究目前已經(jīng)有不少算法，文獻(xiàn)[7]提出了一種在頂點(diǎn)覆蓋集上建立路徑信息的索引?；舅枷胧请S機(jī)選取一條邊，將邊兩端的頂點(diǎn)都加入到覆蓋集C中，刪除這兩個(gè)頂點(diǎn)的所有出邊和入邊，再重新隨機(jī)選取一條邊，重復(fù)以上操作直到圖中沒(méi)有剩余的邊，然后在覆蓋集上建立k步以內(nèi)的路徑傳遞閉包。

由于索引是在覆蓋集的基礎(chǔ)上構(gòu)建的，因此查詢可以分為三種情況，分別是（1）u和v都是覆蓋集C中的頂點(diǎn)，此時(shí)只要查詢索引中u到v是否 k步可達(dá)就能直接得出結(jié)果；（2）起始點(diǎn) u是覆蓋集C中的頂點(diǎn)而目標(biāo)頂點(diǎn)v不在覆蓋集內(nèi)，這種情況下把問(wèn)題轉(zhuǎn)換為是否存在一個(gè)頂點(diǎn)w，且w是v的入結(jié)點(diǎn)，滿足u到w的距離不大于k-1（u不在覆蓋集中且 v在覆蓋集中的情況類似，不再贅述）；（3）u、v都不在覆蓋集里，此時(shí)查詢能否存在w1和w2，且w1是u的出結(jié)點(diǎn)，w2是v的入結(jié)點(diǎn)，滿足w1到w2的距離不大于k-2。

這種索引方法存在規(guī)模大、效率低兩個(gè)問(wèn)題，覆蓋集的大小直接影響了索引的大小和性能，然而對(duì)于覆蓋集的選取過(guò)于隨機(jī)性，導(dǎo)致生成的索引每次都不同。并且，該方法沒(méi)有考慮邊的不確定性，只能運(yùn)用在確定圖上。

1.2.2 MC抽樣法

在不確定圖中進(jìn)行蒙特卡洛（Monte Carlo）抽樣[12-13]是求解可達(dá)性問(wèn)題的一種基本方法，主要思想如下：從起始點(diǎn)u出發(fā)BFS遍歷進(jìn)行不同可能世界的抽樣，只有當(dāng)邊(u,w)存在時(shí)，才把頂點(diǎn)w加入BFS的運(yùn)算隊(duì)列中。在隊(duì)列為空前，如果找到了目標(biāo)頂點(diǎn)v，則該可能世界中兩者可達(dá)，繼續(xù)下一次的圖抽樣和可達(dá)判斷。最終的結(jié)果為

1.2.3 其他方法

YILDIRIM在文獻(xiàn)[1]中提出GRAIL算法進(jìn)行可達(dá)性查詢，首先用不同遍歷方式生成d個(gè)區(qū)間標(biāo)簽加速不可達(dá)判斷，對(duì)于使用標(biāo)簽會(huì)產(chǎn)生誤判的查詢對(duì)，提出使用特例列表進(jìn)行記錄，減少查詢時(shí)的遍歷操作。

文獻(xiàn)[2]提出的 BFSI-B將查詢分為可達(dá)和不可達(dá)進(jìn)行處理，先構(gòu)建深度優(yōu)先生成樹(shù)，再基于樹(shù)利用區(qū)間標(biāo)簽判斷可達(dá)性，如果滿足區(qū)間包含要求，則計(jì)算兩頂點(diǎn)在樹(shù)中的層數(shù)差是否不大于k，從而得出k步可達(dá)查詢結(jié)果。

Yano等人在文獻(xiàn)[9]中提出 PLL算法，該方法為每個(gè)頂點(diǎn) u建立inLabel和outLabel兩組標(biāo)簽，分別用來(lái)記錄能到達(dá)u的頂點(diǎn)和距離以及從u出發(fā)可達(dá)的頂點(diǎn)和距離。當(dāng)查詢時(shí)只需要求起始點(diǎn)的 outLabel與目標(biāo)頂點(diǎn)的 inLabel中的交集頂點(diǎn)，通過(guò)判斷兩段距離相加之和與k的大小關(guān)系進(jìn)行判斷。

2 兩階段求解算法

對(duì)于給定兩點(diǎn)u和v的k步可達(dá)查詢，基本方法是從u出發(fā)，進(jìn)行N次抽樣，統(tǒng)計(jì)這些可能世界中既滿足可達(dá)又滿足k步的樣本個(gè)數(shù)，除以N值得到結(jié)果。這種方法存在大量冗余計(jì)算。例如，在圖3給定的有向無(wú)環(huán)不確定圖中求頂點(diǎn)v0到頂點(diǎn)v1的3步可達(dá)概率，按照以上方法，需要從頂點(diǎn) v0出發(fā)對(duì)邊依次進(jìn)行抽樣。然而從頂點(diǎn)v0出發(fā)，無(wú)論怎么抽樣都不可能到達(dá)頂點(diǎn)v1。事實(shí)上，在這種無(wú)法k步可達(dá)的情況下直接抽樣毫無(wú)意義。對(duì)于該問(wèn)題，本文提出結(jié)點(diǎn)覆蓋索引快速判斷不可達(dá)情況，從而能夠避免抽樣的昂貴代價(jià)。另外，對(duì)于可能到達(dá)的情況，本文提出高效的索引來(lái)加速查詢處理。下面分別進(jìn)行介紹。

圖3 有向無(wú)環(huán)不確定圖Fig.3 Directed Acyclic Uncertain Graph G

2.1 頂點(diǎn)覆蓋索引

本文首先在不確定圖對(duì)應(yīng)的完全圖上構(gòu)建頂點(diǎn)覆蓋集，接著基于覆蓋集中的頂點(diǎn)構(gòu)建k步索引，用來(lái)判斷給定查詢是否能在確定圖上k步可達(dá)。只有在確定圖上k步可達(dá)的前提下，才需要計(jì)算它的可達(dá)概率，否則無(wú)需進(jìn)行抽樣操作。和k-reach算法構(gòu)造覆蓋集的方法不同：k-reach是通過(guò)隨機(jī)選邊的方式來(lái)構(gòu)造覆蓋集，然后計(jì)算覆蓋集中兩兩頂點(diǎn)之間的最短路徑。

本文在構(gòu)建索引時(shí)選用的邊并非隨機(jī)抽取，而是優(yōu)先選擇度較大的頂點(diǎn)加入到覆蓋集。因?yàn)殡S機(jī)取邊的操作不僅會(huì)導(dǎo)致每次生成的頂點(diǎn)覆蓋集和索引都不一樣，索引效果也無(wú)法保證。

例如，用 k-reach算法對(duì)圖 3中不確定圖 G的完全圖進(jìn)行頂點(diǎn)覆蓋計(jì)算的可能情況如下。假設(shè)第一次隨機(jī)取邊結(jié)果為 v1-＞v2，將頂點(diǎn) v1和頂點(diǎn)v2加入結(jié)點(diǎn)覆蓋集C，刪除頂點(diǎn)v1和頂點(diǎn)v2的所有鄰邊，即邊 v1-＞v4、v0-＞v2、v2-＞v3和v2-＞v4。第二次隨機(jī)取邊 v4-＞v7，相應(yīng)的將頂點(diǎn)v4和頂點(diǎn)v7加入覆蓋集C，并刪除鄰邊v4-＞v6。若第三次和第四次隨機(jī)取到的邊分別為 v6-＞v8和v5-＞v9，那么此次求解覆蓋集的過(guò)程如表1所示?？梢钥吹阶罱K求得的覆蓋集C仍有8個(gè)頂點(diǎn)，對(duì)圖的壓縮效果較差。

表1 求解覆蓋集過(guò)程Tab.1 The progress of computing vertex cover

但是如果按照大度頂點(diǎn)進(jìn)行求解的話，能獲得更小的頂點(diǎn)覆蓋集，生成的索引在查詢時(shí)也更高效，具體操作如下。首先選取度最大的頂點(diǎn)，即頂點(diǎn) v2，刪除 v2的鄰邊。然后選取當(dāng)前度最大的頂點(diǎn) v4，刪除 v4的鄰邊。第三步選擇剩余圖中度最大的v8，最后選擇頂點(diǎn)v5?？梢?jiàn)，用這四個(gè)頂點(diǎn)就能構(gòu)成原圖的頂點(diǎn)覆蓋集，比隨機(jī)選邊的方式減少了一半的頂點(diǎn)規(guī)模。

圖4 完全圖的kR+索引Fig.4 The kR+ index

關(guān)于索引構(gòu)建的具體代碼設(shè)計(jì)如下。

算法1kR+(完全圖G=(V,E))

輸入：完全圖G=(V,E)

輸出：基于頂點(diǎn)覆蓋集VC的索引kR+

算法1用來(lái)構(gòu)建完全圖上的索引，加速判斷k步不可達(dá)的情況。第 1～7行按照上述大度頂點(diǎn)的方法構(gòu)建頂點(diǎn)覆蓋集，第1行初始化頂點(diǎn)覆蓋集VC為空集，第2行判斷是否有剩余邊，|E|表示邊數(shù)，第 3行選擇當(dāng)前度最大的頂點(diǎn)賦給 u，在第4行加入覆蓋集VC，第5～6行刪除u的所有鄰邊并將鄰接點(diǎn)的度都減去一。第8～11行基于頂點(diǎn)覆蓋集構(gòu)造k步索引，對(duì)于頂點(diǎn)u和頂點(diǎn)v，若u能在k步以內(nèi)到達(dá)v，則給邊(u,v)賦予權(quán)值，表示路徑步數(shù)，否則不建立邊。最后生成kR+索引。

查詢時(shí)，如查詢頂點(diǎn)v1到頂點(diǎn)v5是否3步可達(dá)，由于v1不在覆蓋集內(nèi)而v5在覆蓋集內(nèi)，則問(wèn)題轉(zhuǎn)換為查詢頂點(diǎn)v1的出結(jié)點(diǎn)到頂點(diǎn)v5是否2步可達(dá)。頂點(diǎn)v1的出結(jié)點(diǎn)為v2和v4，由kR+索引查詢可知v2到v5在2步內(nèi)可達(dá)，因此得出結(jié)論v1到v5可以3步到達(dá)。

2.2 基于路徑的提前抽樣

本文采用文獻(xiàn)[14]中提出的離線抽樣思想，把N個(gè)可能世界提前進(jìn)行抽樣并且以位向量[15]的索引形式存放在邊上。邊存在時(shí)記為 1，不存在記為0，第i個(gè)值表示在第i個(gè)可能世界上該邊的存在與否，每一條邊都有一個(gè)N大小的位向量，如[01100]可以看作5個(gè)抽樣圖中某一條邊的出現(xiàn)情況，該邊在第二、第三個(gè)可能世界上存在。由于該索引只需要0和1兩種值，因此可以采用C++中STL容器bitset或者二進(jìn)制int的存儲(chǔ)方式，從而節(jié)省索引所占內(nèi)存，時(shí)間復(fù)雜度為O(K|E| )，其中N是抽樣個(gè)數(shù)，|E|是邊數(shù)。

求解不確定圖上兩點(diǎn)間 k步可達(dá)概率的一個(gè)重要前提是它們之間能夠可達(dá)，而這一點(diǎn)可以用完全圖上的頂點(diǎn)覆蓋索引進(jìn)行判斷。倘若在完全圖上無(wú)法滿足k步可達(dá)，那么在任何一個(gè)可能世界中都不存在符合要求的路徑，此時(shí)查詢結(jié)果為0.如果完全圖的查詢結(jié)果為TRUE，再通過(guò)路徑枚舉剪枝可能世界中的邊，縮小查詢范圍。

例如，在圖3上求v2-＞v8在3步內(nèi)可達(dá)概率，有 v2-＞v3-＞v8 和 v2-＞v4-＞v6-＞v8 兩條路徑。此時(shí)看 v2-＞v3和 v3-＞v8這兩條邊的第 1位，只有兩者都為 1的時(shí)候這條路徑才完整存在并且滿足 3步可達(dá)，此時(shí)不再需要驗(yàn)證 v2-＞v4-＞v6-＞v8 路徑，只有在前一條路徑不符合要求時(shí)才進(jìn)行第二條路徑的查詢。

本文提出枚舉路徑的時(shí)候可以采用 kDFS的方式，求解的如果是k步可達(dá)問(wèn)題，則用一個(gè)大小為k+1的棧，把起始點(diǎn)壓入棧中，如果存在未被訪問(wèn)過(guò)的鄰居頂點(diǎn)就依次入棧。與DFS不同的是該棧有固定大小，如果棧滿時(shí)還未到達(dá)目標(biāo)頂點(diǎn)，則需先彈出棧頂元素后再入棧其余頂點(diǎn)，直到?？?。kDFS的過(guò)程中若遇到了目標(biāo)頂點(diǎn)，就把棧中所有元素記錄下來(lái)，作為一條可能路徑，該方法的時(shí)間復(fù)雜度為O(|Gk(u) |)，即從源頂點(diǎn) u 出發(fā)k步內(nèi)可以到達(dá)的頂點(diǎn)個(gè)數(shù)。

2.3 查詢算法

算法2給出了在不確定圖G上查詢兩點(diǎn)間k步可達(dá)概率的kRP方法，設(shè)計(jì)代碼如下。

算法2 kRP(u,v,k,N)

輸入：起始點(diǎn)u，目標(biāo)頂點(diǎn)v，步數(shù)k，抽樣個(gè)數(shù)N

輸出：u到v在k步內(nèi)可達(dá)的概率

第一行中success用來(lái)計(jì)數(shù)可能世界里k步可達(dá)的數(shù)量。第2行是在生成的頂點(diǎn)覆蓋索引上進(jìn)行查詢，若u不在覆蓋集內(nèi)，則轉(zhuǎn)換為u的出結(jié)點(diǎn)與v的k-1步查詢，v不在覆蓋集內(nèi)的情況不再贅述。如果該步驟判斷結(jié)果為 TRUE，則用固定大小的棧執(zhí)行深度優(yōu)先遍歷kDFS枚舉u到v的k步路徑。第5～9行，在預(yù)先存儲(chǔ)的N個(gè)可能世界中進(jìn)行查詢，當(dāng)路徑存在且查詢結(jié)果為TRUE時(shí)，給計(jì)數(shù)器 success的值增加1。第10行用可達(dá)的抽樣圖個(gè)數(shù)除以總的個(gè)數(shù)N，即可得到概率結(jié)果。

3 實(shí)驗(yàn)分析

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

本文實(shí)驗(yàn)所使用的硬件平臺(tái)是Intel Core i7，主頻為2.60 GHz的CPU，RAM內(nèi)存為8 GB，操作系統(tǒng)為 Windows10 64位系統(tǒng)。代碼用 C++實(shí)現(xiàn)，使用基礎(chǔ)BFS抽樣法進(jìn)行比較。查詢的距離k取值為3，抽樣個(gè)數(shù)N為1000個(gè)，查詢對(duì)數(shù)100對(duì)，其中3步內(nèi)可達(dá)的頂點(diǎn)對(duì)數(shù)和不可達(dá)的頂點(diǎn)對(duì)數(shù)各占一半。

3.2 數(shù)據(jù)集

本文使用8個(gè)數(shù)據(jù)集對(duì)實(shí)驗(yàn)進(jìn)行驗(yàn)證，Amaze和 Kegg都是與生物基因相關(guān)的網(wǎng)絡(luò)圖；Human和 Pubmed描述的是蛋白質(zhì)網(wǎng)絡(luò)；Nasa是 XML文檔的數(shù)據(jù)集；Yago用來(lái)描述語(yǔ)義庫(kù)中的關(guān)系結(jié)構(gòu)；Arxiv來(lái)自文獻(xiàn)[16]；Web-Google是 Google網(wǎng)頁(yè)相關(guān)的數(shù)據(jù)集，具體信息見(jiàn)表 2，|V|表示頂點(diǎn)數(shù)，|E|表示邊數(shù)。邊上的概率權(quán)值用隨機(jī)數(shù)生成，取值為(0,1)的左開(kāi)右閉區(qū)間。查詢集用完全圖隨機(jī)生成 100對(duì)查詢對(duì)，3步可達(dá)與不可達(dá)的比例為1∶1。

表2 數(shù)據(jù)集Tab.2 Dataset

3.3 性能比較分析

3.3.1 索引大小

表 3展示了在不同數(shù)據(jù)集上構(gòu)造的索引大小，單位均為MB。其中，kR+是本文提出的用頂點(diǎn)覆蓋集構(gòu)造的k步路徑索引，bitEdge是提前抽樣N個(gè)可能世界后存儲(chǔ)在邊上的索引，此處N值是1000，total表示兩個(gè)索引相加后的大小?？梢钥闯鏊饕嫉膬?nèi)存都較小，即使是在幾十萬(wàn)頂點(diǎn)的圖上，也僅要117.553 MB。

表3 索引大小/MBTab.3 Inde x Size/MB

3.3.2 索引構(gòu)建時(shí)間

如表4所示，列出了構(gòu)造對(duì)應(yīng)索引所需的時(shí)間。在構(gòu)造bitEdge位向量索引時(shí)耗時(shí)較長(zhǎng)，因?yàn)樵摬襟E相當(dāng)于對(duì)每一條邊都預(yù)先抽樣了N次，優(yōu)點(diǎn)是在后續(xù)的查詢時(shí)，不論查詢對(duì)是多少，都無(wú)需再進(jìn)行額外的抽樣，且在查詢時(shí)可以直接得出結(jié)果。基于頂點(diǎn)覆蓋構(gòu)造的 kR+索引不僅消耗時(shí)間少，還能加快處理不可達(dá)查詢。

表4 索引構(gòu)建時(shí)間/msTab.4 Index Building Time/ms

3.3.3 查詢時(shí)間

由于樸素抽樣法中，對(duì)于每一組查詢對(duì)，都需要從起始點(diǎn)開(kāi)始向外BFS尋找目標(biāo)頂點(diǎn)，且找到后還需要判斷兩個(gè)頂點(diǎn)之間的最短距離是否滿足 k步可達(dá)，消耗了極大的時(shí)間。如果u不可達(dá)v或者可達(dá)步數(shù)超過(guò)k時(shí)，更是浪費(fèi)了N次的BFS遍歷。

而本文提出的kRP算法先判斷了查詢是否滿足可達(dá)和k步兩個(gè)條件，又枚舉出路徑縮小了需要查詢的邊數(shù)，剪枝了不在路徑上的邊，查詢的時(shí)候通過(guò)讀取位向量就可以直接得出結(jié)果。當(dāng)一條邊在多次查詢中用到的時(shí)候，也不需要進(jìn)行重復(fù)抽樣，極大地縮短了查詢時(shí)間。查詢100對(duì)頂點(diǎn)對(duì)的時(shí)間結(jié)果如表5所示，可見(jiàn)樸素的抽樣法耗費(fèi)了大量時(shí)間在冗余遍歷上，只有在數(shù)據(jù)集nasa上，使用本文所提方法的構(gòu)建索引時(shí)間超出了樸素方法的時(shí)間，原因是該數(shù)據(jù)集的出度較小。而其余7個(gè)數(shù)據(jù)集中，構(gòu)建索引的時(shí)間都遠(yuǎn)遠(yuǎn)小于直接抽樣所耗費(fèi)的時(shí)間，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提出的kRP算法的有效性。

表5 查詢時(shí)間/msTab.5 Query Time/ms

4 結(jié)論

本文分析了不確定圖上的 k步可達(dá)近似算法，即樸素抽樣的BFS方法，并針對(duì)該方法中直接抽樣過(guò)于耗時(shí)的問(wèn)題，提出將查詢分為兩種情況進(jìn)行不同的處理。首先基于完全圖的頂點(diǎn)覆蓋集構(gòu)建了k步可達(dá)索引，其中在求解覆蓋集時(shí)按照頂點(diǎn)度從大到小的順序選擇頂點(diǎn)加入覆蓋集，從而縮小覆蓋集的規(guī)模。用索引判斷出無(wú)法k步可達(dá)的頂點(diǎn)對(duì)，直接得出可達(dá)概率為 0，對(duì)這些查詢不再進(jìn)行后續(xù)抽樣計(jì)算。對(duì)于可以k步可達(dá)的查詢，本文提出基于路徑來(lái)減少抽樣時(shí)的邊數(shù)，再用位向量的索引方式提前存儲(chǔ)抽樣圖例。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提方法的高效性。