基于大規(guī)模網(wǎng)絡(luò)的可達性研究

張兆坤

（四川大學計算機學院，成都 610065)

0 引言

可達性是圖論中的基本問題，它回答了一個結(jié)點u是否可以通過一條簡單的路徑到達另一個結(jié)點v。目前，可達性查詢已被廣泛應用于計算機科學領(lǐng)域，包括軟件工程、編程語言和分布式計算等。早期關(guān)于數(shù)據(jù)庫領(lǐng)域的可達性研究主要應用于遞歸運算和知識管理。豐富的圖表數(shù)據(jù)（來自生物學、社交網(wǎng)絡(luò)、軟件分析、語義網(wǎng)絡(luò)）的出現(xiàn)，對可達性查詢提出了新的挑戰(zhàn)，使得可達性研究重新引起了廣大研究學者的關(guān)注。

現(xiàn)有可達性查詢方法的主要思想是在原始網(wǎng)絡(luò)上建立有效的索引來加速查詢，同時尋找一個（a）在線查詢時間，（b）索引建立時間，（c）索引空間大小之間的平衡。這些方法大致分為兩類：標簽索引法，索引加遍歷法，其中，標簽索引法，顧名思義即采用迭代閉包的方法為網(wǎng)絡(luò)中的結(jié)點添加標簽進行索引；索引加遍歷法，即在建立索引的基礎(chǔ)上對網(wǎng)絡(luò)中的結(jié)點進行遍歷，該方法可以有效減少索引建立的時間。然而，大多數(shù)方法在處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)（例如，快速增長的社交網(wǎng)絡(luò)數(shù)據(jù)）時都面臨可擴展性的挑戰(zhàn)。

本文針對該問題提出一個統(tǒng)一的框架MRN（Mul?tiple Resolution Networks），該框架的核心思想為在保留大規(guī)模網(wǎng)絡(luò)的可達性信息的前提下，縮小網(wǎng)絡(luò)規(guī)模。MRN是一個層次結(jié)構(gòu)，是對原始網(wǎng)絡(luò)在不同解析度下的描述，同時構(gòu)建MRN可以作為一步網(wǎng)絡(luò)圖預處理方法用于任意可達性查詢方法，從而加快可達性查詢速度。

實驗證明，MRN可以在保留大規(guī)模網(wǎng)絡(luò)包含的可達性信息的同時縮小其規(guī)模，同時MRN可以應用于任意現(xiàn)有的可達性查詢方法，加快查詢速度。

1 算法實現(xiàn)

MRN是對大規(guī)模網(wǎng)絡(luò)在不同解析度下的描述，其本質(zhì)上是一個層次網(wǎng)絡(luò)，以世界地圖為例，其MRN即在城市、國家、板塊等解析度下對世界地圖中可達信息的描述。在本文中，假設(shè)MRN有r層，MRN的正式定義如下：

定義 1（Multiple Resolution Network（MRN））給定無向圖G=（V,E），V和E分別為G的點集和邊集，其第i層的MRN記為Gi=（Vi,Ei），其中Vi為第i層MRN的點集，Ei為第i層MRN的邊集。Vi中的任意結(jié)點v表示Gi+1的一個聯(lián)通子圖，Ei為Vi中任意兩結(jié)點之間的邊組成的集合。第r層MRN即原始圖G。

根據(jù)定義1可得，對于任意給定的圖G，它有r個MRN，{G1，G2，…，Gr}，每一個 MRN 都保留了原始圖 G中的可達性信息，即在G中可達的兩個結(jié)點，在任意層次的MRP中仍然可達，反之亦然。

MRN通過迭代的方式構(gòu)建，如定義1所述，第i層MRN中的一個結(jié)點表示第i+1層MRN結(jié)點的聚類，第i層MRN中的邊為第i+1層MRN中分屬于不同聚類的點之間的邊。在構(gòu)建第i層的MRN時，我們的目標是對第i+1層的MRN進行劃分，使其模塊度盡可能大，第i+1層MRN中每一個簇構(gòu)成了第i層MRN中的一個結(jié)點，模塊度的定義如下：

其中，Au,v是連接結(jié)點 u和 v的邊的權(quán)值，ku=∑vAu,v是與結(jié)點u相連的邊的權(quán)值之和，C()u為結(jié)點u所在的簇編號，若結(jié)點u和結(jié)點v屬于同一個簇，δ函數(shù)返回1，否則返回0，m=∑uvAu,v。然而，每次迭代計算時直接更新Q計算量巨大，為了提高效率，我們用模塊增益代替模塊度，模塊增益定義如下：

其中，σin是結(jié)點v所在的簇C（v）的入邊的權(quán)值之和，σtot是結(jié)點v所在的簇C（v）的出邊的權(quán)值之和，σin是結(jié)點v所在的簇C（v）的入邊的權(quán)值之和，ku,in是連接結(jié)點u和結(jié)點v所在的簇C（v）中結(jié)點的邊的權(quán)值之和。

下面給出MRN的具體構(gòu)建過程：

輸入： 給定網(wǎng)絡(luò)圖G=（V,E）

輸出： MRN 集合：M={G1，G2，…，Gr}

將V中各結(jié)點初始化為一個簇，計算初始模塊度Q；

2 實驗

為了驗證MRN的有效性，本文分別在兩個數(shù)據(jù)集Facebook和DBLP上構(gòu)建MRN，同時將MRN應用于BFS（廣度優(yōu)先遍歷）和DFS（深度優(yōu)先遍歷），對比其在可達性查詢時間上的效率。通過對比實驗結(jié)果，發(fā)現(xiàn)MRN可以高效縮小原圖的規(guī)模，加快可達性查詢速度。

圖1 邊的數(shù)量隨迭代次數(shù)的變化

圖2點的數(shù)量隨迭代次數(shù)的變化

圖1 和圖2分別顯示了MRN在Facebook和DBLP兩個數(shù)據(jù)集上對點和邊規(guī)模的縮小效果，可以看出在MRN兩個數(shù)據(jù)集上均高效縮小了原圖規(guī)模，僅經(jīng)過3次迭代，兩個數(shù)據(jù)集上邊和結(jié)點數(shù)量均縮小了2-3個數(shù)量級。

本文分別在Facebook和DBLP上隨機生成2000對結(jié)點，表1顯示了BFS和DFS及他們的MRN版本在Facebook和DBLP上進行可達性查詢的時間（單位：秒）對比?？梢钥闯?，MRN在Facebook和DBLP兩個數(shù)據(jù)集上都加速了BFS和DFS可達性查詢的時間，時間提高了3-6個數(shù)量級。可達性時間的縮減是因為MRN高效地縮小了原圖的規(guī)模，并保留了原圖中的可達性信息。

表1 可達性查詢時間

3 結(jié)論

本文提出的MRN框架，可以有效地對縮小網(wǎng)絡(luò)規(guī)模，加速現(xiàn)有可達性查詢的速度，同時MRN具有層次機構(gòu)，可以在不同解析度下描述結(jié)點的可達性。MRN最大的優(yōu)勢在于，其作為一個統(tǒng)一的框架，可以應用于任何現(xiàn)有的可達性查詢方法。MRN在現(xiàn)實應用中具有實際意義，尤其在大規(guī)模網(wǎng)絡(luò)中進行可大型查詢時，可以顯著地加速現(xiàn)有可達性查詢方法的效率。

[1]吳祖峰，王鵬飛等．改進的Louvain社團劃分算法[J]．成都：電子科技大學學報，2003.

[2]Ruoming Jin，Ning Ruan.SCARAB:Scaling Reachability Computation on Large Graphs[C].ACM SIGMOD International Conference on Management of Data,pp.169-180.ACM(2012).

[3]Newman,M.E.,Girvan,M.:Finding and evaluating community structure in networks[J].Physical Review E 69(2),026,113(2004).

[4]Blondel,V.D.,Guillaume,J.L.,Lambiotte,R.,Lefebvre,E.:Fast Unfolding of Communities in Large Networks[J].Journal of Statistical Mechanics:Theory and Experiment 2008(10),P10,008(2008).

[5]Chen,H.,Jin,H.:Finding and Evaluating the Community Structure in Semantic Peerto-Peer Overlay Networks[J].Science China Information Sciences 54(7),1340-1351(2011).