流模式下有向近似覆蓋圖算法研究

張 昕 李曉光

(遼寧大學信息學院 沈陽 110036) (zhangxin1979@hotmail.com)

圖作為一種重要的數據結構,一直有著廣泛的應用,特別是隨著信息技術的發展,在諸如通信網絡中路由選擇與資源優化、社交網絡中用戶關系與興趣點分析、交通網絡分析以及計算幾何學與計算生物學等重要應用領域中,大量的數據均以圖結構作為抽象對象,進而開展各種復雜的計算與分析研究[1].因此,大規模圖數據相關研究逐漸成為許多研究與應用領域的一項重要的基礎性工作.但由于數據量的飛速增長,以及圖結構自身的復雜性,大規模圖數據的存儲與計算代價通常較高,很難高效地支撐后續的研究應用工作.

針對這種情況,研究人員進行了大量相關工作,其中求解近似覆蓋圖是目前一種代表性的研究方法,得到廣泛的關注.該方法通過近似解代替精確解,以此降低存儲精度需求,進而降低存儲與計算代價.考慮到在許多應用中,對圖中節點間連接信息的需求精度不高,可以在保持節點間連通性的前提下刪除大量邊,僅保留節點間近似的路徑長度,形成對原圖的一種近似覆蓋.這種方法通常以2個參數α與β約束近似圖與原圖中節點間路徑長度的變化程度,稱為原圖的(α,β)-覆蓋.文獻[2]提出一種確定性算法,可以獲得(k,k-1)-覆蓋,該算法適用于無向無權圖,其時間復雜度為O(m+n),空間復雜度為O(k×n),其中n與m分別為圖數據中節點與邊的數量.同時,該文獻還證明了對于無向圖的(1,6)-覆蓋,在空間復雜度為O(n)的情況下,都能夠在時間復雜度最高為O(mn).文獻[3]提出一種適用于加權無向圖的隨機性算法,該算法可以獲得(2k-1,0)-覆蓋,其時間復雜度為O(m+n),空間復雜度為O(k×n).文獻[4]則提出了與文獻[3]相同使用環境與目標的非隨機性算法,其時間復雜度也同樣為O(m+n).

較早的研究工作多集中針對靜態無向圖,考慮到數據的動態變化,特別是邊的插入與刪除,文獻[5]提出的方法可以在O(n)條邊的插入與刪除過程中,獲得(3,0)-覆蓋與(5,0)-覆蓋,處理每次邊變化的時間復雜度與原圖最大度值呈線性關系,算法所得到(3,0)-覆蓋邊數為O(n),而(5,0)-覆蓋邊數則為O(n).文獻[6]提出了一種可更加快速獲得(2k-1,0)-覆蓋的隨機動態算法,空間復雜度為O(k×n),處理每次邊變化的時間復雜度為O(mn).文獻[7]提出的方法能夠動態構造(1+ε)-覆蓋,其更新時間為O(logn),其中ε為常數參數.

隨著數據量級以及變化速度的不斷增大,流模式下近似覆蓋圖的計算逐漸成為研究熱點.文獻[8]提出了一種適用于無向無權圖的隨機算法,該算法僅通過1次掃描可以獲得(2k+1,0)-覆蓋,其空間大小為O(k×n),平均處理1條邊的時間為O(k2×n×logn),所需內存大小為O(k2×n×logn)字節.文獻[9]提出的方法可以通過1次掃描獲得空間大小為O(k×n)的(2k-1,0)-覆蓋,其整體時間復雜度為O(m+n),所需內存大小為O(k×n).文獻[10]提出了一種非嚴格流模式下的算法,該算法假定數據傳輸以塊的模式進行,內存中保留與節點有關的信息,算法所需的內存大小為O(n),所需外部存儲塊為O(nB),其中B是外部存儲塊的大小.文獻[11]提出基于采樣的流模式近似覆蓋圖算法,該算法對每條邊的平均處理時間為O(max{llogn,1}),其中l為子圖數量.

近年來,基于其他覆蓋形式以及不同距離含義的研究也得到一定程度的關注,例如圖的近似樹形覆蓋[12-14]以及有向圖環境下基于往返距離[15-17]與平面距離的近似覆蓋圖[18-19]等.綜合看來,目前的研究工作大多集中于無向圖環境,有少量針對有向圖的研究,但其側重點以及應用環境與傳統方法相比差異較大.本文針對有向圖環境,研究基于傳統距離含義的近似覆蓋圖計算,定義相關概念,進而給出具體算法,并通過理論分析以及實驗,說明算法的有效性.

本文的主要工作有3個方面:

1) 針對有向圖特點,重新定義近似覆蓋圖的相關概念,包括簇集以及簇邊、橋邊、自由邊這3類關鍵邊;

2) 分析了求解近似覆蓋圖過程中,簇集的形成、3類關鍵邊的確定以及關鍵邊類型可能發生的轉化,論證了3類關鍵邊形成的子圖滿足覆蓋因子為(3,2)的近似覆蓋圖定義;

3) 給出了在流模式下求解有向圖近似覆蓋的算法,依據在模擬數據集上的實驗結果,對該算法進行了定量分析,并與無向圖近似覆蓋算法進行了定性對比分析,綜合說明算法較佳的時空效率.

1 相關概念

本節給出有向圖的近似覆蓋圖計算所需相關定義的形式化描述,并論證其合理性.

1.1 基本定義

本文所需基礎定義為圖G=(V,E),其中，

V:圖中節點的集合;

E:圖中邊(節點對間的連接)的集合;

deg(v):圖中與節點v(v∈V)連接的邊數,稱為該節點的度;

deg_in(v):有向圖中射入節點v的邊數,稱為該節點的入度;

deg_out(v):有向圖中由節點v射出的邊數,稱為該節點的出度;

d(u,v):圖中節點u到v經過最少的邊數,稱為節點對(u,v)間的距離.若u到v之間不存在連通路徑,記距離d(u,v)為正無窮.無向圖中d(u,v)=d(v,u);

Pre(x):節點x所有前趨節點的集合,即對于任意的節點a,若a,x∈E,則a∈Pre(x);

Next(x):節點x所有后繼節點的集合,即對于任意的節點b,若x,b∈E,則b∈Next(x);

N(x):節點x的鄰節點集合,且包含x自身.

圖G的近似覆蓋圖是一個與圖G擁有相同的節點集合的子圖,且該子圖保存了圖G中任意節點對之間距離的近似.

定義1. 近似覆蓋圖.設圖G=(V,E),給定參數α≥1,β≥0,若對于G′=(V,E′)中任意的節點對(u,v),均滿足：

d′(u,v)≤d(u,v)×α+β,

(1)

則稱子圖G′是圖G的近似覆蓋圖,記作(α,β)-覆蓋,參數α與β稱為覆蓋因子.

式(1)中d′(u,v)表示節點對(u,v)在G′中的距離.依參數α=1或參數β=0,稱對應的近似覆蓋圖為簡單加性近似覆蓋圖或簡單乘積近似覆蓋圖.若參數α與β取值過小,則近似覆蓋圖與原圖的差異不大,降低存儲計算開銷的作用不明顯,而參數α與β取值過大的話,則相對原圖來說細節損失過多,不適合進一步的計算分析.因此,適當的參數選取才能夠較為充分地發揮近似覆蓋圖的作用.參考現有研究工作的參數選擇,本文設定覆蓋因子α=3,β=2,即計算圖G的(3,2)-覆蓋.

1.2 簇 集

本文算法基本思路為獲得原圖的一個適當的聚簇結果,有選擇地刪除簇內及簇間的部分邊,由此得到原圖的一個近似覆蓋.本節給出簇集以及相關定義如下.

定義2. 簇集.令x1,x2,…,xk為節點集V中的若干節點,取其中每個節點前驅集與后繼集的不小于l的子集,分別合并為k個集合,即：

Up(xi)?Pre(xi),|Up(xi)|≥l,

(2)

Down(xi)?Next(xi),|Down(xi)|≥l,

(3)

Cl(xi)=Up(xi)∪Down(xi)∪{xi},

(4)

其中，k≥1,l≥1且1≤i≤k,若滿足：

(5)

則稱這些集合{Cl(xi)}為圖G的l類簇集.

圖G的l類簇集中,稱每個集合Cl(xi)為簇,節點xi為該簇的中心節點,分別稱集合Up(xi)與Down(xi)為該簇的上簇節點與下簇節點,合稱該簇的簇節點,而不屬于任何簇的節點則稱為自由節點.由定義1可見,簇之間可能存在重疊,同時屬于多個簇的節點,其在各個簇中的角色也可能不同.對于簇節點x,依據節點x為這些簇的上簇節點或下簇節點,對應簇的中心節點集合分別表示為center_up(x)或center_down(x).圖1為一個簡單的3類簇集示意,為清晰起見,省略了簇節點之間包含在簇內的邊.圖1中節點a,b分別為簇Cl(a),Cl(b)的簇中心節點,同時節點a在簇Cl(b)中為簇節點,節點b在簇Cl(a)中也為簇節點.節點c同時屬于2個簇,且均為下簇節點,因此集合center_down(c)={Cl(a),Cl(b)}.

Fig. 1 3-clustering圖1 3類簇集

定義3. 自由鄰節點集合.對于圖G中的節點v,其自由鄰節點集合為

(6)

由定義2可以看出,1個節點可以同時屬于多個簇,所以1個l類簇集最多可以有n個簇,每個簇至少包含l個節點以及2l條有向邊.結合定義3可知,若給定1個l類簇集,對于圖中任意的節點v來說均有|FN(v)|<2l成立,則該l類簇集顯然是最大化的.

1.3 關鍵邊

對于圖G中的任意邊u,v是否保存在近似覆蓋子圖G′中,本節分為簇邊、橋邊與自由邊3類關鍵邊討論,其中與簇中心節點相連的邊均保存為該簇的簇邊,余下分3種情況討論：

1) 當節點u與v同屬1個簇Cl(x),若u∈Up(x),v∈Down(x),則邊u,v不需要保存；除此之外,則臨時標記邊u,v為自由邊.顯然,邊的始點與終點分別為同簇內的上簇節點與下簇節點時,存在由簇中心點轉接的長度為2的路徑,由原圖中去除該邊不影響節點間可達性,且節點間距離僅增加1.

2) 當節點u與v分屬2個不同簇Cl(x1),Cl(x2)時,進一步分3種情況來討論:

① 當u∈Down(x1),v∈Up(x2)時,邊u,v保存為連接簇Cl(x1)與Cl(x2)的橋邊.

② 當u∈Up(x1),v∈Up(x2)時,若不存在以節點v為終點的橋邊a,v,則臨時標記邊u,v為自由邊.如圖2所示,節點x1與x2為簇中心節點,節點u與v分別為各簇的上簇節點,圖2中虛線邊為簇間橋邊,若該橋邊不存在,則邊u,v需保存于近似覆蓋圖中,以保證節點u與v之間可達.

③ 當u∈Cl(x1),v∈Down(x2)時,若簇對Cl(x1)與Cl(x2)之間不存在橋邊,則臨時標記邊u,v為自由邊.如圖3所示,節點x1與x2為簇中心節點,節點u為Cl(x1)中的簇節點,節點v為Cl(x2)中的上簇節點,圖3中虛線邊為簇間橋邊,若該橋邊不存在,則邊u,v需保存于近似覆蓋圖中,以保證節點u與v之間可達.

Fig. 3 Edge between different cluster from Cluster-node to Down-node圖3 簇節點指向下簇節點的簇間邊

3) 節點u與v中的任意一個節點為自由節點,則臨時標記邊u,v為自由邊.

由于同一節點可能屬于多個簇,因此上述3種情況可能有所重疊,所以明確不同類型邊的保存規則有4項:

① 簇邊均需保存;

② 至少滿足1對簇間橋邊定義,需保存;

③ 1個端點為自由節點的自由邊需保存;

④ 簇內自由邊與簇間自由邊,若不存在包含邊的2個端點,且始點為上簇節點,終點為下簇節點的簇,則需保存.

考慮聚簇過程如下：當臨時自由邊數量達到一定閾值時,對其進行聚類形成新簇,具體來說當以某節點u為始點及終點的臨時自由邊數量均超過閾值l時,則形成新簇Cl(u),節點u為該簇中心節點,節點u的所有臨時自由前趨節點與自由后繼節點分別為該簇的上簇節點與下簇節點.

在聚簇過程中部分臨時自由邊會轉為簇邊或橋邊保存,而部分臨時自由邊可能轉變為無需保存的冗余邊從而被刪除,最終所得近似圖覆蓋子圖中可能仍保存有未被刪除的自由邊,因此近似圖覆蓋子圖是由簇邊、橋邊以及自由邊形成的集合.

1.4 合理性證明

由1.3節對簇邊、橋邊以及自由邊的描述,可以證明對于給定有向圖G=(V,E)及圖上的1個l類簇集,若子圖G′=(V,E′)是圖G的(3,2)-覆蓋,即滿足：

d′(u,v)≤3d(u,v)+2,

(7)

則E′為這3類關鍵邊的集合.為此,觀察圖G中任意邊u,v在子圖G′中對應的以u為起點且v為終點的路徑,可分4種情況討論.需要注意的是,在聚簇過程中,簇內自由邊或簇間自由邊可能轉變為新簇內上簇節點指向下簇節點的冗余邊,從而被刪除,使得原來長度為1的自由邊轉變成了2條簇邊形成的長度為2的路徑:

1) 當節點u,v中至少有1個節點是簇中心點時,則邊u,v為圖G′中的1條簇邊,此時d′(u,v)=1.

2) 當節點u,v中至少有1個節點是自由節點且沒有簇中心節點時,則u,v為圖G′中的1條自由邊,此時d′(u,v)=1.

3) 當節點u,v同屬1個簇Cl(x)時,若u∈Up(x),v∈Down(x),則邊u,x,x,v為圖G′中的簇邊,此時d′(u,v)=2.否則邊u,v為圖G′中的簇內自由邊,此時d′(u,v)=1或2.

4) 當節點u,v分屬2個不同簇Cl(x1),Cl(x2)時,又細分為4種情況:

① 當u∈Down(x1),v∈Up(x2)時,則邊u,v為圖G′中的橋邊,此時d′(u,v)=1；

② 當u∈Down(x1),v∈Down(x2)時,若圖G′中存在橋邊u,a,其中a∈Up(x2),則該橋邊與簇邊a,x2,x2,v構成圖G′中的1條路徑,此時d′(u,v)=3.否則,u,v為圖G′中的簇間自由邊,此時d′(u,v)=1或2；

③ 當u∈Up(x1),v∈Up(x2)時,若圖G′中存在邊a,v,其中a∈Down(x1),則簇邊u,x1,x1,a與該邊構成圖G′中的1條路徑,此時d′(u,v)=3.否則,u,v為圖G′中的簇間自由邊,此時d′(u,v)=1或2；

④ 當u∈Up(x1),v∈Down(x2)時,若圖G′中存在橋邊a,b,其中a∈Down(x1),b∈Up(x2),則圖G′中存在路徑{u,x1,x1,a,a,b,b,x2,x2,v},此時d′(u,v)=5.否則,u,v為圖G′中的簇間自由邊,此時d′(u,v)=1或2.

由以上分析可以看出,除最后1種情況外,均滿足d′(u,v)≤3d(u,v).將觀察范圍擴展為圖G中的路徑D={u1,u2,u2,u3…ui-1,vi},顯然有:

(8)

再觀察前述最后1種情況(同時也是最壞情況),即每個節點uj分別屬于簇Cl(xj),其中1≤j≤i,且圖G中相鄰節點在子圖G′中需要經過始點所在簇中心節點以及橋邊轉接至相鄰簇,再經相鄰簇中心節點連接至終點,因這2部分子路徑的長度分別為3和2,則對于圖G中邊u1,u2來說,有:

d′(u1,u2)=3d(u1,u2)+2.

(9)

式(9)中右部第1項為簇Cl(x1)中2次轉接及1次橋邊轉接,第2項為簇Cl(x2)中的2次轉接.進一步考慮圖G中路徑D的下一條邊u2,u3,在子圖G′中節點u1到達u3則需要多經過1個簇,因此增加2次簇中轉接及1次橋邊轉接,即式(10)中右邊第2項:

d′(u1,u3)=3d(u1,u2)+3d(u2,u3)+2.

(10)

以此類推,可得：

(11)

因此可得,在所有情況下子圖G′均是滿足定義1覆蓋因子為(3,2)的近似覆蓋圖,即圖G的(3,2)-覆蓋.

2 流模式下有向近似覆蓋圖算法

本節給出有向圖中計算近似覆蓋圖算法的基本思想以及算法中需要保存的臨時信息,以偽代碼的形式給出算法具體過程的描述,并分析了算法空間效率.

2.1 算法基本思想

圖數據以邊的形式存儲,按邊的端點排序后以流模式輸入.算法或者建立上簇節點與下簇節點均至少為l個的新簇,或者將輸入邊的端點添加至已存在的簇.在處理節點的同時,輸入邊可能保存為簇邊或橋邊,也可能被拋棄,剩余邊均標記為自由邊,臨時保存在候選自由邊集合中.當候選自由邊集合大小超過閾值時,將對其進行聚類形成新簇,這樣即使簇邊u,v的起點u距離終點v較遠,使得邊的輸入位于數據流早期時,仍然可以形成以v為中心節點的簇.

具體算法中,每個節點x存儲2種信息:

1) 標識節點x是簇節點、自由節點或簇中心點的狀態標志.若節點x為簇節點,還需存儲包含x的所有簇的標志,以及集合center_up(x)與center_down(x)；若節點x是某個簇的中心節點,則需保存該簇的Up(x)與Down(x)集合.

2) 臨時自由邊的集合Tpre(x)與Tnext(x).其中Tpre(x)包含了節點x的所有前趨自由邊,Tnext(x)包含了節點x的所有后繼自由邊.隨著算法的運行導致節點狀態發生改變,這2個集合中可能會包含一些非自由邊,將在自由邊集聚類時刪除.

簇邊保存在對應簇邊集合中,橋邊存儲在矩陣Bridge中,Bridge[i,j]存儲連接簇Ci到簇Cj的橋邊集合.若簇Ci與簇Cj之間不存在橋邊,則Bridge[i,j]顯然為空.但反之未必成立,即Bridge[i,j]為空時,可能存在連接簇Ci與Cj的橋邊,保存在Tpre(x)或Tnext(x)中.

2.2 算法描述

算法通過判斷邊端點類型來決定邊是否需要保存以及保存為何種類型.若端點包含簇中心點則保存邊為簇邊,否則先考慮是否滿足橋邊定義,之后判斷是否屬于同簇內上簇節點指向下簇節點,最后分3種情況考察是否為自由邊.當節點自由邊數量超過閾值時,開始聚集新簇,并刪除新簇中可能的冗余邊.

算法1. 流模式下有向近似覆蓋圖的計算.

輸入:前一時刻有向圖G、當前到達的邊x,y;

輸出:當前時刻聚簇以及3類關鍵邊.

① ifx或y為簇中心點

③ ify為自由節點

④ 添加y至Down(x);

⑤ 更新y標識為簇節點;

⑥ end if

⑦ ifx為自由節點

⑧ 添加x至Up(y);

⑨ 更新x標識為簇節點;

⑩ end if

〈u,v〉;

算法1中,簇邊與橋邊自初次保存后一直存在,端點為自由節點的自由邊在端點標識改變之前一直保存,之后可能隨著聚集新簇成為簇邊,或成為橋邊,或繼續保存為自由邊,還可能任意一個保存條件都不再滿足從而刪除.顯然,算法滿足2.3節給出的不同類型邊的保存規則.

2.3 算法分析

依據2.2節給出的算法描述,本節分析該算法在有向圖中求得的近似圖覆蓋子圖邊集的大小.由圖4所示,有向圖中的節點可看作上下2部分,圖4中的邊均由上半部分中指向下半部分.這種情況下,若刪除其中的任意1條邊,則某2個節點之間不再連通,稱這種結構為結構.

Fig. 4 structure圖4 結構

考慮圖G的節點v,若滿足deg_in(v)≥n且deg_out(v)≥n,則進行聚類操作形成簇Cl(v).設簇總數為k,則最壞情況下簇邊的數量為(n-k)×k,當k=n2時達到最大值,即簇邊的數量不超過O(n24).

考慮與簇Cl(v)相連的節點u,以節點u為始點連接簇Cl(v)的邊集合u,X,則滿足X?Up(v)或者X?Down(v),但2者不會同時滿足.因此聚類操作得到2部分結果:或是聚類成簇,則除了簇邊以外的橋邊及自由邊形成結構;或是部分節點的出度或入度之一小于n,不足以形成新簇,保存為自由邊.其中結構顯然可以判斷出邊的數量不超過O(n24).

對于滿足deg_in(v)

由此可得,圖G′=(V,E′)為關聯到n類最大化簇集的(3,2)-覆蓋,則G′包含O(n24)條邊.

3 實驗與分析

3.1 實驗環境與方法

實驗運行的硬件環境為英特爾酷睿雙核處理器,主頻2.2 GHz、內存8 GB、軟件環境為Linux操作系統,算法由C語言編寫實現,使用gcc進行編譯.實驗數據使用冪率模型生成的人工數據集,此類圖中節點的度分布呈現冪率分布,與互聯網、社交網、交通網以及蛋白質生物網絡等現實世界中的大規模圖數據類似,普遍具有小世界與無標度等宏觀拓撲特性[20-22],是圖分析領域廣泛選用的實驗數據集,適用于本文的算法實驗分析.本文具體采用基于遞歸矩陣(R-MAT)的網絡模型[23],生成節點數量為8 000,平均度分別為50,200,800,3 200的4個人工圖數據集,對比算法在不同數據集上的運行效果.

算法的具體實現中,使用散列表存儲節點所需的信息,為每個節點保存1個32 b的標簽作為散列表鍵值.當1條有向邊以流的形式到達時,首先判斷該邊的2個端點是否首次出現.若是首次出現的新節點,則創建1個與該節點對應的散列表項,否則根據節點的標簽檢索到對應的散列表項并根據需要進行更新.

對于非對稱的橋邊集矩陣Bridge,也使用散列表來保存橋邊列表,并采用64 b的散列鍵值.當1條有向邊判定為橋邊,需要保存至列表中時,將該邊的2個端點各自的32 b標簽值連接為1個64 b鍵值,這樣由標簽值的連接次序就可以區別同一對節點對應的2條有向邊.橋邊的存儲按其64 b鍵值將該邊插入到橋邊列表的相應位置,而當檢索某2個簇間的橋邊是否存在時,則同樣按其64 b鍵值在散列表中進行查找.

3.2 實驗結果

本文實驗中主要考察3項指標:

1) 平均伸展率是指圖中所有節點對(x,y)在近似覆蓋圖與原圖中距離之比d′(x,y)d(x,y)的平均值.實際計算中普遍使用采樣估算值,即隨機選取一定比例的節點對進行計算,在大幅減少計算量的同時,結果的精度也有一定的保證.依據定義所得理論上限值通常稱為最大伸展率,由覆蓋因子決定,而在實際上近似覆蓋圖中的節點對并不都處于理論上的極限情況,因此平均伸展率比最大伸展率要小.

2) 近似圖覆蓋比例是指近似圖覆蓋中邊的數量與原圖中邊的數量之比,體現算法的空間效率.

3) 運行時間即算法在數據集上運行的時間,體現其時間效率.

圖5所示是近似圖覆蓋比例隨著聚簇閾值的改變表現出的不同情況,圖5中4條折線分別表示本文算法在4個不同人工圖數據集上運行的結果.由圖中可以看出,隨著圖數據集的密度增大,即邊的數量增加,近似圖覆蓋比例逐漸下降.這是由于在高密度的圖數據集中,節點對之間的路徑較多,其中滿足最大伸縮因子的路徑數量也較多,因此大量的邊均不需保存在近似覆蓋子圖中,使得覆蓋圖與原圖的邊數量比較低.

Fig. 5 Coverage ratio on different dataset圖5 不同數據集上的覆蓋比例

同時由圖5中還可以看出,近似圖覆蓋比例隨著聚簇閾值的增大呈U型變化.當聚簇閾值較小時,簇的數量較大,則需保存大量的簇間橋邊,同時由于單個簇中節點較少,節點間的簇內連接(包括簇邊和自由邊)保留比例較高,使得整體覆蓋比例較高.當聚簇閾值較大時,大量節點由于無法聚簇而成為自由節點,導致大量的自由邊需要保存在近似圖覆蓋子圖中,使得近似圖覆蓋比例較高.特別是在低密度圖數據集中,當聚簇閾值較大,甚至大于圖中節點平均度時,只能形成數量極少的簇,此時近似圖覆蓋比例極高.

現有無向圖近似覆蓋的研究成果中,最佳聚簇閾值大多設為n1/3,對應本文實驗中圖數據集的節點數量,則最佳閾值為20.由實驗結果可以看到,4個數據集在聚簇閾值為20左右時表現一致,所得近似圖覆蓋比例均為最低(不同數據集約為 0.001～0.01左右),驗證了本文的理論分析,即近似覆蓋圖中邊的數量主要與節點數量相關,這與相關無向圖的研究結果也是一致.同時較低的最優覆蓋比例也符合真實大規模圖的拓撲統計特性,即圖中節點平均度不高的同時,節點間的最短路徑仍然較短,即所謂的小世界特性.特別是近似覆蓋圖的節點間路徑長度約束較原圖更寬,所需邊的數量更少,因此所得最優近似圖覆蓋比例極低,極大的降低了圖數據存儲的空間開銷.

圖6所示是平均伸展率隨著聚簇閾值的改變表現出的不同情況,圖6中4條折線分別表示本文算法在4個不同人工圖數據集上運行的結果,其中平均伸展率是采用隨機選取10 000對節點計算所得的采樣估算值.由圖6中可以看出平均伸展率隨著聚簇閾值的增大基本呈倒U型變化,與圖5中的近似圖覆蓋比例變化相對應,即近似圖中保存的邊比例越高,節點間路徑越接近原圖,平均伸展率越小.當聚簇閾值較小時,較多的簇內與簇間連接使得節點間的路徑與原圖相比變化較小,因此平均伸展率較小.當聚簇閾值較大時,形成少量的簇與大量自由節點,原圖中許多節點間的路徑由大量的自由邊維持下來,使得平均伸展因子趨近于1.當聚簇閾值為20左右時,近似圖覆蓋比例最低,而此時平均伸展率較大.由于刪除了原圖中大量的邊,因此很多相鄰節點不再保持有直接的鄰居關系,而是需要由始點經過若干次轉接間接到達終點.圖6中實驗結果顯示,平均伸展因子峰值為3.08,接近定義1給出的理論上限3x+2.

Fig. 6 Stretch ratio on different dataset圖6 不同數據集上的伸展率

4個數據集的數據曲線趨勢基本一致,且隨著數據集節點平均度的增加,平均伸展率有所增大.這顯然是由于低密度圖的近似覆蓋比例較高,近似圖中保留的邊相對更多,使得節點間路徑變化更小,這同樣與圖5所示相對應.

Fig. 7 Runtime on different dataset圖7 不同數據集上的運行時間

圖7所示是算法運行時間隨著聚簇閾值的改變表現出的不同情況,圖7中4條折線分別表示本文算法在4個不同人工圖數據集上運行的結果.由圖7中可以明顯看出,算法在節點平均度較低的圖數據集上運行時間較短,這是因為同樣聚簇閾值下,算法在稀疏的圖數據集中需要處理的邊的數量較少.

同時由圖7中還可以看出算法運行時間隨著聚簇閾值的增大呈下降趨勢.由算法描述可知,較大的時間開銷一部分在于Tpre(x)與Tnext(x)這2個集合中邊信息的處理,并且需要遍歷節點x鄰接點所屬簇,另一部分在于邊端點均為簇節點時,需要判斷其所屬的多個簇之間的重疊情況,因此簇的數量極大的影響算法時間效率.當聚簇閾值較小時,運行時間較長,隨著聚簇閾值增大,簇的數量顯著減少,算法運行時間也隨之明顯縮短,但當聚簇閾值繼續增大時,由于所保存邊的數量達到最小值后開始增加,運行時間縮短的趨勢開始平緩.

3.3 與無向圖的對比分析

本文算法適用于計算有向圖的近似覆蓋圖,而相關研究工作多針對無向圖環境,且少有的針對有向圖環境的研究,其距離的定義較為特殊,不具有普遍意義,因此算法效率之間直接的定量對比沒有明確的意義.直觀看來,與相同規模(節點與邊的數量相同)的無向圖相比,有向圖的近似覆蓋圖中保留的邊顯然更多,存儲開銷更大,算法的時間復雜度也更高.本節定性的分析本文算法與同為聚簇方法的無向圖環境下近似覆蓋圖算法相比,空間與時間開銷存在差異的原因.

本文算法存儲空間的額外需求主要是自由邊的增加.為保證同簇內上簇節點之間、下簇節點之間以及下簇節點到上簇節點的連通,在近似覆蓋圖中保留了許多簇內自由邊,這類邊在無向圖環境下是不需要保存的.盡管隨著數據流的到達,在逐步聚簇的過程中刪除了其中的冗余,但仍有一部分保留至最終的近似覆蓋圖,增加了存儲開銷.類似地為保證簇間節點的連通性,當邊的2個端點分別為不同簇的上簇節點,若當前橋邊不滿足端點間連通的需求,則需要保留簇間自由邊,或者當邊終點為與始點不同簇的下簇節點時,若當前沒有橋邊,則也需要保留簇間自由邊.簇間自由邊類似于額外的橋邊,這類邊在無向圖環境下是也不需要保存的.

時間開銷方面,當邊到達時,本文算法需要考慮的情況比無向圖環境下更為復雜.當邊端點均為簇節點時,本文算法需要判斷該邊是否應保留為簇內自由邊、簇間自由邊或者橋邊,因此要進行多次集合的交與并操作,而無向圖僅需判斷2個端點是否同簇.當自由邊數量超過閾值時從而需要刪除其中冗余時,本文算法需要再次判斷這些邊是否應保留為簇內自由邊、簇間自由邊或者橋邊,而無向圖僅需判斷端點是否仍是自由節點.聚簇過程中,對于新簇內可能出現的簇內自由邊冗余,本文算法需要通過遍歷相關上簇節點與下簇節點集刪除這部分冗余,而無向圖中并不存在簇內自由邊,因此不需要進行這部分處理.

由以上分析可以看出,本文算法相比無向圖環境下的算法,時空開銷均有所增加,但其原因是由于保證有向圖節點間連通所帶來的復雜性的增加.相對于有向圖與無向圖之間復雜度的差異,本文算法復雜度的增加十分有限,可以認為其時空效率較佳.

4 總 結

本文以有向圖為研究對象,重新定義了近似覆蓋圖計算過程中所需的相關概念,包括簇集與簇邊、橋邊、自由邊3類關鍵邊,以及由有向圖簇衍生出的上簇節點與下簇節點等不同類型的節點.通過理論分析的方式,證明了這3類邊的集合滿足覆蓋因子為(3,2)的有向近似覆蓋圖的定義.針對圖數據以流模式到達的情況,本文給出依次處理每條到達邊的具體算法.算法通過判斷邊端點的類型,據此將到達邊拋棄或保存適合類型,并在滿足聚簇閾值時形成新簇,最終得到包含簇邊、簇間橋邊以及自由邊的近似覆蓋圖.算法空間開銷的理論分析結果表明,對于包含n個節點的有向圖G,其最大化簇集的(3,2)-覆蓋包含O(n24)條邊.最后,考慮冪指數特性是現實大規模圖數據的普遍規律,本文實驗數據選取以冪指數模型為基礎的人工圖數據,通過對比節點平均度不同的圖數據,觀察隨聚簇閾值變化時,算法的空間時間效率等方面的變化.實驗結果表明：本文算法在滿足覆蓋因子約束的前提下,時空效率均較好.