參考節點嵌入最短距離估算在圖聚類中的應用

溫菊屏，林冬梅

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

0 引 言

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

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

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

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

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

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

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

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

2.1 算法思想

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

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

（2）求任意兩點之間的最短路徑距離，假設第一個點為s，第二個點為t，dist（s，t）表示s到t的最短路徑距離，dist（s，t）的計算方法如下：由于參考點vi和s、t構成一個三角形，根據三角形兩邊之和大于第三邊的原理，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）通過查詢預先存儲的距離獲得。

2.2 參考點的選擇

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

2.3 時間復雜度分析

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

3 最短距離估算在圖聚類中的應用

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

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

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

4 實 驗

4.1 實驗數據

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

4.2 實驗步驟

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

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

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

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

4.3 測試時間

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

4.4 距離相對誤差率

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

4.5 衡量指標

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

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

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

表2 距離相對誤差率

圖2 距離相對誤差率

表3 兩種距離算法density數值

圖3 兩種距離算法density數值

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

4.6 聚類效果

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

5 結束語

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

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

［2］XU Xiaowei，Nurcan Yuruk，FENG 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）.［張健沛，楊悅，楊靜，等.基于最優劃分的K－Means初始聚類中心選擇算法 ［J］.系統仿真學報，2009，21（9）：2586－2590.］

［4］Graph clustering based on structural/attribute similarities ［C］.Lyon，France：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.