一種高效的頂點偏心率計算方法

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

(東華大學 計算機科學與技術學院，上海 201620)

0 引言

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

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

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

1 背景知識及相關工作

1.1 問題定義

1.1.1 數據模型及基本概念

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

圖1 無向無權圖 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出發的一條最長最短路徑的長度，記做ecc(x)，且有ecc(u) ≥d(u,v) ,?v∈V。如圖2所示，頂點上方的數字表示該頂點的偏心率值。

圖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局部偏心率：設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，根據定義4，對?x∈V，有ecc(x) ≥pecc(x|V1),ecc(x) ≥pecc(x|V2)， 當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設V1,V2為V的子集，有V=V1∪V2，對?u,v∈V，則當pecc(u|V2) ≥pecc(v|V1) +d(u,v)時，有ecc(u) =pecc(u|V2)。

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

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

1.1.2 PLL算法

1.2 相關工作

現有偏心率求解的算法可以追溯到2011年，Frank W. Takes等人[7]根據三角不等式推導，首次提出了偏心率不等式，為之后研究偏心率求解的問題提供了思路。

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

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

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

2 偏心率求解算法ECC-DIS

2.1 子圖劃分策略

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

算法1：SGR(G,K)

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

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

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

1) forif r om 1to Kdo

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

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

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

圖4 子圖劃分結果（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 單個頂點偏心率求解算法

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

算法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 基于頂點合并策略的優化

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

算法3：NodeMerge(G,di)

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

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

1)Q← ?,W←V

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

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

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

圖9 合并結果Fig.9 The result of merge

2.4 偏心率計算方法

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

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

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

初始化：Q=?

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

3 實驗分析

3.1 實驗環境

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

3.2 數據集

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

表1 數據集統計信息Tab.1 Statistics for the dataset

3.3 性能分析與比較

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

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

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

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

3.3.2 參考頂點索引規模及構建時間對比

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

表3 不同數據集上的索引規模及構建時間Tab.3 Index size and build time on different data sets

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

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

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

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

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

4 結論

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