溫菊屏，林冬梅

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

0 引 言

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

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

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

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

1 最短路徑算法距離的計(jì)算

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

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

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

2.1 算法思想

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

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

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

2.2 參考點(diǎn)的選擇

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

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

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

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

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

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

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

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

4.2 實(shí)驗(yàn)步驟

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

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

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

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

4.3 測試時(shí)間

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

4.4 距離相對(duì)誤差率

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

4.5 衡量指標(biāo)

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

表1 基于參考節(jié)點(diǎn)嵌入的最短距離估算算法的運(yùn)行時(shí)間

圖1 基于參考節(jié)點(diǎn)嵌入的最短距離估算算法的運(yùn)行時(shí)間

表2 距離相對(duì)誤差率

圖2 距離相對(duì)誤差率

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

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

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

4.6 聚類效果

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

5 結(jié)束語

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

［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é)報(bào)，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.