不確定圖上Top-k最大影響力邊查詢算法

胡 陽,黃金晶,2,劉光富,趙 雷

(1.蘇州大學 計算機科學與技術學院,江蘇 蘇州 215006; 2.蘇州工業職業技術學院 軟件與服務外包學院,江蘇 蘇州 215104)

0 概述

在科研和實際應用領域中,圖數據模型的研究工作已較為成熟。然而,隨著數據規模的指數級增長以及數據處理技術的改進,人們對數據的準確性要求也在不斷提高,需要考慮到采集數據時出現的噪音數據和錯誤[1]處理結果。因此,對圖數據的研究也從確定性數據擴展到不確定性數據。由于很多傳統的確定圖算法無法有效地應用于這類新型數據模型,因此不確定圖[2-4]研究領域也就應運而生。就不確定性數據而言,由于不確定圖邊上特有的存在概率屬性,使得問題定義、處理過程及結果信息都有所差異,不確定圖已經成為近年來圖領域研究的熱點問題。許多現實應用中的數據都可以抽象地表示成不確定圖,如蛋白質互連網絡[5-6]中的噪音數據和實驗結果的誤差、通信網絡[7]中的傳播擁塞和異常中斷以及社交網絡[8-9]中影響力的傳播過程等。

最大影響力邊是指能夠很大程度上影響圖結構的那些邊,此處圖結構包括平均距離、度分布、圖連通性、聚集系數等。最大影響力邊的數量一般非常少,但是其影響力卻可以快速地波及到圖中大部分頂點和邊[10]。因此,查詢不確定圖上邊的影響力是一項有意義的研究工作。該問題在現實中同樣也有著廣泛的應用場景。例如在生物網絡中,用頂點表示蛋白質分子,邊表示蛋白質之間的關系,但是實驗中得到的數據可能出現的誤差和錯誤會導致蛋白質之間關系產生不確定性。通過在邊上賦概率值表示關系的重要程度,查詢出最大影響力的k條邊,能快速找到影響蛋白質互連關系的重要的邊集。

本文研究不確定圖上Top-k最大影響力邊查詢問題,建立一個基于平均距離差評價邊影響力的計算模型。由于在圖中計算任意頂點對之間最短路徑距離時,無向無權圖采用的廣度優先搜索(Breadth-First Search,BFS)方法時間復雜度是O(|V|2),直接運用到圖的距離差計算非常耗時,因此,本文基于簡單隨機邊抽樣算法(REB)和Forest Fire抽樣[11-12]算法(FFB)設計Top-k最大影響力邊查詢基礎算法。首先給出不確定圖上Top-k最大影響力邊查詢問題及其形式化定義;然后采用抽樣技術簡化窮舉可能圖的處理過程;最后建立基于平均距離的邊影響力評價模型并優化過程,以進一步提高算法的執行效率。

1 相關工作

近年來,不確定圖問題得到了較多的關注。現有不確定圖的研究集中在3條主流觀點上:

1)不確定圖上的挖掘問題[13],特別是頻繁子圖挖掘[14-15]、子圖模式匹配[16]或高可靠性子圖挖掘[17]以及聚類分析[9,18]。

2)不確定圖上的查詢問題,主要體現在兩方面:第一方面是基于距離的查詢[2-4,19-20],文獻[2]采用最短路徑距離方法去查找給定頂點的k個最近鄰居點集,文獻[3]研究基于距離約束的可達性問題,判斷不確定圖中給定兩點是否滿足可達性的要求,并且滿足一個給定的距離閾值;另一方面是子圖查詢問題[5,17,21],文獻[5]采用一種最優化策略去查找不確定圖中的基于概率閾值的子圖,此外,文獻[21]還研究子圖相似度的問題。

3)針對不確定圖蘊含的指數級個數的可能圖,且為了滿足特定問題的需要,研究者利用圖抽樣方法避免窮舉所有可能圖基本的方法是基于蒙特卡洛抽樣法[3,22],并應用到相關不確定圖問題的研究中。文獻[23]提出基于分層抽樣的統計量來估計查詢結果,同時用實驗證明了準確性和效率要優于蒙特卡洛抽樣法。文獻[24]提出從不確定圖中抽取一個具有代表性可能世界圖的算法,令該樣本圖保留了原圖大部分有用性質,并驗證其有效性。然而,目前不確定圖上邊查詢的研究不多,其中文獻[25]從流量和流量可靠性的觀點出發,研究不確定圖上關鍵邊的查詢。

邊影響力計算問題是近年來研究的一個熱點方向。文獻[26]研究邊刪除后對頂點之間可達性的影響,定義了圖上邊的影響力并且提出刪除邊后更新圖編號索引的方法,用于計算圖中任意邊的影響力大小。本文把從不確定圖的樣本圖中刪除候選邊后對平均最短距離的差值作為該邊的影響力大小來建立計算模型。

目前基于不確定圖上查詢的研究也已經有了很多成果,現有的方法主要是隨機算法,采用抽樣的技術估計邊影響力概率,其中最直觀也是最簡單的抽樣技術是對不確定圖的每條邊等概率地進行抽樣。文獻[3]從估計結果的準確性和效率方面對4種隨機抽樣技術進行對比,得到結論是這種算法優點是簡單,但需要確定每一條邊的存在性,另外通過基本的抽樣估計的方差較大。

目前在不確定圖的研究方面較少有針對Top-k最大影響力邊查詢的算法。為此,本文綜合考慮不確定圖的概率模型與邊影響力的特點,提出在不確定圖上進行Top-k最大影響力邊查詢的有效算法。

2 問題定義與形式化

2.1 不確定圖

定義1(不確定圖) 一個不確定圖的無向圖可以表示為一個三元組g=(V,E,Pr),其中,V是g頂點的集合,E是邊的集合,Pr:E→(0,1]是邊上的概率函數,表明該邊存在的概率,本文約定不確定圖上邊之間的存在性是相互獨立的。

由于不確定圖邊的存在與否是不確定的,因此一個不確定圖實際上對應著很多邊概率為1的確定圖,即上文提到的可能世界語義模型。在可能世界語義模型下,一個不確定圖可以派生出一組確定圖G=(V’,E’),記為g?G,此確定圖稱為可能世界圖,也稱可能圖,滿足V’=V,E’?E。那么根據邊上的存在概率以及不同邊是相互獨立的理論,即可得到可能圖的概率為:

(1)

設Pws(g)為不確定圖g的所有可能世界集合,顯然Pws(g)的大小為2|E|。

定義2(邊影響力) 邊影響力的研究是近年來剛興起的一個研究方向,文獻[27]提出邊影響力的定義:每次在圖中刪除一條邊之后,導致兩點之間可達性改變的頂點對個數(即兩點之間不可達)作為該邊對圖可達性的影響力。基于此,本文給出了邊影響力的定義。通過刪除每一條邊e,把刪除前后圖的平均最短距離的差值作為該邊影響力大小的衡量標準,記作Imp(e)。

定義3(不確定圖的邊影響力概率) 給定一個不確定圖g和一條邊e,求出所有e所存在的可能圖的影響力概率之和。對于一個可能圖G?g,本文定義一個符號函數如下:

(2)

則不確定圖中e的影響力概率可以表示為式(3)。

(3)

已知可能圖的數量是邊數量的指數量級,精確計算每一個可能圖距離差值的邊影響力是#P-完全問題,即使是中等大小規模的圖也是很難在多項式時間內求解的。因此,本文利用隨機化方法處理該類查詢問題。

2.2 問題定義

本文所提出問題的定義如下:

定義4(不確定圖上Top-k最大影響力邊查詢)給定一個不確定圖g=(V,E,Pr)和一個很小的正整數k,尋找一個k大小的邊集EImp,對任意e∈EImp,能最大化e的影響力概率Rg(e)表示如下:

(4)

其中,|EImp|=k。

3 Top-k最大影響力邊查詢基礎算法

在不確定圖上查詢出最大影響力的邊具有非常廣泛的應用場景。例如在社交網絡中,用戶之間一般通過最短路徑來傳遞信息。本文利用用戶之間的親密度來刻畫關系的不確定性。假設2個用戶之間親密度為0時,原先經過這2個用戶傳遞消息的路徑將會改變,或許需要尋找一條更長的最短路徑進行傳遞消息,或許消息完全不能傳遞。因此,網絡中一定存在一些影響力非常大的邊,它們一旦不存在,將對整個網絡的信息傳遞造成很大影響,如果查詢出網絡中最大影響力的k條邊加以保護,則可使整個網絡的信息流通性更健壯。

按照上節給出的邊影響力定義,本文基于最短路徑距離算法并采用抽樣技術設計Top-k最大影響力邊查詢算法。首先給出一個基準方法,其采用每次刪除任意一條邊計算圖的平均距離差值來精確計算該圖中每一條邊的影響力概率Rg(e)。由于基準算法肯定存在時間指數爆炸的缺點,無法在多項式時間內求解,因此給出2個對基準算法的近似算法(REB和FFB)來估計概率Rg(e),進而解決邊影響力的Top-k查詢問題。

3.1 REB算法

本文的基準算法在計算e這條邊的邊影響力概率Rg(e)時通過枚舉e存在的所有可能圖來計算,引發了圖數量的指數爆炸。因此,本文不再按照基準方法去精確計算每條邊的影響力概率,而是采用獨立、隨機地N次采樣不確定圖空間,只需要對g中每條邊按照其存在概率進行采樣即可得到一個樣本圖。然后在采樣得到每個樣本圖上計算e的影響力大小Imp(e)。

利用REB算法在樣本圖中近似計算邊影響力概率時,從候選邊集Ce中依次取出每條邊e及其被影響頂點對的集合Impnodepairs(e),調用e.Update()函數更新e被刪除之后所有點對的當前最短距離。

利用REB算法計算邊e影響力概率近似值的偽代碼如算法1所示。首先輸入一個不確定圖g,每次等概率地從g中抽取一條邊e。然后判斷e上的存在概率是否大于一個隨機值,若滿足,加入到樣本圖中;否則,繼續上述操作。對樣本圖中的候選邊計算其影響力概率并求和,輸出每條邊的影響力概率。

算法1隨機抽樣邊影響力算法REB

輸入不確定圖g,邊候選集合Ce,邊e∈Ce,參數k<|Ce|,樣本數N

輸出邊影響力概率集合R

1.Ce=?;//初始化邊候選集合

有研究證實乳腺癌組織中基質金屬蛋白酶2（MMP‐2）和VEGF的表達較正常乳腺組織增高，癌細胞降解細胞外基質、促進上皮間質化、激活生長因子及受體、促進血管生成、增加血管通透性等能力較強，而這些與腫瘤生長、侵襲及轉移密切相關。范盼紅等［28］用染料木黃酮處理乳腺癌MDA‐MB‐231細胞，可觀察到染料木黃酮能顯著降低細胞的體外侵襲和遷移能力，進一步研究結果顯示染料木黃酮可能通過抑制MMP‐2和VEGF的表達，降低乳腺癌細胞侵襲和遷移能力。

3.若一次BFS中訪問到一次以上距離相等的頂點對,將路徑上共用邊加入到Ce;

4.按e∈Ce生成被影響頂點對集合 Impnodepairs(e)={(u1,v1),(u2,v2),…,(ut,vt)};

5.Samptimes=0;

6.g中所有的邊組成一個向量edges=(e1,e2,…,em);

7.while(Samptimes≤N);

8.產生(0,1]之間的均勻隨機數r1,r2,…,rm;

9.while(ri

10.Sampedges.push(ei);//產生一個樣本圖

11.end while

13.Pri=1;

14.While(j

15.if(edges[j] = 1)

16.Pri=Pri·pr(ej);

17.else

18.Pri=Pri·(1-pr(ej));

19.end if

20.end while

21.for each e∈Ce do

22.Imp(e)=e.Update(Impnodepairs(e))-e.distance;

23.R(e)=R(e)+Imp(e)·Pri;

24.end for

25.end for

26.end while

27.Sort(e1,e2,…,e|Ce|);

28.R={e1,e2,…,ek};

29.return R;

3.2 FFB算法

基于邊選擇的抽樣策略具有一定的隨機性,使用其并不能很好地保證結果的準確性。因此,本文提出使用效果更好的“Forest Fire”采樣法(以下簡稱FFS算法),文獻[12]表明,FFS法在各種圖抽樣算法中是最優的,采用該方法所獲得的樣本圖能夠很好的保留原圖的各種參數特性,如平均度、冪律指數和聚集系數。因此,本文采用FFS算法來對不確定圖進行抽樣處理。

在FFS算法中,首先隨機選擇一個頂點v,然后生成一個隨機數x且滿足均值為pf(1-pf) 的幾何分布,v選擇x條出邊沒有訪問過的鄰居頂點,使w1,w2,…,wx表示為所選擇邊的另一個端點,這些頂點獲得一個機會去“燃燒”它的出邊,重復迭代上述過程直到滿足抽樣條件為止。在此過程中,頂點不可以被訪問2次,這樣保證避免在構造過程中出現環路。但是如果“燃燒”過程被“熄滅”(即沒有頂點可以繼續“燃燒”出邊),將重新隨機選擇一個頂點開始上述過程。本文把參數pf稱作前向燃燒概率。

FFB算法其實是在算法1基礎上替換隨機邊抽樣過程為FFS法,因此,下文只給出FFS算法的偽代碼,如算法2所示。輸入一個不確定圖g,根據上述“燃燒”過程,輸出一個可能世界里的樣本圖G。

算法2FFS算法

輸入不確定圖g,前向燃燒概率pf,樣本圖邊數sampedgecount

輸出樣本圖G

1.Stack S=?;

2.while(G.Edges.Count

3.隨機選擇一個開始頂點start;

4.S.push(start);

5.while(S.size)

6.v=S.pop();

7.v點未訪問出邊放入集合outEdges={oe1,oe2,…,oex}中;

8.for each oei∈outEdges do

9.if(random≥pf)

10.break;

11.oej是從oei之后的一條隨機出邊;

12.將oej和oei交換位置;

13.G.Vertices.push(oei.destVertex);

14.G.Edges.push(oei);

15.S.push(oei.destVertex);

16.end for

17.end while

18.end while

19.return G;

3.3 復雜度與算法局限性分析

精確計算不確定圖上邊影響力概率是窮舉所有可能圖,然后計算每個可能圖上|E|條邊的影響力大小,整個算法運行時間是O(2|E|·|E|·|V|2),顯然是多項式時間不可解。因此,只能采用近似算法盡可能快速、準確地找出k條影響力最大的邊。

4 Top-k最大影響力邊查詢優化算法

本節主要介紹在樣本圖中對BFS過程的優化算法,由于該算法對2種抽樣得到樣本圖都適應,因此分別將其命名為REPB算法和FFPB算法,但是下文主要介紹優化BFS的過程。

上文分析了計算主要時間代價是距離差值的過程,計算距離時每一次查詢使用BFS或者Dijkstra’s算法效率較低。為減少計算距離的時間消耗,本文借鑒文獻[27]提出的剪枝BFS思想,采用PB(Pruned BFS)算法達到加速查詢邊影響力的目的。

PB算法是基于2-hop覆蓋理論精確計算兩點之間距離的算法,算法開始按照頂點標號從小到大的順序開始每輪BFS,并記錄起點到其他頂點的標號集合,設起點是vφ第φ次BFS的起點,標號集合記為Lφ={Lφ(u1),Lφ(u2),…,Lφ(un)}。假設當前訪問u的距離為δ,如果Query(vφ,u,Lφ-1)≤δ,將剪枝u,即不再訪問從u出發的任何鄰居;否則更新標號集合Lφ(u)=Lφ-1(u)∪{(vφ,δ)}。PB算法的剪枝效果取決于頂點標號的順序。文獻[28]證明了按照頂點度數或頂點中心性排序編號得到的剪枝效果要好于隨機編號,所以,筆者在實驗中先對原圖頂點度數排序,然后重新對頂點標號編號。

REPB算法和FFPB算法提高效率的原理是刪除邊之后不需要再重新構建標號集合,而只需對標號集合中被影響到的標號點對進行距離的更新,而未被影響的標號集合不改變。PB算法及其更新標號集合算法UpdateLabelsSet的偽代碼分別如算法3和算法4所示。

算法3PB算法

輸入樣本圖G

輸出標號集合L

1.初始化標號集合L0[v]=?,v∈V(G);

2.for each φ=1,2,…,|V(G)| do

3.Lφ=PrunedBFS(G,vφ,Lφ-1);

4.end for

5.PrunedBFS(G,vφ,Lφ-1)//剪枝BFS主要過程

6.Queue Q={vφ};

7.P[vφ]=0;P[v]=∞,v∈V(G){vφ};

8.Lφ[v]=Lφ-1[v],v∈V(G);

9.while Q非空 do

10.u=Q.front;

11.if(Query(vφ,u,Lφ-1)≤P[u])

12.continue;

13.Lφ[u]=Lφ-1[u]∪{(vφ,P[vφ])};

14.for each w∈NG(v) s.t.P[w]=∞do

15.P[w]=P[u]+1;

16.Q.push(w);

17.end for

18.end while

19.L=L0∪L1∪…∪Lφ;

20.return L;

算法4UpdateLabelsSet算法

輸入樣本圖G,被影響標號點對集合ImpLabSet,刪除點對(u,v),標號集合L

輸出更新標號集合L’

1.從u出發尋找一條大于1的最短路徑到達v,并記距離為dist’(u,v),更新L[v]=(u, dist' (u,v));

2.for each (lu,lv)∈ImpLabSet do

3.Queue Q=?;

4.Q.push(lu);

5.while Q非空 do

6.u=Q.front;

7.Lk[u]=Lk-1[u]∪{vk,P[vk]};

8.for each w∈Ng(v) s.t.P[w]=∞do

9.P[w]=P[u]+1;

10.Q.push(w);

11.end for

12.end while

13.end for

14.return G;

5 實驗與結果分析

為了驗證算法的執行效率、不同數據規模對算法的影響以及隨機算法所獲結果的準確性,本文采用真實和模擬的不確定圖數據進行實驗。所有算法都在STL庫下用C++實現,用于實驗的是一臺Inter Core(TM)i5-3470 CPU @3.2 GHz內存8 GB 64位Window7系統的PC機。

對比算法包含:1)隨機邊抽樣的邊影響力估計算法REB;2)“Forest Fire”抽樣的邊影響力估計算法FFB;3)剪枝BFS策略的隨機邊抽樣法REPB;4)剪枝BFS策略的“Forest Fire”抽樣法REPB。

下面介紹實驗考察的集中測度,本文從準確性和效率兩方面對4種算法作對比,其中REB和FFB這兩種不同抽樣技術用Top-k最大影響力邊的排名結果的相似度α來衡量,效率用各個算法的運行時間來衡量。

因為不確定圖邊影響力算法獲取的是邊影響力大小的排序,所以分別從算法獲取的排名情況比較近似方法和基準方法的準確性。具體操作是計算基準算法的排序結果和近似結果的平均歐幾里得距離α,表示如下:

(5)

實驗數據集包括真實數據集和模擬數據集:

1)真實數據集:實驗中采用歐洲分子生物學實驗室string(http://string-db.org)提供的真實不確定圖數據。數據集是一個蛋白質網絡,其中,頂點代表蛋白質,具有確定性,邊代表不同蛋白質之間存在相互作用的概率,通過生物實驗加以測定。整個網絡包括6 865個頂點和70 288條邊。實驗對此數據集抽取了1 675個頂點和4 693條邊,避免數據集過大導致時間爆炸增長。

2)模擬數據集:首先產生|V|個頂點,然后通過隨機選擇2個端點的方式生成|E|條邊,而后為所有的邊隨機生成存在概率,概率取值為隨機生成的0.01～0.99之間的小數。V和E是實驗中可以設定的參數,可以合成不同特征的數據。

在考察抽樣方法的準確性時,需要通過枚舉出不確定圖g的全部可能圖準確計算候選邊集的影響力排序,因此,實驗不能使用邊數很大的數據。又由于本文抽取的可能圖須滿足:1)是連通圖;2)所有頂點都將被采集,因此本文在模擬數據集上生成5組實驗數據集:Dys1(|V|=60,|E|=120),Dys2(|V|=70,|E|=140),Dys3(|V|=80,|E|=160),Dys4(|V|=90,|E|=180),Dys5(|V|=100,|E|=200)。對每組選擇60條查詢邊,用前兩種方法對邊的影響力概率進行計算,其中樣本數設為2 000,對每條邊的估計次數K=100。

圖1給出了不同規模圖上REB和FFB算法之間相似度的比較結果,可以看出隨著數據規模等比例增長,FFB算法在結果相似度的比較上要優于隨機的REB算法,但是兩者相差不大并且維持在較低水平(30以內)。圖2顯示了隨著樣本數的增加,排序結果相似度的變化,可以看出相似度呈下降趨勢,并且FFS要更準確一點。在考察不同抽樣方法及其優化方法的效率時,將上述4種方法分別在模擬數據集和真實數據集上進行了多組實驗,主要設置參數有圖規模(主要參數是圖邊數|E|)、查詢邊數k以及樣本大小N,并對優化前后的執行時間作對比。在測試某一參數時固定其他參數,并給出執行時間關于參數變化的關系。

圖1 不同規模數據集上排序結果的相似度

圖2 不同樣本數下排序結果的相似度

首先設定參數N=1 000,k=60,測試圖邊數|E|從2 000～6 000變化時的執行時間。由圖3可以看出,隨著邊數的增加剪枝BFS優化算法的時間遠小于未優化算法,并且未優化過的算法基本上都呈指數增長。優化后2種抽樣方法的時間基本上重合,增長趨勢緩慢。造成這種現象的原因在于,計算邊影響力過程是直接影響整個實驗效率的好壞的重要環節,并且邊數是重要的影響因素。而后,設定參數N=1 000,圖規模|E|=4 000,測試k值從50～500變化的執行時間。由圖4可以看出,當k大于200時,未優化算法的執行時間已經超過3 000 s,而優化算法維持在一個相對較低時間(1 000 s以內)水平。k值是計算候選邊的影響力的個數,由于未優化算法每計算一條邊都要對所有被影響點對重新計算距離長度,時空開銷非常大,而優化算法只需要更新被影響的標號集合即可,其他非標號的被影響點對可以通過更新之后的標號集合間接計算,且每次需要更新的標號集合比較小,查詢標號集合的時間復雜度為O(|L(s)|+|L(t)|),s和t是被影響點對,|L(s)|和|L(t)|分別是s和t的標號集合長度。因此,上述結果進一步說明了優化算法的效率較高。

圖3 不同邊數下執行時間的變化

圖4 不同k值下執行時間的變化1

下面考察樣本數對執行時間的影響。設定k=60,|E|=2 000,測試N值從100～500變化對執行時間的影響。由圖5可以看出,優化算法的效率依舊緩慢增長,未優化算法隨著樣本個數的增加執行時間也在指數級增長。本文提出的4種算法都可以單獨求解出所提出的不確定圖上查詢Top-k條最大影響力邊問題,區別在于不同的圖抽樣策略和不同的最短路徑距離的計算策略,兩兩組合即為4種方法。通過圖1和圖2的分析可知,FFB和FFPB算法的結果準確性更高,而通過對不同邊數、不同結果數值和不同樣本數上4種算法在時間效率上的比較可以總結出,優化后算法REPB和FFPB的效率都明顯優于未優化算法REB和FFB。最后在真實數據集上驗證k值變化時4種算法的執行效率,同樣優化算法明顯優于非優化算法,如圖6所示。

圖5 不同樣本數下執行時間的變化

圖6 不同k值下執行時間的變化2

6 結束語

本文給出不確定圖上邊影響力的定義,同時提出2個近似方法來求解Top-k最大影響力邊查詢問題。在此基礎上,通過設計優化方法進一步提高效率。實驗結果表明,本文算法具有較高的準確性和效率。后續將把概率語義的“最短路徑距離”作為衡量標準,進一步解決不確定圖上Top-k最大影響力邊查詢問題。