一種高效的頂點(diǎn)偏心率計(jì)算方法

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

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

0 引言

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

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

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

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

1.1 問(wèn)題定義

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

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

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

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

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

圖2 所有頂點(diǎn)的偏心率值Fig.2 Eccentricity of all vertex

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

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

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

證明：因?yàn)閂=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，對(duì)?u,v∈V，則當(dāng)pecc(u|V2) ≥pecc(v|V1) +d(u,v)時(shí)，有ecc(u) =pecc(u|V2)。

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

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

1.1.2 PLL算法

1.2 相關(guān)工作

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

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

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

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

2 偏心率求解算法ECC-DIS

2.1 子圖劃分策略

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

算法1：SGR(G,K)

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

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

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

1) forif r om 1to Kdo

2)z←W中度最大的頂點(diǎn)

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

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

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

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

2.2 單個(gè)頂點(diǎn)偏心率求解算法

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

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

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

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

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

圖6 計(jì)算頂點(diǎn)12的偏心率Fig.6 Computing the eccentricity of vertex 12

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

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

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

算法3：NodeMerge(G,di)

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

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

1)Q← ?,W←V

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

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

圖8 合并度為1的頂點(diǎn)Fig.8 Merging the vertex of degree is 1

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

2.4 偏心率計(jì)算方法

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

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

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

初始化：Q=?

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

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

3.3 性能分析與比較

3.3.1 偏心率計(jì)算的總時(shí)間對(duì)比

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

表2 偏心率計(jì)算的時(shí)間比較/sTab.2 Time comparison of eccentricity computation

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

3.3.2 參考頂點(diǎn)索引規(guī)模及構(gòu)建時(shí)間對(duì)比

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

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

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

3.3.3 參考頂點(diǎn)索引平均查找長(zhǎng)度對(duì)比

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

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

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

4 結(jié)論

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