陳 澤，丁琳琳，宋寶燕，王俊陸

（1.遼寧大學(xué) 信息學(xué)院，沈陽 110036；2.山東能源新汶礦業(yè)集團有限責(zé)任公司，山東 泰安 271200；3.東北大學(xué) 資源與土木工程學(xué)院，沈陽 110004）

0 概述

圖作為一種抽象的數(shù)據(jù)結(jié)構(gòu)，能夠有效描述現(xiàn)實中各類對象間的復(fù)雜關(guān)系［1-2］，并廣泛應(yīng)用于社交網(wǎng)［3］、智能交通網(wǎng)［4］與語義Web 分析［5］等領(lǐng)域。在圖結(jié)構(gòu)中，節(jié)點間的相似性度量是各類圖查詢處理的基礎(chǔ)［6］，且可利用得到的查詢結(jié)果對節(jié)點對間的相似程度進行分析。因此，節(jié)點相似性查詢是圖研究領(lǐng)域中的重要問題［7］。

隨著大數(shù)據(jù)［8］與信息技術(shù)［9］的應(yīng)用，圖中使用的數(shù)據(jù)規(guī)模逐漸增大，圖的節(jié)點與邊都隨著時間推移不斷發(fā)生動態(tài)變化［10-11］。因此，大規(guī)模動態(tài)圖上的節(jié)點相似Top-k 查詢成為圖研究領(lǐng)域中的熱點與難點問題［12］?，F(xiàn)有圖節(jié)點相似Top-k 查詢方法多數(shù)為迭代計算相似度方法［13］，在迭代過程結(jié)束前不能得出結(jié)果，造成系統(tǒng)資源浪費，且迭代計算可能造成次優(yōu)相似度累加結(jié)果優(yōu)于最優(yōu)解，從而導(dǎo)致查詢結(jié)果錯誤［14］。此外，迭代查詢方法通常需要遍歷全圖，未考慮到圖結(jié)構(gòu)發(fā)生動態(tài)變化時如何對查詢過程及結(jié)果進行更新維護［15］的問題。上述方法在小規(guī)模圖或靜態(tài)圖［16］上具有較高的查詢效率與準確度，但不能滿足大規(guī)模動態(tài)圖對相似查詢效率及準確度的要求。

本文提出一種基于PageRank 的節(jié)點相似Top-k查詢方法。該方法通過對PageRank 進行概率游走約束，避免了概率游走反復(fù)選取少數(shù)邊的情況，并實現(xiàn)將基大圖生成多個小規(guī)模單向圖。同時，結(jié)合Monte Carlo 模擬法思想，以Top-k 取值為約束條件，有效解決次優(yōu)相似度疊加問題，提高查詢效率。依據(jù)局部自適應(yīng)原則提出基大圖觸發(fā)更新策略和單向圖集聯(lián)動更新策略，從而解決查詢效率較低的問題。

1 相關(guān)工作

目前，國內(nèi)外研究人員針對圖節(jié)點相似Top-k 查詢方法的研究眾多。文獻［17］提出一種基于節(jié)點指紋信息進行相似性查詢的FR 方法，但因為處理節(jié)點指紋信息代價較大，所以該方法在大規(guī)模圖上的查詢效率較低。文獻［18］提出一種較為精確的迭代計算算法，但該算法在計算相似度的過程中需計算所有節(jié)點對的SimRank 相似度，存在計算代價過大的問題。文獻［19］構(gòu)建一種新的概率計算框架，該框架通過降維的方式能夠有效減少計算量，但在相似度計算中還存在冗余問題，導(dǎo)致查詢結(jié)果準確度不高。文獻［20］通過對SimRank 方法進行加權(quán)來衡量用戶對具體信息的偏好程度，從而實現(xiàn)相似推薦查詢，但該方法適用于小規(guī)模圖查詢，在大規(guī)模圖上存在計算權(quán)值及查詢對比代價過高的問題。文獻［21］提出一種KM 方法，它通過預(yù)計算節(jié)點對相似度的邊界來提高查詢效率，但是因為該方法需要進行大量預(yù)處理操作，且當圖更新時需要重新計算相似度邊界，所以其在動態(tài)圖上的查詢效率較低。文獻［22］提出基于SimRank 的概率游走算法，該算法對節(jié)點間相似度的計算表示進行改進，查詢效率較高，但它無法保證在動態(tài)圖上的查詢準確度。文獻［23］提出一種在異構(gòu)信息網(wǎng)絡(luò)中的相似性搜索方法，通過x-star 模式來實現(xiàn)相似性搜索，但該模式計算代價較高，且在動態(tài)圖上的查詢效率較低。文獻［24］提出基于有向圖的相似性度量方法，依據(jù)圖的結(jié)構(gòu)特征綜合性衡量相似性，但其處理過程復(fù)雜，不能適用于動態(tài)圖查詢。

本文對節(jié)點相似Top-k 查詢方法進行深入研究，并提出一種大規(guī)模動態(tài)圖概率游走約束的節(jié)點相似Top-k 查詢方法。該方法綜合考慮大圖的數(shù)據(jù)規(guī)模及圖動態(tài)變化時，對節(jié)點相似查詢效率及結(jié)果集準確度的影響。

2 概率游走約束的相似度累積查詢

大規(guī)模圖中游走步數(shù)的增大將會直接影響查詢效率，為降低基大圖節(jié)點相似度計算次數(shù)，避免Top-k 查詢中多個“遠關(guān)系”的疊加結(jié)果優(yōu)于“近關(guān)系”的問題，本文引入PageRank 概率游走機制，并提出利用單邊弱化因子對概率進行約束，將基大圖轉(zhuǎn)化為多個小規(guī)模單向圖，以k取值為約束條件來遞增游走步數(shù)，實現(xiàn)單向圖集上的節(jié)點相似Top-k 快速累積查詢。

2.1 PageRank 概率約束

定義1基大圖：假設(shè)Gr表示基大圖，即大規(guī)模動態(tài)圖，節(jié)點u為基大圖Gr中的節(jié)點，（u，v）表示基大圖Gr中的邊。

定義2單向圖：假設(shè)Gs表示基大圖中的單向圖，則且v至多取一個節(jié)點。其中，節(jié)點u為基大圖Gr中的節(jié)點，在單向圖Gs中，（u，v）表示節(jié)點u的唯一出邊。

當單向圖進行選取時，需要從基大圖中的查詢節(jié)點開始，從圖中查詢節(jié)點及其相關(guān)節(jié)點中隨機選出一條路徑進行迭代計算，滿足每個節(jié)點有且僅有一條出邊，但可以存在多條入邊的情況。為確保隨機選取的效率，本文引入PageRank 概率游走機制進行路徑選取，具體如式（1）所示：

其中，P（u）為節(jié)點u被訪問到的概率，d表示算法繼續(xù)訪問執(zhí)行的概率，N為基大圖中所有的節(jié)點數(shù)量，in（u）表示所有指向節(jié)點u的節(jié)點集合，out（v）表示節(jié)點v指向其他節(jié)點的集合。單向圖的大小可根據(jù)具體的Top-k 查詢條件及游走步數(shù)i來確定。圖1 為基大圖轉(zhuǎn)化為單向圖的示意圖。

圖1 單向圖轉(zhuǎn)化示意圖Fig.1 Schematic diagram of unidirectional graph conversion

從圖1 可知，通過概率游走得到的單向圖可有效降低圖規(guī)模。由于單向圖是在基大圖中通過概率游走機制選取的，若某個或某些節(jié)點的出邊數(shù)較少或只有一條出邊，則會導(dǎo)致對PageRank 概率游走進行選取時，每個單向圖中出現(xiàn)出邊的概率較大，進而在相似度計算時會反復(fù)疊加這些邊，直接影響查詢結(jié)果的準確度。

為避免上述問題，本文對單向圖的各條邊引入單邊弱化因子參量，并進行PageRank 的概率約束。其中，n為選取次數(shù)。將因子參量賦予給單向圖中的每條邊，若某條邊被選中的次數(shù)越多，則其對相似度計算的影響力下降越多，重復(fù)選中該邊的概率將會形成弱化趨勢。圖2 為單向圖集構(gòu)建示意圖。

圖2 單向圖集構(gòu)建示意圖Fig.2 Schematic diagram of unidirectional graphs construction

如圖2 所示，單向圖1 與單向圖2 均是由圖1 中基大圖通過弱化重復(fù)路徑約束生成的單向圖。以節(jié)點h為例，因為h只有一條出邊，所以生成的所有單向圖均含有邊（h，c）。在單向圖1 中，邊（h，c）的影響力為1，而在單向圖2 中，在單邊弱化因子的作用下，其影響力降至為1/2，這說明通過減少某一條邊的反復(fù)疊加，可有效降低對相似計算結(jié)果的影響。

2.2 節(jié)點相似Top-k 累積查詢

如果要找到查詢節(jié)點u的相似節(jié)點v，則需要找到節(jié)點u和節(jié)點v在j步概率游走內(nèi)的可能相遇節(jié)點。由于查詢游走步數(shù)較多，在基大圖上的遍歷查詢效率很低，因此本文基于Monte Carlo 模擬法思想，在整個單向圖集中選取若干個查詢節(jié)點u的j步隨機相遇節(jié)點，使用節(jié)點的累積相似度代替節(jié)點真實相似度。

假設(shè)弱單向圖集為Gs={Gs1，Gs2，…，Gsn}中的單向圖，且是相互獨立的隨機樣本，給基大圖G中的邊隨機分配權(quán)重值，則由大數(shù)定理可得：

由式（2）可知，當n→∞時，基大圖中個體和總體的均值差值正向趨近于0。因為弱單向圖集中的各個單向圖具有極小的相關(guān)性，且只與查詢節(jié)點u的j步游走鄰居節(jié)點相關(guān)，所以由Monte Carlo 模擬法可得，當弱單向圖集Gs中的各個單向圖樣本滿足路徑覆蓋時，其計算結(jié)果可滿足基大圖G的誤差需求，且具有更快的收斂性。累積相似度計算方法如式（3）所示：

其中，節(jié)點u、v表示概率游走的節(jié)點，ω表示相遇節(jié)點，pt(u，ω) 及pt(v，ω) 為節(jié)點u、v在概率游走過程中出度倒數(shù)的乘積，j表示游走步數(shù)，∏w為單邊弱化因子的疊乘值。

2.3 節(jié)點相似Top-k 算法

針對基大圖游走步數(shù)遞增會降低圖查詢效率的問題，本文通過多次引入PageRank 概率游走機制，并提出單邊弱化因子對其進行概率約束，實現(xiàn)基大圖轉(zhuǎn)化為多個單向圖集合。由于查詢游走步數(shù)較多導(dǎo)致基大圖上的遍歷查詢效率較低，因此通過多次隨機選取查詢節(jié)點，利用大數(shù)定理進行驗證，并計算出節(jié)點的累計相似度作為節(jié)點的真實相似度，以Top-k 取值為基準逐步增大游走步數(shù)，實現(xiàn)節(jié)點相似Top-k 的快速累積查詢。

節(jié)點相似Top-k 算法描述如算法1 所示。其中，通過PageRank 概率游走機制得到N個單向圖的圖集，且在每個單向圖中，根據(jù)概率游走路徑找到節(jié)點ur的t步相遇節(jié)點集，再將節(jié)點的游走概率以及單邊弱化因子疊乘值代入相似度計算公式中進行計算，以k值作為約束條件，從相遇節(jié)點集中選出節(jié)點ur的相似節(jié)點集，并對節(jié)點進行相似度排序得出最終結(jié)果。

采用概率游走約束的節(jié)點進行相似Top-k 累積計算，且當計算結(jié)果滿足Top-k 結(jié)果集需求時，則立即停止迭代并輸出結(jié)果集，避免多個“遠關(guān)系”的疊加結(jié)果優(yōu)于“近關(guān)系”的問題，并提高查詢效率。算法1 中對n個單項圖均選取查詢節(jié)點ur進行概率游走，共找到其j步相遇節(jié)點，通過相似度計算公式計算其與查詢節(jié)點ur的相似度，排序得出查詢結(jié)果。因此，算法1 的時間復(fù)雜度為O（n·j）≈O（n）。

3 自適應(yīng)動態(tài)更新

節(jié)點相似Top-k 查詢方法在大規(guī)模圖中可以快速反饋滿足條件的查詢結(jié)果，但當圖發(fā)生動態(tài)變化時，為確保查詢結(jié)果的準確度，需要對圖結(jié)構(gòu)及結(jié)果集進行更新維護。本文綜合更新效率及準確度2 個方面的因素，實現(xiàn)基大圖及單向圖集的自適應(yīng)動態(tài)更新。

3.1 基大圖觸發(fā)更新

對基大圖更新時，若每次都進行實時更新，則會導(dǎo)致更新代價過大，且許多變化與查詢無關(guān)，造成資源浪費；若進行累計更新，則可能導(dǎo)致查詢結(jié)果錯誤，降低查詢準確度。因此，本文以Top-k 查詢條件作為更新操作觸發(fā)點進行自適應(yīng)觸發(fā)更新，且觸發(fā)規(guī)則為：判斷查詢節(jié)點u以及u的出邊集合｛（u，v）|u∈Gr，v∈No(u)，(u，v)∈Gs｝是否發(fā)生變化，若節(jié)點u及（u，v）均發(fā)生變化，則采取即時更新策略更新查詢；若查詢節(jié)點u或其出邊（u，v）沒有發(fā)生變化，則繼續(xù)判斷在游走路徑過程中的相遇節(jié)點是否為起點，并查看起點的邊集合｛（v，r）|r∈Gr，v∈No(u)，是否變化，若發(fā)生變化，此時需采用即時更新策略；若上述2 種情形均未發(fā)生，則采用累計更新策略對圖集進行更新。

3.1.1 即時更新策略

對基大圖進行更新時，當圖中的節(jié)點及邊變化較大時通常會對圖的查詢結(jié)果產(chǎn)生較大影響，此時需采用即時更新策略。即時更新策略主要是針對查詢節(jié)點u及其i步鄰居節(jié)點的變化而言，采用即時更新策略的具體情況可表述為當圖發(fā)生動態(tài)變化時，首先查看節(jié)點及其出邊是否存在變化，若出現(xiàn)變化，則說明其相似節(jié)點等均發(fā)生變化，若不對其改變會增加查詢結(jié)果的錯誤率；若節(jié)點及其出邊未發(fā)生變化時，則需查看其鄰居節(jié)點集中各個節(jié)點的查詢節(jié)點i步鄰居節(jié)點集合是否發(fā)生變化，若發(fā)生變化，則采用即時更新策略。

即時更新策略的優(yōu)勢在于當發(fā)現(xiàn)基大圖的變化對查詢關(guān)聯(lián)影響較大時，通過該方法可有效保證查詢結(jié)果的準確度。即時更新算法如算法2 所示。其中，判斷查詢節(jié)點u以及u的出邊集合｛（u，v）|u∈Gr，v∈No(u)，(u，v)∈Gs｝是否發(fā)生變化，若節(jié)點u及邊（u，v）發(fā)生變化，則即刻進行更新操作；若未發(fā)生變化，則繼續(xù)判斷u的鄰居節(jié)點集中各個節(jié)點的查詢節(jié)點i步鄰居節(jié)點集合是否發(fā)生變化。若查詢節(jié)點i步鄰節(jié)點集合與原數(shù)據(jù)集相比沒有發(fā)生變化，則停止遍歷，查詢結(jié)果集不變，若發(fā)生變化，則分別找出該集合中各個節(jié)點的出邊及i步鄰居節(jié)點集合，并重新計算相似查詢結(jié)果。

在算法2 中，假設(shè)共有n個節(jié)點u，對每個節(jié)點u開始遍歷，若節(jié)點u或者其出邊發(fā)生變化，則立即更新圖，因此最少時間復(fù)雜度為O（n）；若未發(fā)生變化，則需查看其i步鄰居節(jié)點集合是否發(fā)生變化，假設(shè)其鄰居節(jié)點集合數(shù)量為k，則最大時間復(fù)雜度為O（n·k）≈O（n）。由于算法2 中無需額外輔助存儲空間，因此空間復(fù)雜度為S（1）。

3.1.2 累積更新策略

即時更新策略在針對查詢節(jié)點及其鄰居節(jié)點發(fā)生變化時，能夠有效減少查詢圖時的錯誤率，但當基大圖發(fā)生的變化與查詢關(guān)聯(lián)較小時，采用即時更新策略會降低效率以及浪費空間。針對這種情況，為提高效率和節(jié)省存儲空間，本文提出一種累積更新策略，其主要步驟為：先為圖查詢創(chuàng)建一個輔助存儲空間Ω，該空間主要用來記錄在一段時間內(nèi)圖的節(jié)點與邊的變化情況，并以一定的周期對圖進行定時更新。為避免某個節(jié)點或某條邊存在多次刪除、增添等情況，在輔助存儲空間Ω中，需要先對記錄變化進行合并操作，從而進一步提高更新效率。在輔助存儲空間Ω中為每條記錄添加一個數(shù)據(jù)變化用到的標簽，并令標簽的初始值為0。由于節(jié)點的增刪最終可以轉(zhuǎn)化為邊的增刪，因此表中只需記錄邊的增刪，并以設(shè)定的?t為周期累加輔助表標簽值，進而更新圖。

累計更新策略的優(yōu)勢在于能夠避免某條邊的重復(fù)刪減情況，通過這種標簽的設(shè)定不僅可以簡化更新操作，而且可有效提高更新效率。累計更新算法如算法3 所示。其中，為更新圖中每條邊的增減情況記錄均設(shè)定一個標簽（u，v，i），若刪除邊（u，v）則將其標記為（u，v，-1）；若增加邊（u，v）則將其標記為（u，v，1）；接下來對更新圖中的所有邊進行遍歷，若標簽值為0，則說明不需增加刪除邊；若標簽值為1，則說明需要增加邊；若標簽值為-1，則說明需要刪除邊。在統(tǒng)計完所有邊的標簽后，再對圖進行更新操作。

在算法3 中，假設(shè)圖中共有n條邊（u，v），并對每條邊的記錄進行統(tǒng)計，共需統(tǒng)計n次，因此其時間復(fù)雜度為O（n）。由于統(tǒng)計一次邊需額外開辟輔助空間對記錄進行存儲，因此空間復(fù)雜度為S（n）。

3.2 單向圖集聯(lián)動更新

如3.1 節(jié)所述，當基大圖發(fā)生變化時，為保證查詢的準確度，需要對單向圖集進行對應(yīng)的更新操作。為避免重新選取單向圖，本文基于局部更新原則分別對單向圖集中所有單向圖中邊和節(jié)點的變化進行局部更新處理，更新策略可表述為：

1）增加邊：當基大圖中增加某條邊（a，b）時，判斷邊（a，b）中頭節(jié)點a的出邊數(shù)Num（a），若節(jié)點a出邊數(shù)Num（a）=0，則需要在每個單向圖中均增加邊（a，b）；若節(jié)點a出邊數(shù)Num（a）≠0，則需要在所有單向圖中為該節(jié)點重新選取一條出邊。

2）刪除邊：當基大圖中刪除了某條邊（a，b）時，判斷邊（a，b）中頭節(jié)點a的出邊數(shù)Num（a），若節(jié)點a出邊數(shù)Num（a）=1，則在所有單向圖中刪除這條邊；若節(jié)點a出邊數(shù)Num（a）>1，則為所有包含被刪除邊的單向圖中的節(jié)點a重新選取一條出邊。

3）增加節(jié)點：當基大圖中增加節(jié)點u時，主要看其是否有邊（u，v）的增加，若沒有邊的增加，則不需處理單向圖集，否則按上述邊的增加方法來更新圖集。

4）刪除節(jié)點：當基大圖中需要刪除某節(jié)點時，先要查看是否存在以該節(jié)點為頭節(jié)點或者為尾節(jié)點的邊，若存在以該節(jié)點為頭節(jié)點的邊，則需要在每個單向圖中刪除這樣的節(jié)點以及以它們?yōu)轭^節(jié)點的邊；若存在以該節(jié)點為尾節(jié)點的邊時，則需刪除并找到它們的頭節(jié)點；若不存在上述兩種情況，則不需處理。其中，若節(jié)點不存在出邊則不進行處理，并在每個單向圖中為其余節(jié)點重新選取一條出邊。

圖3 為基大圖中刪除節(jié)點f、增加邊（g，h）時，單向圖集中的單向圖更新示意圖。

圖3 基大圖與單向圖更新示意圖Fig.3 Schematic diagram of base large graph and unidirectional graph updating

如圖3 所示，通過對各單向圖節(jié)點和邊的局部操作，可以最大程度地降低單向圖集的更新代價，進而提高大規(guī)模動態(tài)圖Top-k 查詢效率。單向圖更新算法如算法4 所示，其過程為在單向圖集中判斷邊（u，v）以及節(jié)點u是否出現(xiàn)上述某一種情況，并針對上述中某一種情況進行相應(yīng)操作。

4 實驗結(jié)果與分析

實驗從查詢效率、結(jié)果可靠性及更新效率等方面驗證本文所提方法的有效性。實驗的硬件配置為Windows10 系統(tǒng)主機、16 GB 內(nèi)存、CPU 型號為Intel i5-9300H 以及64 位操作系統(tǒng)、2 TB 硬盤。為驗證本文方法的有效性，本文選取5 組節(jié)點與邊數(shù)量均不等的數(shù)據(jù)集，具體如表1 所示。

表1 實驗數(shù)據(jù)集Table 1 Experimental datasets

4.1 節(jié)點相似Top-k 查詢效率分析

圖4為在5 組數(shù)據(jù)集下，F(xiàn)R、KM、SimRank、P-SimRank 方法與本文方法的查詢效率對比結(jié)果。其中，實驗以平均查詢時間作為查詢效率評價準則。從圖4 可以看出，相比其他方法，本文方法具有較高的查詢效率。這是由于FR 與KM 采用的是在結(jié)果集中過濾掉不合格節(jié)點的方法，造成查詢效率較低，SimRank 與P-SimRank 在計算過程中容易造成相似度疊加問題，因此其適用于小規(guī)模的圖查詢問題，在大圖上權(quán)值的計算及查詢效率較低，本文方法僅需篩選出查詢節(jié)點的相似節(jié)點，因此需要處理的數(shù)據(jù)量很小，查詢效率較高。

圖4 4 種方法的查詢效率對比Fig.4 Comparison of query efficiency of four methods

4.2 節(jié)點相似Top-k 查詢結(jié)果可靠性分析

圖5 為4 種方法查詢結(jié)果的可靠性對比。從圖5可以看出，本文方法的準確度與FR、KM 方法的原圖查詢準確度近似，但FR、KM 方法存在穩(wěn)定性較差以及準確度差異較大的問題。本文方法具有較高的可靠性，這是由于SimRank、P-SimRank 方法中的節(jié)點間相似度計算僅考慮了游走過程中節(jié)點相遇總時間的數(shù)學(xué)期望，無法保證較高的查詢準確度。因此，本文方法查詢結(jié)果的準確度相對較高。

圖5 4 種方法的查詢結(jié)果可靠性對比Fig.5 Reliability comparison of query results of four methods

4.3 自適應(yīng)動態(tài)更新策略分析

實驗通過分析邊的更新效率來驗證更新策略的有效性，每個圖隨機選擇約80%的插入邊和20%的刪除邊進行更新。表2 為在4 個數(shù)據(jù)集上更新1 000 條邊的原圖與單向圖的時間。從表2 可知，本文提出的更新策略在各個數(shù)據(jù)集上均可達到較高的更新效率。

表2 本文更新策略在4 個數(shù)據(jù)集上的更新效率Table 2 Update efficiency of the proposed strategy on four datasets

5 結(jié)束語

本文利用大規(guī)模動態(tài)圖概率游走約束條件，提出一種節(jié)點相似Top-k 查詢方法。該方法通過引入PageRank 概率游走機制，實現(xiàn)將基大圖轉(zhuǎn)化為多個單向圖集，并依據(jù)Monte Carlo 模擬法思想實現(xiàn)Top-k節(jié)點相似查詢。實驗結(jié)果表明，與FR、KM、SimRank及P-SimRank 方法相比，本文方法的查詢準確度與查詢效率均有大幅提升，且在查詢準確度上表現(xiàn)出良好的穩(wěn)定性?？紤]到圖中邊的權(quán)值對節(jié)點相似度的影響以及對圖查詢與更新的重要性，后續(xù)將采用SimRank 及其優(yōu)化方法對加權(quán)圖的相似節(jié)點Top-k查詢進行改進，進一步提高查詢效率與準確度。