參考節(jié)點嵌入最短距離估算在圖聚類中的應(yīng)用

溫菊屏，林冬梅

（1.佛山科學(xué)技術(shù)學(xué)院 電子與信息工程學(xué)院，廣東 佛山528000；2.佛山科學(xué)技術(shù)學(xué)院 信息與教育技術(shù)中心，廣東 佛山528000）

0 引 言

圖聚類算法是一種分析社會關(guān)系網(wǎng)絡(luò)的有效算法，它可以發(fā)掘社會關(guān)系網(wǎng)絡(luò)中的子團體，對社會關(guān)系網(wǎng)絡(luò)的分析有重大意義，包括提高互聯(lián)網(wǎng)信息服務(wù)，發(fā)掘網(wǎng)絡(luò)輿論導(dǎo)向等作用。圖聚類有很多不同的方式，比較具代表性的有：Markov聚類［1］、譜聚類、基于密度的聚類［2］和基于劃分的聚類［3］等。

本文主要研究基于劃分的聚類算法，此算法使用距離來衡量點與點之間的相異度。由于社會關(guān)系網(wǎng)絡(luò)圖中的節(jié)點沒有坐標值，所以只能采用具有坐標值無關(guān)特性的距離算法進行聚類，比如最短路徑算法和隨機漫步算法［4］等。其中，最短路徑算法問題是圖論研究中的一個經(jīng)典算法問題，是本文研究的主要內(nèi)容。

最短路徑算法旨在尋找圖（由結(jié)點和路徑組成）中兩結(jié)點之間的最短路徑。其中，Dijkstra算法以及A＊［5］搜索都是很有代表性的最短路徑算法，由于要遍歷計算的節(jié)點很多，所以效率低。最短路徑算法在交通網(wǎng)絡(luò)中應(yīng)用很廣泛，比如google map、GPS，用戶給定兩個地點a、b，要求計算出這兩點之間的最短路徑，由于是在線查詢，沒有預(yù)存儲階段，所以在線查詢時間很長。為了快速響應(yīng)用戶的請求，需要有更為高效的算法計算兩點之間的距離。

文獻 ［6］中提到了參考節(jié)點嵌入算法思想，該算法是從所有點中選擇比較少量的參考點，預(yù)先將參考點與其他點之間的距離計算存儲下來，在需要計算兩點距離時，通過預(yù)先存儲的距離，計算出兩點之間近似估算距離。本文對最短路徑算法做了改進，引入基于參考節(jié)點嵌入的最短距離估算方法來近似獲得兩點之間的距離。從理論和實驗來比較兩種距離算法時間復(fù)雜度的大小，并且用估算的近似距離和真實距離相比，計算距離相對誤差率，實驗證明利用改進后的距離算法計算的近似距離，相對于真實距離誤差很小，但極大縮短了計算時間。

1 最短路徑算法距離的計算

文中最短路徑算法采用最有代表性的Dijkstra算法，它用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。

Dijkstra算法的缺點是時間復(fù)雜度大，分析如下：假設(shè)一個連通的大圖一共有n個頂點，一共有m條邊，則針對最短路徑算法而言，一個點到所有n個點的時間復(fù)雜度為O（n＊logn＋m），則n個點到所有n個點的時間復(fù)雜度為O（n＊n＊logn＋n＊m）。最壞情況下 m＝O（n2），因此時間復(fù)雜度的最壞情況為O（n3）。

2 基于參考節(jié)點嵌入的最短距離估算

2.1 算法思想

一個圖通常表示為G＝（V，E，w）。其中V是頂點的集合，E是邊的集合，w：E→R是一個邊權(quán)重函數(shù)，把一條邊映射成一個實數(shù)域上的權(quán)重。如果一個圖是無權(quán)圖，那么每條邊的權(quán)就是1。

（1）從V中選擇d個參考點：v1、v2、……vd，計算這d個參考點到V中每個點之間的最短路徑距離，將其預(yù)先存儲下來。

（2）求任意兩點之間的最短路徑距離，假設(shè)第一個點為s，第二個點為t，dist（s，t）表示s到t的最短路徑距離，dist（s，t）的計算方法如下：由于參考點vi和s、t構(gòu)成一個三角形，根據(jù)三角形兩邊之和大于第三邊的原理，dist（s，t）＜dist（s，vi）＋dist（vi，t）（i＝1、2、3……d），則可以取 min（dist（s，vi）＋dist（vi，t））作為最接近s、t兩者之間的真實最短路徑的距離，其中dist（s，vi）、dist（vi，t）通過查詢預(yù)先存儲的距離獲得。

2.2 參考點的選擇

從V中選擇d個參考點，其中選擇的方法有很多種，比如隨機選擇法、基于度的大小選擇法。本文考慮到社會關(guān)系網(wǎng)絡(luò)中，由于比較重要的人聯(lián)系人多，故選擇他們作為參考點比隨機選擇更為合理，則算法中根據(jù)每個節(jié)點的度大小進行降序排列，選擇度數(shù)最大的前d個節(jié)點作為參考節(jié)點。

2.3 時間復(fù)雜度分析

基于參考節(jié)點嵌入的最短距離估算，距離矩陣的計算分兩個部分進行：第一個部分是計算度數(shù)最大的d個點到其他所有點的距離，其時間復(fù)雜度為O（d＊n＊logn＋d＊m）；第二個部分是通過d個參考點來計算剩下n－d個點的近似距離，對于兩個點之間距離dist（s，t）的計算，需要查2d個距離，時間復(fù)雜度為O（d），由于圖是無向圖，那么剩下n－d個點，以每個點為起點，計算它與所有其它點之間距離的時間復(fù)雜度為O（（n－d）＊（n－d）＊d），故兩個部分時間相加，則時間復(fù)雜度為：O（d＊n＊logn＋d＊m＋（n－d）＊（n－d）＊d），由于d＜＜n，則時間復(fù)雜度最大值為n2。由此可見，相對于最短路徑距離算法時間復(fù)雜度而言，時間復(fù)雜度大大降低。

3 最短距離估算在圖聚類中的應(yīng)用

由于基于劃分的聚類算法具有簡單、快速并有效處理大規(guī)模數(shù)據(jù)等諸多優(yōu)點，它已經(jīng)成為經(jīng)典并應(yīng)用最廣泛的聚類方式之一，主要包括k－means算法和k－medoids算法，本文采用的是k－medoids的聚類算法。

基于劃分的聚類算法是使用距離來衡量點與點之間的相異度。由于社會關(guān)系網(wǎng)絡(luò)圖中點沒有坐標值，所以選擇與坐標值無關(guān)的最短路徑距離作為點與點之間相異度的衡量是行之有效的方法，但是，計算所有點對之間的最短路徑算法，例如Dijkstra和Floyd－Warshall算法具有時間復(fù)雜度大的缺點，因此需要找一種復(fù)雜度低的算法來計算所有點對之間的最短距離，在保證精確度的同時，降低時間復(fù)雜度。

參考節(jié)點嵌入（reference node embedding）算法思想被廣泛應(yīng)用在各種網(wǎng)絡(luò)數(shù)據(jù)上，包括社會關(guān)系網(wǎng)絡(luò)［6－9］，公路網(wǎng)絡(luò)［10］，因特網(wǎng)等等，用于快速的估算兩點之間的最短距離，例如在公路網(wǎng)絡(luò)中查詢兩個地點之間的最短路徑［10］，或者在因特網(wǎng)中查詢最近的服務(wù)器以減少客戶端的訪問延遲。另外對于參考節(jié)點嵌入算法思想，在計算機理論研究領(lǐng)域也有一些研究成果［11－12］，著重于給出這種估算最短距離的一個誤差上界和復(fù)雜度的分析［13－15］。參考節(jié)點嵌入的核心思想就是選擇一些參考節(jié)點，用預(yù)先計算出參考節(jié)點到所有點的最短距離作為一種索引，利用這些預(yù)先算好的距離和三角不等式關(guān)系，快速處理用戶的在線查詢。本文的貢獻在于，在圖聚類的問題中，引入最短路徑作為一種有效的距離衡量，并且采用了參考節(jié)點嵌入的思想來快速計算所有點對之間的最短路徑，在保證精度的同時，降低時間復(fù)雜度，提高運行效率。

4 實 驗

4.1 實驗數(shù)據(jù)

實驗數(shù)據(jù)來源于一個真實的圖——DBLP數(shù)據(jù)集（http：//www.informatik.uni－trier.de/～ley/db/）。在實驗中選用來自數(shù)據(jù)庫、數(shù)據(jù)挖掘、信息檢索和人工智能這4個研究領(lǐng)域的參考文獻數(shù)據(jù)，從中挑選出這4個領(lǐng)域內(nèi)最高產(chǎn)的前1000名作者，構(gòu)建他們的合著者關(guān)系大圖。在該圖中，每一個節(jié)點表示一個作者，每一條邊表示兩個作者之間的合著關(guān)系。在選擇的1000個點中，有68個是相對孤立的點，對于不連通的點，得到的最短路徑是無窮大，為了保證做最短路徑的查詢都得到有意義的解，選擇其中一個最大的連通子圖，該子圖包含932個節(jié)點。

4.2 實驗步驟

（1）使用Dijkstra算法和基于參考節(jié)點嵌入的最短距離估算算法，分別計算出精確距離矩陣和近似距離矩陣，同時測試計算距離矩陣所需的時間，比較這兩種算法運行時間的長短。

（2）根據(jù)精確距離矩陣和近似距離矩陣計算距離相對誤差率。

（3）在使用k－medoids算法時，分別使用精確距離矩陣和近似距離矩陣進行聚類，根據(jù)衡量指標density數(shù)值大小，來判斷兩種距離算法是否達到相同的分類效果。

（4）在使用k－medoids算法時，采用基于參考節(jié)點嵌入的最短距離估算算法，將最大的連通子圖分成若干類，根據(jù)程序運行得到的每個子類里作者名單，判斷實驗分類與實際情況是否吻合，驗證是否達到良好的分類效果。

4.3 測試時間

為了驗證兩種算法運行時間的長短，對程序采集數(shù)據(jù)，Dijkstra算法所需要的時間為16.022s?；趨⒖脊?jié)點嵌入的最短距離估算算法所需要的時間，隨著參考節(jié)點數(shù)目d值的增加，程序運行的時間也隨之增加，具體數(shù)據(jù)值和變化趨勢如表1和圖1所示。

4.4 距離相對誤差率

由于基于參考節(jié)點嵌入的最短距離估算算法，是基于有限個參考點得到的近似距離，與Dijkstra算法得到的精確距離有一定的偏差，其中誤差隨著d值的增大逐漸降低，直到誤差率為0，當d＝400時，距離相對誤差率降到0.004433，誤差率極小，具體數(shù)據(jù)值和變化趨勢如表2和圖2所示。

4.5 衡量指標

為了在節(jié)省運行時間的情況下，達到與Dijkstra算法同樣的分類效果，d的取值不能太小，也不能太大，d值太小則誤差率太大，d值太大則運行時間增加，通過試驗得到當d＝400時，采用基于參考節(jié)點嵌入的最短距離估算算法的運行時間大約是Dijkstra算法時間的一半，分類效果相當。為了表現(xiàn)分類效果，在這里將給出一個衡量指標density。假設(shè)圖為無向圖，首先統(tǒng)計整個大圖，在沒有分割之前，一共有n條邊，接著分別計算k類中每類包含的點之間的邊數(shù)，假設(shè)分別為n1、n2、……nk，最后計算density＝（n1＋n2＋……＋nk）/n。最理想的狀態(tài)是：在切分大圖時，都是在沒有邊的地方切割，則density的結(jié)果為1。density的值越大說明分割的方法越好。將算法用程序?qū)崿F(xiàn)之后，運行程序采集數(shù)據(jù)：在每一個k值的情況下，都要進行10次分類（為了保證可比性，兩個算法用到的隨機聚類中心點采用相同的點），取10次分類比率的平均值作為當前k值下的最終比率denstiy，根據(jù)兩個算法density值的大小，可以比較出分類效果的好壞。假設(shè)density1是使用Dijkstra算法得到的比率，density2是基于參考節(jié)點嵌入的最短距離估算算法得到的比率。實驗數(shù)據(jù)證明，當d＝400時，density2和density1大致相同，說明取得了相同的分類效果。density1、density2兩者數(shù)據(jù)如表3所示，變化趨勢如圖3所示。

表1 基于參考節(jié)點嵌入的最短距離估算算法的運行時間

圖1 基于參考節(jié)點嵌入的最短距離估算算法的運行時間

表2 距離相對誤差率

圖2 距離相對誤差率

表3 兩種距離算法density數(shù)值

圖3 兩種距離算法density數(shù)值

從表3和圖3我們可以看出：①對于兩種距離算法來說，k值增大，density值下降，這個趨勢都是相同的，因為分的類越多，類與類之間的邊就越多，而類內(nèi)部的邊就少，所以density下降；②使用Dijkstra算法與基于參考節(jié)點嵌入的最短距離估算算法，獲得的density大致相同，達到同樣的分類效果。

4.6 聚類效果

為了驗證基于參考節(jié)點嵌入的最短距離估算圖聚類算法的有效性，在使用k－medoids算法時，采用d＝400時對應(yīng)的近似距離矩陣進行聚類，將最大的連通子圖數(shù)據(jù)分成7小類，實驗結(jié)果表明每類數(shù)據(jù)均為相同領(lǐng)域合著關(guān)系比較緊密的作者列表，實驗分類情況和實際情況吻合，分類效果理想。在這7小類中，選擇其中具有代表性的4類，其中每類只列舉出比較多產(chǎn)的前20位作者姓名，如圖4和圖5所示。

5 結(jié)束語

針對社會關(guān)系網(wǎng)絡(luò)圖中點沒有坐標值的問題，本文提出選用與坐標值無關(guān)特性的最短路徑距離作為點與點之間相異度的衡量是一種行之有效的方法。同時，為了克服最短路徑算法時間復(fù)雜度大的缺點，對最短路徑算法進行改進，引入基于參考節(jié)點嵌入的最短距離估算思想。實驗證明，基于參考節(jié)點嵌入的最短距離估算算法在取得較好的聚類效果的同時，大大降低了運行時間，提高了效率。

［1］Venu Satuluri，Srinivasan Parthasarathy.Scalable graph clustering using stochastic flows：Applications to community discovery ［C］.Paris，F(xiàn)rance：Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2009：737－746.

［2］XU Xiaowei，Nurcan Yuruk，F(xiàn)ENG Zhidan，et al.SCAN：A structural clustering algorithm for networks ［C］.San Jose，CA，USA：Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2007：824－833.

［3］ZHANG Jiangpei，YANG Yue，YANG Jing，et al.Algorithm for initialization of K－Means clustering center based on optimized－division ［J］.Journal of System Simulation，2009，21（9）：2586－2590（in Chinese）.［張健沛，楊悅，楊靜，等.基于最優(yōu)劃分的K－Means初始聚類中心選擇算法 ［J］.系統(tǒng)仿真學(xué)報，2009，21（9）：2586－2590.］

［4］Graph clustering based on structural/attribute similarities ［C］.Lyon，F(xiàn)rance：Proceedings of the VLDB Endowment，2009：718－729.

［5］Goldberg A V，Harrelson C.Computing the shortest path：A＊search meets graphs theory ［C］.Vancouver，Canada：Proceedings of the Sixteenth Annual ACM－SIAM Symposium on Discrete Algorithms，2005：156－165.

［6］Potamias M，Bonchi F，Castillo C，et al.Fast shortest path distance estimation in large networks ［C］.Hong Kong：Proceed－ings of the 18th ACM Conference on Information and Knowledge Management，2009：867－876.

［7］Gubichev A，Bedathur S，Seufert S，et al.Fast and accurate estimation of shortest paths in large graphs ［C］.Toronto，Canada：Proceedings of the 19th ACM International Conference on Information and Knowledge Management，2010：499－508.

［8］Sarma A D，Gollapudi S，Najork M，et al.A sketch－based distance oracle for web－scale graphs ［C］.New York，NY，USA：Proceedings of the Third ACM International Conference on Web Search and Data Mining，2010：401－410.

［9］Rattigan M J，Maier M，Jensen D.Using structure indices for efficient approximation of network properties ［C］.Philadelphia，PA，USA：Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2006：357－366.

［10］Kriegel H P，Kr？oger P，Renz M，et al.Hierarchical graph embedding for efficient query processing in very large traffic networks ［C］.Hong Kong：Proceedings of the 20th International Conference on Scientific and Statistical Database Management，2008：150－167.

［11］Kleinberg J，Slivkins A，Wexler T.Triangulation and embedding using small sets of beacons ［C］.Rome，ITALY：Proceedings 45th Annual IEEE Symposium on Foundations of Computer Science，2004：444－453.

［12］Thorup M，Zwick U.Approximate distance oracles ［J］.Journal of the ACM，2005，52（1）：1－24.

［13］HU H，LEE D L，LEE V S.Distance indexing on road networks ［C］.Seoul，Korea：Proceedings of the 32nd International Conference on Very Large Data Bases，2006：894－905.

［14］Samet H，Sankaranarayanan J，Alborzi H.Scalable network distance browsing in spatial databasdes ［C］.Vancouver，Canada：Proceedings of the 2008ACM SIGMOD International Conference on Management of Data，2008：43－54.

［15］ WEI F.TEDI：Efficient shortest path query answering on graphs ［C］.Indianapolis，IN，USA：Proceedings of the International Conference on Management of Data，2010：99－110.