基于最短路徑的加權屬性圖聚類算法研究

張素智 張 琳 曲旭凱

(鄭州輕工業(yè)學院計算機與通信工程學院 河南 鄭州 450002)

?

基于最短路徑的加權屬性圖聚類算法研究

張素智 張 琳 曲旭凱

(鄭州輕工業(yè)學院計算機與通信工程學院 河南 鄭州 450002)

圖在計算機領域是一種重要的數(shù)據(jù)結構，可以用來描述事物之間的復雜關系。圖的節(jié)點和邊具備一個或者多個不同的屬性。如何結合屬性對圖進行聚類是目前所面臨的一個新的挑戰(zhàn)。目前的屬性圖聚類算法，多存在聚類效果差，消耗資源多，效率低等缺點。針對以上問題，提出一種基于最短距離的加權屬性圖聚類算法WASP(weighted attribute graph clustering algorithm based on shortest path)，建立加權屬性無向圖模型，在此模型上基于最短路徑算法度量節(jié)點間的關聯(lián)度，以此為原則選取新的聚類中心對圖進行聚類。實驗表明，新的聚類算法具有更高效的聚類效果。

圖 加權屬性圖 最短路徑 聚類

0 引 言

近年來，圖結構被廣泛應用于多個領域來描述數(shù)據(jù)之間的復雜結構。針對海量圖數(shù)據(jù)的分析和挖掘越來越重要。作為圖數(shù)據(jù)挖掘算法的一種，圖聚類算法引起了眾多關注[1，2]。圖聚類，簡單描述就是根據(jù)圖結構上節(jié)點和邊的某種相似性，將圖上的節(jié)點和邊劃分為不同的組。屬性圖聚類是圖聚類中的一種特殊情況，即在用節(jié)點和邊表示實體和實體關系的同時，還需要考慮到節(jié)點和邊的屬性。在屬性圖聚類時，同時考慮節(jié)點間結構和屬性的相似性，則能夠得到更加準確的聚類效果。如何更好地同時結合結構和屬性進行聚類是目前圖聚類研究的熱點和難點。

針對屬性圖聚類問題，現(xiàn)階段也有許多研究成果：Tian等人[3]根據(jù)聚類中節(jié)點和屬性相一致的原則，提出了k-SNAP算法，該算法通過用戶的下鉆和上取，將屬性一致的點聚集在一起，實現(xiàn)了多粒度的圖聚類。但是此算法僅根據(jù)節(jié)點屬性聚類，會造成聚類結構分散，聚類效果中節(jié)點數(shù)過多。針對k-SNAP算法存在的問題，Zhang等人[4]改進了該算法，對數(shù)值屬性分類，并對屬性相近對按相似度基于最大惡化程度進行劃分。Nevile 等人[5]將具有相同屬性的屬性個數(shù)定義為邊的權重值，并以此為基礎將屬性圖轉(zhuǎn)化為帶權圖進行聚類。Steinhaeuser等[6]提出了相似的算法，并將屬性擴展到具有連續(xù)值域的情況。此類算法由人工定義權重值，雖然算法效率高，但聚類效果和可拓展性差。也有一些算法通過增廣屬性圖[7，8]，采用熵的統(tǒng)一模型來衡量圖中的同質(zhì)性，實現(xiàn)屬性圖的聚類。該方法雖然將圖的結構和屬性結合起來聚類，但統(tǒng)一聚類超結點中的結點聯(lián)系并不緊密。還有一些算法把模型的思想[9，10]應用到屬性圖聚類中，將屬性圖聚類轉(zhuǎn)化為概率問題，但此類算法需要事先設定好聚類數(shù)量，才能達到較好的聚類效果。

針對以上算法的問題，本文提出了一種基于最短路徑的加權屬性圖聚類算法WASP。該算法通過建立加權屬性圖模型，對圖中邊和節(jié)點的屬性設置權值，確定節(jié)點相似度，采用最短路徑算法計算節(jié)點間的距離，確定聚類中心，并在聚類過程中自動更新權重值，以此為基礎進行聚類。最后將WASP算法應用在DBLP數(shù)據(jù)集中，通過實驗對比，該算法具有較好的聚類效果。

1 相關定義

1.1 屬性加權無向圖定義

定義1屬性加權無向圖G=(V,E,A,ω)；其中：

V表示屬性圖中節(jié)點集合：V={v1,v2,…,vn}；

E表示屬性圖中邊的集合：E={(vi,vj)|(vi,vj)∈R,1≤i,j≤n,i≠j}；

A表示圖的屬性的集合：A={a1,a2,…,am}；其中|A|=m′；

ω為邊的權重值：ω={ω1,ω2,…，ωp} ，|ω|=p′ ，ωa(ik)表示節(jié)點vi的屬性ak的權值，若任意兩節(jié)點vi、vj直接相連，則這兩點節(jié)點間的權重值為ωi,j= ωq，q∈{1,2…，p}；

1.2 節(jié)點相似度定義

在社交網(wǎng)絡中，如果用戶之間的公共朋友越多，則用戶之間的聯(lián)系越大。對于屬性圖中的節(jié)點，如果節(jié)點之間聯(lián)系的公共節(jié)點越多，則這些節(jié)點位于同一個簇的可能性越大。本文考慮將與節(jié)點直接關聯(lián)的點稱為該節(jié)點的節(jié)點朋友。

定義2屬性圖G=(V,E),v為圖中的節(jié)點。定義節(jié)點朋友集合為Κ(v)：

K(v)={u∈V|(v,u)∈E}∪{v}

(1)

若v、u之間有邊，即∈E,則將邊的相似度定義為：

(2)

2 算法描述

2.1 自動更新屬性權重值

為了得到較好的聚類效果，提出了一種自動更新屬性權重值的方法，在聚類過程中不斷更新屬性權重值，來得到較好的聚類效果。

(3)

因此更新后的權重值：

(4)

2.2 最短路徑算法

為了發(fā)現(xiàn)圖中高關聯(lián)度的邊，考慮到邊的權重和相似度，設定參數(shù)α、β，且α+β=1。任意一條邊上的關聯(lián)度為：

(5)

兩個節(jié)點間路徑越長，則關聯(lián)度越小，若要取得最大關聯(lián)度的節(jié)點，則相鄰節(jié)點直接取節(jié)點間最短距離，非相鄰節(jié)點取節(jié)點之間最短距離的和。最大關聯(lián)度的和為:

(6)

其中，Z是節(jié)點va、ub中間節(jié)點的集合。本文采用最短路徑算法中的經(jīng)典算法Dijkstra算法。

根據(jù)最短路徑的最優(yōu)子結構性質(zhì)，如果存在一條從i到j的最短路徑(vi,…,vk,vj)，vk是vj前面的一頂點，那么(vi，…，vk)也必定是從i到j的最短路徑。為了求出最短路徑，Dijkstra提出了以最短路徑長度遞增，逐次生成最短路徑的算法。例如對于源頂點v0，首先選擇其直接相鄰的頂點中長度最短的頂點vi，那么當前已知可得從v0到達vj頂點的最短距離：

(7)

根據(jù)這種思路，假設存在圖G=(V,E,ω)，源頂點為v0，U={v0},dist[i]記錄v0到vi的最短距離，path[i]記錄從v0到vi路徑上的i前面的一個頂點，則算法過程為：

1) 從{V-U}中選擇使dist[i]值最小的頂點i，將i加入到U中；

2) 更新與i直接相鄰頂點的dist值，即dist[j]=min{dist[j],dist[i]+matrix[i][j]}；

3) 直到U=V。

2.3 聚類算法描述

基于最短路徑的圖聚類算法，就是在計算最大關聯(lián)度時采用最短路徑算法，選取相應的節(jié)點并劃分到同一簇中。具體算法步驟如下：

輸入：屬性加權無向圖G=(V,E,A,ω)，初始權重值ω=1.0，聚類數(shù)量k，參數(shù)α=0.4，β=0.6；

輸出：劃分的不同的簇；

1) 計算邊的相似度Γ(v,u)；

2) 在初始聚類數(shù)量k中選擇節(jié)點作為初始聚類中心Vstart，且Vstart不能為空集。定義剩余節(jié)點Vleft=V-Vstart；

4) 在劃分好的節(jié)點中，根據(jù)更新的權重值，得到L(va,ub)，并將關聯(lián)度大且距離短的的節(jié)點劃分為一簇；

5) 若Vleft=?，則聚類結束，所有節(jié)點劃分完畢，若Vleft≠?且Vleft

WASP算法是一種基于最短路徑對圖的結構和屬性聚類的算法。在算法時間復雜度方面，第1步，計算邊的相似度，時間復雜度為Ο(n)；第2、3步，選擇聚類中心的，時間復雜度為Ο(n3)，第3-5步，計算最短路徑，劃分節(jié)點到不同的簇，時間復雜度為Ο(kn-n2)，其中k為初始聚類數(shù)量。該算法總體時間復雜度為Ο(n3)。

3 實驗與分析

3.1 實驗數(shù)據(jù)集

本次實驗采用DBLP數(shù)據(jù)集。這是一個學術合作關系的網(wǎng)絡。由德國的特里爾大學創(chuàng)建的發(fā)表在計算機期刊、雜志和會議論文的數(shù)據(jù)庫系統(tǒng)。該網(wǎng)絡包括一萬多個節(jié)點和兩萬多條無向邊。其中節(jié)點表示論文作者，邊代表作者們合作完成的論文。本次實驗選擇了該網(wǎng)絡提供的在數(shù)據(jù)挖掘、數(shù)據(jù)庫、人工智能、信息檢索等相關領域發(fā)表論文最多的5000名作者英文單位。

作者單位的中英文要完全對應，每個實詞的首字母大寫。在部門名稱和單位名稱之間、在單位名稱和城市名之間使用英文逗號隔開，城市名和郵編之間使用一個英文空格隔開，不能用逗號。

3.2 評價標準

(8)

3.3 實驗結果

實驗時設定聚類初始數(shù)量k=5,10,15,20,25,30，圖1為WASP算法與SCAN算法在DBLP數(shù)據(jù)集上的聚類密度效果。由圖1可知，在聚類數(shù)量較少時，WASP算法與SCAN算法聚類效果沒有太大差別，但當聚類數(shù)量增多時，WASP算法更具有優(yōu)勢。這是因為WASP算法不但考慮了圖的屬性和結構，還考慮到了節(jié)點間的權重值，在聚類數(shù)量增多的時候，節(jié)點間的權重值也會增大，此時WASP算法聚類效果更明顯。

圖1 聚類密度結果圖

為了更好地對比兩個算法的聚類效率，選擇對比兩算法的聚類時間。在實驗數(shù)據(jù)集上分別運行WASP算法和SCAN算法各10次，并記錄下每次運算所消耗的時間。取10次運算的平均值作為聚類時間。

由圖2可知，當聚類數(shù)目較小時，WASP算法與SCAN算法聚類時間差距不大。但當聚類數(shù)目開始增多時，SCAN算法無明顯變化，WASP算法卻出現(xiàn)變化。這是因為由于該算法在聚類迭代時，每次都要計算當前聚類中心到所有節(jié)點的最短距離。當聚類數(shù)量增多，即k的值增加時，由于算法3-5步的時間復雜度為Ο(kn-n2)，算法第3-5步所消耗的時間將會增加。因此算法總體時間將會變長，而對于SCAN算法來說，時間復雜度不會有明顯變化。在大型圖聚類算法中，WASP算法時間會長于SCAN算法，但由于k值對WASP算法時間影響較小，因此具體到實際應用中只有幾秒鐘時間，且在小型數(shù)目集中沒有明顯區(qū)別。

圖2 聚類時間圖

4 結 語

本文通過對現(xiàn)有圖聚類算法的研究，以加權屬性圖為模型，提出了基于最短路徑的加權屬性圖算法。該算法結合圖的屬性和結構進行聚類，實驗表明，該算法比一般圖聚類算法具有更好的聚類效果。但是該算法在大型圖上聚類時間略長于其他聚類算法，需要在今后的工作中進一步的改進。

[1] Majumdar D,Kanjilal A,Bhattacharya S.Separation of scattered concerns: a graph based approach for aspect mining[J].ACM SIGSOFT Software Engineering Notes,2011,36(2): 1-11.

[2] Sengupta S,Kanjilal A,Bhattacharya S.Measuring complexity of component based architecture: a graph based approach[J].ACM SIGSOFT Software Engineering Notes,2011,36(1): 1-10.

[3] Tian Y,Hankins R A,Patel J M.Efficient aggregation for graph summarization[C]//Proceedings of the 2008 ACM SIGMOD international conference on Management of data.ACM,2008: 567-580.

[4] Zhang N,Tian Y,Patel J M.Discovery-driven graph summarization[C]//Data Engineering (ICDE),2010 IEEE 26th International Conference on.IEEE,2010: 880-891.

[5] Neville J,Adler M,Jensen D.Clustering relational data using attribute and link information[C]//Proceedings of the text mining and link analysis workshop,18th international joint conference on artificial intelligence.2003: 9-15.

[6] Steinhaeuser K,Chawla N V.Community detection in a large real-world social network[M]//Social computing,behavioral modeling,and prediction.Springer US,2008: 168-175.

[7] Cheng H,Zhou Y,Yu J X.Clustering large attributed graphs: A balance between structural and attribute similarities[J].ACM Transactions on Knowledge Discovery from Data (TKDD),2011,5(2): 12.

[8] Liu Z,Yu J X,Cheng H.Approximate homogeneous graph summarization[J].Information and Media Technologies,2012,7(1): 32-43.

[9] Xu Z,Ke Y,Wang Y,et al.A model-based approach to attributed graph clustering[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.ACM,2012: 505-516.

[10] Zanghi H,Volant S,Ambroise C.Clustering based on random graph model embedding vertex features[J].Pattern Recognition Letters,2010,31(9): 830-836.

[11] Zhou Y,Cheng H,Yu J X.Clustering large attributed graphs: An efficient incremental approach[C]//Data Mining (ICDM),2010 IEEE 10th International Conference on.IEEE,2010: 689-698.

STUDY ON SHORTEST PATH-BASED CLUSTERING ALGORITHM OF WEIGHTED ATTRIBUTE GRAPH

Zhang Suzhi Zhang Lin Qu Xukai

(School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,Henan,China)

Graph is an important data structure in computer science,and can be used to describe the complex relationship between things.The nodes and edges in graph have one or more different attributes.How to cluster the graph in combination with attributes is a new challenge encountered at present.Many of current attribute graph clustering algorithms have the drawbacks of poor clustering effect,big resource consumption and low efficiency.In view of the above problems,this paper puts forward a shortest path-based weighted attribute graph clustering algorithm,and builds the weighted attribute undirected graph model.Based on the model the algorithm measures the correlation degree between the nodes based on shortest path algorithm,and takes this as the principle to select new clustering centre to cluster the graph.Experiment shows that the new clustering algorithm has more efficient clustering effect.

Graph Weighted attribute graph Shortest path Clustering

2015-06-10。國家自然科學基金青年科學基金項目(61201447)。張素智，教授，主研領域：Web數(shù)據(jù)庫，分布式計算，異構系統(tǒng)集成。張琳，碩士生。曲旭凱，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2016.11.050