劉 冬，杜 明，王志軍，周軍峰

(東華大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620)

0 引言

在無向圖G=(V,E)中，任意兩個頂點u、v間的最短路徑dist(u,v)指的是從u到v的路徑的最小長度。從u出發(fā)的一條最長最短路徑則是頂點u的偏心率，得知頂點的偏心率有助于分析圖的其他特征，比如圖的中心性、半徑和直徑等。頂點的偏心率越小，它在圖中的中心性越高，表示該頂點距離其他頂點更近。在一些實際的應(yīng)用場景里，偏心率求解是十分重要的，比如尋找社交網(wǎng)絡(luò)中有影響力的人、流行病關(guān)系網(wǎng)絡(luò)中的關(guān)鍵頂點或網(wǎng)絡(luò)拓?fù)鋱D中的重要站點等。

現(xiàn)有偏心率求解的算法主要分為近似算法[1-5]和精確算法[6-13]。針對精確算法，文獻(xiàn)[13]提出了ECC算法，該算法在圖中設(shè)置了參考頂點池，并構(gòu)建參考頂點的全局BFS索引，計算頂點x的偏心率時，選取距離x最近的參考頂點，然后按照該參考頂點索引將所有頂點分為兩個部分，最后分別計算出x對這兩個部分的局部偏心率，局部偏心率的最大值則為x的偏心率。該算法雖然避免了使用大量的BFS遍歷來求解偏心率，但由于其索引構(gòu)建代價高和頂點計算規(guī)模大的問題，所以導(dǎo)致該算法在大圖中計算效率較低。

針對上述算法中存在的問題，本文提出一種基于子圖劃分思想的偏心率求解算法。其主要思想是：首先選定K個參考頂點，將圖劃分為以這K個點為中心、互不相交的子圖，并構(gòu)建基于參考頂點的局部BFS索引。在計算前，利用頂點合并策略對圖中的頂點進(jìn)行合并以降低計算規(guī)模，并對參考頂點索引進(jìn)一步優(yōu)化。在計算時，利用索引先得出待計算頂點對每個子圖的局部偏心率范圍，并基于索引進(jìn)行剪枝，在較小范圍內(nèi)計算偏心率。實驗表明，本文提出的算法降低了索引構(gòu)建的規(guī)模，改進(jìn)了求解偏心率的效率，比現(xiàn)有求解偏心率的算法更加高效。

1 背景知識及相關(guān)工作

1.1 問題定義

1.1.1 數(shù)據(jù)模型及基本概念

給定一個無向無權(quán)圖G=(V,E)，其中V= {v1,v2,… ,vn}是圖中的頂點的集合，e(u,v)∈E表示u、v之間存在一條邊，邊的權(quán)值默認(rèn)為 1，|V|用來表示圖中的頂點個數(shù)，|E|用來表示圖中的邊個數(shù)。如圖1所示。

圖1 無向無權(quán)圖 G = (V, E)Fig.1 undirected and unweight graph G = (V, E)

定義1最短路徑：對于圖G中的任意兩個頂點u、v（?u,v∈V），u、v間的最短路徑是從u到v的路徑中最短的一條，記做d(u,v)。

定義 2偏心率：對于圖G中任意頂點u，其偏心率值是從u出發(fā)的一條最長最短路徑的長度，記做ecc(x)，且有ecc(u) ≥d(u,v) ,?v∈V。如圖2所示，頂點上方的數(shù)字表示該頂點的偏心率值。

圖2 所有頂點的偏心率值Fig.2 Eccentricity of all vertex

定義3偏心率不等式：對圖G中任意三個頂點u、v和w，總滿足d(u,v) ≤d(v,w) +d(w,u)。對圖G中任意兩個頂點u、v，有

定義4局部偏心率：設(shè)V1為圖G的一個子頂點集，即V1∈V，對 ?x∈V,x的在V1上的局部偏心率記做pecc(x|V1) ，則有pecc(x|V1) ≤ecc(x)，另外，pecc(x|V) =ecc(x)。

推論1將圖G的頂點集V的劃分為V1,V2兩個子集，即V=V1∪V2，根據(jù)定義4，對?x∈V，有ecc(x) ≥pecc(x|V1),ecc(x) ≥pecc(x|V2)， 當(dāng)pecc(x|V1)≥pecc(x|V2)時,ecc(x) =pecc(x|V1)，否則，ecc(x) =pecc(x|V2)。

證明：因為V=V1∪V2，且ecc(x)≥d(x,v),?v∈V， 則 有pecc(x|V1) ≥d(x,v) ,?v∈V1和pecc(x|V2)≥d(x,v) ,?v∈V2， 所 以ecc(x)=max{pecc(x|V1),pecc(x|V2)}。

推論2設(shè)V1,V2為V的子集，有V=V1∪V2，對?u,v∈V，則當(dāng)pecc(u|V2) ≥pecc(v|V1) +d(u,v)時，有ecc(u) =pecc(u|V2)。

證明：根據(jù)推論1，可以得出，對?u,v∈V，有pecc(u|V1) ≤pecc(v|V1)+d(u,v)；當(dāng)pecc(u|V2)≥pecc(v|V1) +d(u,v)時，有pecc(u|V2) ≥pecc(u|V1)，根據(jù)推論2，ecc(u) =max{pecc（u|V1）,pecc(u|V2)}，則ecc(u) =pecc(u|V2)。

如果給定的圖G存在孤立頂點，即存在孤立頂點u，使得u與其他任意頂點間，導(dǎo)致所有頂點的偏心率變成+∞，所以本文使用數(shù)據(jù)集均為為連通圖或圖的最大連通分量。

1.1.2 PLL算法

1.2 相關(guān)工作

現(xiàn)有偏心率求解的算法可以追溯到2011年，F(xiàn)rank W. Takes等人[7]根據(jù)三角不等式推導(dǎo)，首次提出了偏心率不等式，為之后研究偏心率求解的問題提供了思路。

K. Henderson提出了 OPEX算法[8]。該算法提前設(shè)立一個閾值 t，根據(jù)頂點的排序結(jié)果進(jìn)行BFS遍歷，并使用遍歷結(jié)果收斂其他頂點的偏心率范圍。當(dāng)所有頂點偏心率范圍的差值小于等于2t時結(jié)束，當(dāng)t=0時，該算法的結(jié)果為精確值。Frank W. Takes等人[10]基于之前提出的偏心率范圍，提出了偏心率求解算法，該算法反復(fù)選取最大上限和最小下限的頂點進(jìn)行BFS遍歷，根據(jù)遍歷的結(jié)果收斂其他頂點的偏心率范圍。以上兩個算法由于大量使用BFS遍歷，導(dǎo)致計算效率低下，不適用于較大規(guī)模的圖。

針對上述問題，Wentao Li等人[13]提出了ECC算法，其基本思想是，首先構(gòu)建圖的PLL查詢索引，避免大量使用BFS遍歷。其次從圖中選擇前K個最大度的頂點作為參考頂點，同時構(gòu)建參考頂點的全局BFS索引，如圖3所示。接著在計算時選擇距離待計算頂點最近的參考頂點，并將對應(yīng)的索引劃分為前后兩個部分W1、W2，分別得出待計算頂點對于這兩個部分的局部偏心率作為全局偏心率范圍。最后，沿著索引逐漸向前擴(kuò)展W2，使得u的全局偏心率下限向上收斂；縮小W1，使得u的全局偏心率上限向下收斂，當(dāng)偏心率上下限相等時可得出頂點u的偏心率值。ECC算法存在以下兩點問題：1）參考頂點索引構(gòu)建代價高；2）索引過長，計算時的索引平均查找代價較高，即改變W1、W2的次數(shù)較多，導(dǎo)致偏心率計算的效率較低。

圖3 參考頂點6和15的全局BFS索引Fig.3 The whole index of reference node 6 and 15

2 偏心率求解算法ECC-DIS

2.1 子圖劃分策略

針對現(xiàn)有算法參考頂點索引構(gòu)建代價高，索引過長的問題，提出了子圖劃分的策略及相應(yīng)算法SGR（Subgraph Refpool）。其主要思想是，首先選定K個頂點作為參考頂點，其次圍繞這K個頂點向外擴(kuò)展，將整個圖G劃分為互不相交的K個子圖，最后每個子圖構(gòu)建基于參考頂點的局部BFS索引，相當(dāng)于每個頂點只參與一次索引構(gòu)建，索引規(guī)模是ECC算法的1/K。相應(yīng)的算法如下：

算法1：SGR(G,K)

輸入：G=(V,E)，K

輸出：參考頂點的局部偏心率及其索引peccz，Lz， ?z∈refpool

初始化：W←V，Q=?，Qz=?，dis=2，/*Q和Qz的存儲結(jié)構(gòu)都是，key是頂點編號，value是最短路徑長度*/

1) forif r om 1to Kdo

2)z←W中度最大的頂點

首先，從未被劃分的頂點中選擇度最大的頂點作為參考頂點z，設(shè)z的未劃分鄰居頂點為t，將(z,0)和(t,1)加入到參考頂點索引Lz中，上述流程執(zhí)行K次，得到K個子圖(第1-9行)。接著，分別使用 BFS遍歷圍繞這 K個參考頂點向外拓展，將遍歷到的頂點劃分到各自的子圖中，并構(gòu)建相應(yīng)的索引，當(dāng)覆蓋所有頂點時，子圖劃分完成（第10-20行）。

例如，對圖1的G，假設(shè)需要選取2個參考頂點，首先選取度最大的頂點6作為參考頂點，將6的鄰居頂點劃分完成后，接著選取剩余度最大的頂點為15作為參考頂點，然后通過子圖劃分可將圖劃分為2個部分，如圖4所示，根據(jù)子圖劃分結(jié)果構(gòu)建參考頂點的局部BFS索引，如圖5所示。從劃分結(jié)果可以看到，圖G被劃分成了 2個不相交的子圖。由于每個頂點只參與了一次構(gòu)建，所以索引規(guī)模是ECC算法的1/2。

圖4 子圖劃分結(jié)果（K=2）Fig.4 The result of subgraph partitioning

圖5 參考頂點6和15的局部BFS索引Fig.5 The partial index of reference node 6 and 15

2.2 單個頂點偏心率求解算法

基于子圖劃分的思想，提出了相應(yīng)的偏心率求解算法EccComp（Eccentricity Computation）。該算法首先根據(jù)子圖劃分所構(gòu)建的索引，得出待計算頂點對于每個子圖的局部偏心率范圍。然后基于索引進(jìn)行剪枝，在較小范圍內(nèi)計算偏心率。該算法的偽代碼如下：

算法2：EccComp(G,K,PLL,Lz,x)

輸入：G=(V,E)，K，PLL，Lz，x

輸出：頂點x的偏心率ecc(x)

//Lzi= {v1,v2,… ,vT}，d(z,x)用PLL索引查詢

圖6 計算頂點12的偏心率Fig.6 Computing the eccentricity of vertex 12

圖7 參考頂點6的索引劃分Fig.7 Partitioning the index of reference node 6

2.3 基于頂點合并策略的優(yōu)化

在無向無權(quán)圖G=(V,E)中，存在一些特殊的“末端”頂點，這些頂點可以分為兩類，第一類是在初始圖中度為1的頂點（比如圖4中的頂點1），第二類頂點是在合并圖中所有度為1的頂點后，度數(shù)變?yōu)?的頂點（比如圖4中的頂點8），這里的“合并”并不是將圖中的頂點刪除，而是暫時忽略合并的頂點和該頂點相連的邊，接受合并的頂點稱為根頂點，如圖9所示，頂點3為頂點1的根頂點。不難看出，第一類頂點到任意頂點的最短路徑必經(jīng)過其根頂點，因為它們只有一個鄰居頂點；第二類頂點則不同，它們有多個鄰居頂點，最短路徑不一定會經(jīng)過其根頂點。根據(jù)以上分析，提出了頂點合并策略及算法，在根頂點的偏心率計算完成后，可直接推理出第一類頂點的偏心率，比較根頂點的偏心率和合并頂點深度的關(guān)系能判斷第二類頂點的偏心率是否與根頂點相關(guān)。該策略減少了偏心率計算的頂點規(guī)模，改進(jìn)了偏心率計算的效率。相應(yīng)算法如下：

算法3：NodeMerge(G,di)

輸入：G=(V,E),di∈(1,n),

輸出：合并頂點表NodeM[v]，合并頂點深度Deep[v] ,?v∈V

1)Q← ?,W←V

首先，根據(jù)給定的初始圖G=(V,E)，從所有頂點中查找di∈(1,n)為1的頂點（第1-4行），將它們合并到未訪問的鄰居頂點j中，可知頂點j為它們的根頂點，修改頂點j的合并頂點深度Deep[j]。接著，將dj減1，并判斷j的剩余度數(shù)是否為1，若為1，說明j也屬于“末端”頂點，同樣，將j合并到其未訪問的鄰居頂點中，并修改鄰居頂點的合并頂點深度。最后，反復(fù)執(zhí)行上述合并流程，直到圖中不存在度為1的頂點為止，W是非合并頂點集，表示只需要計算在W中的頂點偏心率（第5-17行）。

例如，對圖1中的G=(V,E)進(jìn)行頂點合并。首先，合并圖中度為1的頂點，如圖8所示。其次，根據(jù)合并的結(jié)果，繼續(xù)合并新產(chǎn)生的“末端”頂點。最后，反復(fù)合并新的度為1的頂點，當(dāng)圖中不存在該類頂點時，合并流程停止，合并結(jié)果如圖9所示，頂點后面括號中代表合并的頂點，合并后偏心率計算的頂點規(guī)模由19個變?yōu)?個。

圖8 合并度為1的頂點Fig.8 Merging the vertex of degree is 1

圖9 合并結(jié)果Fig.9 The result of merge

2.4 偏心率計算方法

結(jié)合上述三個算法，設(shè)計出求解所有頂點偏心率的完整算法ECC-DIS（Eccentricity Distribution）。具體思想是，首先使用頂點合并策略，降低偏心率計算的頂點規(guī)模。其次劃分出以K個參考頂點為中心、互不相交的子圖，并對每個子圖構(gòu)建基于中心頂點的索引。在計算時利用索引先得出待計算頂點x對于每個子圖的局部偏心率范圍，最后基于索引進(jìn)行剪枝，在較小范圍內(nèi)計算偏心率。ECC-DIS算法的執(zhí)行流程如下：

算法4 ECC-DIS(G,K)輸入：G=(V,E),K

輸出：ecc(v),?v∈V

初始化：Q=?

首先，構(gòu)建G=(V,E)的PLL查詢索引，使用NodeMerge算法合并圖中的“末端”頂點，通過SGR算法劃分子圖以及構(gòu)建參考頂點索引（第1-3行）。其次，計算非合并頂點集W中頂點w的偏心率值，如果頂點w的合并頂點表NodeM[w]不為空，表示w是根頂點，則需要判斷ecc(w)是否等于w的合并頂點深度Deep[w]，若不相等，表示NodeM[w]中被合并頂點x的偏心率ecc(x)=ecc(w)+ 1 ，并且根據(jù)ecc(x)可以繼續(xù)得出NodeM[x]中被合并頂點的偏心率值（第5-15行）；若相等，表示距w最遠(yuǎn)的頂點可能會在以w為根頂點的路徑內(nèi)，即無法判斷出該路徑內(nèi)的頂點偏心率是否與ecc(w)相關(guān)，此時將NodeM[w]中的所有頂點重新加入到非合并頂點集W中，表示它們的偏心率需要計算（第16-18行），最后，繼續(xù)計算W中的頂點偏心率，直到W為空集（第4行），返回所有頂點v的偏心率ecc(v)（第19行）。

3 實驗分析

3.1 實驗環(huán)境

本次實驗所采用硬件平臺是Intel(R) Xeon(R)Silver 4208 CPU @ 2.10GHz，gcc版本為 4.8.5，操作系統(tǒng)版本為Red Hat 4.8.5-39。用于實驗比對的算法有（1）現(xiàn)有偏心率求解方法ECC；（2）本文提出的算法ECC-DIS算法。以上實驗算法均采用C++語言實現(xiàn)。

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

本次實驗使用了11個真實數(shù)據(jù)集，Gowalla、Email-EuAll、Dblp、Web-Google、Youtube、WikiTalk-temporal、Skitter、Wikitopcat和 WikiTalk來源于斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集[15]；05citeseerx描述的是蛋白質(zhì)交互網(wǎng)絡(luò)；Dbpedia數(shù)據(jù)集描述的是知識圖譜。表1列出了這些數(shù)據(jù)集的基本信息，所有圖都被轉(zhuǎn)化成了無向無權(quán)圖，其中，|V|和|E|分別是數(shù)據(jù)集的頂點個數(shù)和邊個數(shù)，Merged Node為頂點合并的個數(shù)。從表中可以看到，大部分?jǐn)?shù)據(jù)集的頂點合并個數(shù)在3%-40%之間。

表1 數(shù)據(jù)集統(tǒng)計信息Tab.1 Statistics for the dataset

3.3 性能分析與比較

3.3.1 偏心率計算的總時間對比

表2中展示了ECC算法和ECC-DIS算法在偏心率計算時的時間比較，其中ECC算法分為三個部分Refpool、EccOneNode和Total；ECC-DIS分為 SGR和 EccComp，分別是參考頂點構(gòu)建方法、偏心率求解方法和兩者的總時間，所有時間均用秒(s)表示，具體實驗結(jié)果分析如下所示。

表2 偏心率計算的時間比較/sTab.2 Time comparison of eccentricity computation

在構(gòu)建參考頂點索引的時間上，SGR算法比已有的Refpool算法快了3倍到13倍左右。在偏心率求解的時間上，除了在 Gowalla數(shù)據(jù)集上EccComp算法和EccOneNode算法的時間相近；在其他數(shù)據(jù)集上，EccComp算法比 EccOneNode算法快了1.2倍到3.6倍左右，這是因為切換子圖的開銷比較大，所以計算偏心率的時間并沒有優(yōu)化太多。在算法的總時間上，ECC-DIS算法比ECC算法快1.2倍到6.4倍左右。

3.3.2 參考頂點索引規(guī)模及構(gòu)建時間對比

表3展示了Refpool算法和SGR算法的參考頂點平均索引規(guī)模和索引構(gòu)建時間。其中，取K=16，參考頂點平均索引規(guī)模表示K個參考頂點索引內(nèi)元素的平均個數(shù)，索引構(gòu)建時間的單位是秒(s)。

表3 不同數(shù)據(jù)集上的索引規(guī)模及構(gòu)建時間Tab.3 Index size and build time on different data sets

由實驗結(jié)果可知，在 K=16的情況下，SGR算法比 Refpool算法的索引規(guī)模小了 16倍到 17倍左右，在索引構(gòu)建時間上，算法加速倍數(shù)在 4倍到15倍之間，因為SGR算法不僅需要對頂點進(jìn)行K次排序來選出K個參考頂點，還需要根據(jù)子圖劃分構(gòu)建索引，導(dǎo)致加速倍數(shù)總低于索引優(yōu)化倍數(shù)。

3.3.3 參考頂點索引平均查找長度對比

圖10展示了ECC算法和ECC-DIS算法在計算偏心率時參考頂點索引的平均查找長度，其中ECC算法中的K=16，ECC-DIS算法中的K=32，圖的橫坐標(biāo)是不同數(shù)據(jù)集，縱坐標(biāo)是計算偏心率時每個頂點的索引平均查找長度。

圖10 不同數(shù)據(jù)集上索引平均查找長度/個Fig.10 The average search length of index in different dataset

由實驗結(jié)果可知，在05citeseerx和Wikitopcat數(shù)據(jù)集上，ECC-DIS算法與ECC算法的索引平均查找長度相近，在其他數(shù)據(jù)集上，ECC-DIS算法的索引平均查找長度普遍要比 ECC算法的平均查找長度少，優(yōu)化倍數(shù)在1.2倍到4倍之間。

4 結(jié)論

本文針對現(xiàn)有偏心率求解算法中存在的索引構(gòu)建代價高、計算效率低的問題，提出了基于子圖劃分的偏心率求解方法ECC-DIS，降低了參考頂點的索引的規(guī)模和構(gòu)建時間，通過對頂點進(jìn)行合并，提高了偏心率的計算效率。實驗結(jié)果表明，ECC-DIS算法中的索引規(guī)模是現(xiàn)有算法的 1/K，在偏心率計算的總時間方面，ECC-DIS算法比現(xiàn)有算法快了1.4倍到6倍左右。