基于有向加權(quán)圖的相似性度量及聚簇劃分

劉合富，劉 蓉，趙 強

（1.華中師范大學(xué)a.信息化辦公室；b.物理科學(xué)與技術(shù)學(xué)院，武漢 430079；2.武漢理工大學(xué) 經(jīng)濟學(xué)院，武漢 430070）

0 引言

聚簇劃分被廣泛應(yīng)用于人與人、人與事物之間的社會關(guān)系的劃分上。研究社區(qū)的聚簇劃分對于社區(qū)拓撲結(jié)構(gòu)、變動規(guī)律、事件預(yù)測等具有重要的理論意義和現(xiàn)實價值。聚簇劃分的首要任務(wù)是社區(qū)網(wǎng)絡(luò)關(guān)系的發(fā)現(xiàn)?，F(xiàn)實社區(qū)活動通過用戶與事件的互動，往往會產(chǎn)生一些社區(qū)網(wǎng)絡(luò)關(guān)系，例如商場商品銷售、銀企信貸關(guān)系、社交網(wǎng)絡(luò)活動等，都可以通過用戶活動構(gòu)成事件之間的強弱關(guān)系[1—3]。將事件關(guān)聯(lián)點當作網(wǎng)絡(luò)空間節(jié)點，將用戶的轉(zhuǎn)移需求作為邊，將需求的有向關(guān)系作為邊的方向，將需求強弱程度看作網(wǎng)絡(luò)的邊權(quán)，于是上述活動事件節(jié)點之間能構(gòu)成一種基于有向加權(quán)網(wǎng)絡(luò)的社交關(guān)系。將加權(quán)網(wǎng)絡(luò)關(guān)系圖引入事件需求分析，既能清晰地展示事件之間是否存在關(guān)聯(lián)，又能直接明了地表示關(guān)聯(lián)程度的強弱，對個性化推薦、社群劃分、社區(qū)發(fā)現(xiàn)等應(yīng)用性研究具有重要意義[4]。許多學(xué)者進行了社區(qū)聚簇劃分和聚類分析研究，付立東等（2019）[5]將無向網(wǎng)絡(luò)圖轉(zhuǎn)換為星形鄰域網(wǎng)絡(luò)，建立相似度模型，節(jié)點相似度值以共鄰節(jié)點數(shù)占鄰居節(jié)點總數(shù)的比重來計算，用于復(fù)雜網(wǎng)絡(luò)社區(qū)劃分；邱德紅等（2012）[6]提出了一種基于邊權(quán)值和方向的有向圖相似度算法用于聚類發(fā)掘；馬鐵民等（2019）[7]提出了基于用戶相似度的Si-user Walker 算法,以無向圖節(jié)點發(fā)生事件次數(shù)和類別數(shù)為指標構(gòu)造相似度模型，用于解決網(wǎng)絡(luò)社交事件推薦問題；任淑霞等（2019）[8]采用馬爾科夫鏈多步轉(zhuǎn)移概率矩陣作為相似度矩陣，完成節(jié)點相似圖的重構(gòu)，采用譜聚類實現(xiàn)社區(qū)劃分。以上相似度計算方法雖然用在社區(qū)劃分中取得了一定成果，但仍存在一些不足：（1）網(wǎng)絡(luò)圖中節(jié)點間直連信息被忽略，僅考慮到鄰域節(jié)點連接關(guān)系；（2）圖中節(jié)點與鄰居節(jié)點在邊方向、邊權(quán)等方面的雙向連接關(guān)系未充分體現(xiàn)；（3）無法呈現(xiàn)節(jié)點間事件發(fā)生的主被動、信息傳遞的正逆向、雙向邊權(quán)的對稱強度等特征信息變化的問題。以此構(gòu)建成的網(wǎng)絡(luò)圖，其節(jié)點相似性度量不夠全面，導(dǎo)致聚簇劃分精度不夠高。

為提高有向網(wǎng)絡(luò)圖節(jié)點相似度計算的準確度，本文基于網(wǎng)絡(luò)社區(qū)用戶活動特征，充分考慮節(jié)點間連接強度、共鄰節(jié)點相似性、邊方向作用、邊權(quán)值對稱性等對相似度的影響，提出雙向度量相似度BDMS（Bi-Directional Measurement Similarity）算法。算法首先建立符合社區(qū)活動事務(wù)特征的馬爾科夫鏈矩陣；然后，構(gòu)建有向加權(quán)圖，其中節(jié)點間的相似度主要包含共鄰相似度和直連相似度兩個部分，并將影響相似度度量的節(jié)點直連強度、相鄰節(jié)點數(shù)、邊方向、邊權(quán)值等要素納入計算，形成相似度鄰接矩陣；最后，結(jié)合譜聚類無向圖切圖方式尋找矩陣的相關(guān)特征向量進行聚簇劃分。為了驗證BDMS算法的合理性和有效性，以更清晰地獲得聚類分析效果，本文基于真實的高校學(xué)生生活和學(xué)習(xí)數(shù)據(jù)對其進行驗證。

1 有向加權(quán)圖構(gòu)建

社區(qū)網(wǎng)絡(luò)空間節(jié)點的事件發(fā)生關(guān)系通常采用圖的結(jié)構(gòu)表示，圖是在分析具有連接關(guān)系的科學(xué)和工程問題時常用的一種數(shù)據(jù)結(jié)構(gòu)[9]。將空間位置或事件看作圖的節(jié)點，節(jié)點之間的關(guān)系表示成圖的邊，包含節(jié)點間動態(tài)轉(zhuǎn)移事件數(shù)量的權(quán)重、方向等相互關(guān)聯(lián)的特征信息，形成一張有向加權(quán)圖。圖中節(jié)點關(guān)系的生成，重點在于圖邊的定義、權(quán)值計算以及邊方向的確定?？紤]到事件發(fā)生過程中節(jié)點關(guān)系的復(fù)雜性，多數(shù)相似度算法采用無向加權(quán)圖來表示節(jié)點間的事件連接關(guān)系，但是無向加權(quán)圖忽略了很多節(jié)點間主被動關(guān)系、互轉(zhuǎn)強度對稱性、信息流動方向性等特征信息，難以較為全面地呈現(xiàn)節(jié)點之間相似關(guān)系的實質(zhì)。例如：將高校學(xué)生網(wǎng)上選修公選課事件視為一項社區(qū)網(wǎng)絡(luò)活動，公選課之間的選課人流量轉(zhuǎn)移關(guān)系是雙向的，隨著教學(xué)管理和培養(yǎng)計劃的變化，學(xué)校提供不同課程的優(yōu)化策略，課程之間因熱度或需求不同可能出現(xiàn)學(xué)生選課次數(shù)互轉(zhuǎn)現(xiàn)象，該現(xiàn)象若以有向加權(quán)圖表示能更清晰地勾畫出強弱不同的雙向轉(zhuǎn)移關(guān)系。因此，用有向加權(quán)圖表示節(jié)點事件所發(fā)生的關(guān)系和特征，具有更好的代表性和呈現(xiàn)性。

本文基于具有馬爾科夫特征的社區(qū)活動事件的轉(zhuǎn)移關(guān)系，采用有向加權(quán)圖的方式表示。將空間位置節(jié)點間發(fā)生的事件數(shù)量轉(zhuǎn)移看作是一個馬爾科夫過程，具有n個節(jié)點的狀態(tài)空間M={1，2，…，n}，以P來表示空間M中節(jié)點的事件狀態(tài)轉(zhuǎn)移概率矩陣，如式（1）所示。

將公式（1）抽象為一個由空間節(jié)點、有向邊及邊權(quán)組成的有向加權(quán)圖，記為:

其中，V={v1，v2，…，vn}是馬爾科夫鏈節(jié)點的集合；是代表現(xiàn)實世界中兩個實體間的轉(zhuǎn)移關(guān)系的雙向邊的集合；W={W11，W12，…，Wnn}是→中邊權(quán)的集合，當i≠j時，Wij為馬爾科夫鏈轉(zhuǎn)移概率Pij；(vi，vj)表示由節(jié)點vi指向節(jié)點vj的邊；W對應(yīng)于有向邊(vi，vj)的權(quán)Wij記為轉(zhuǎn)移概率Pij，若Wij=0，則表示節(jié)點vi到vj無連接邊。

式（2）實現(xiàn)了從馬爾科夫鏈的轉(zhuǎn)移概率矩陣向有向加權(quán)圖的轉(zhuǎn)換，具有方向性和關(guān)聯(lián)關(guān)系強度的轉(zhuǎn)移概率的值越大，表示節(jié)點間的關(guān)系越重要或聯(lián)系越頻繁[10]。式（2）中以節(jié)點間的轉(zhuǎn)移概率來表示的圖中的邊連接權(quán)重具有方向性且可能具有不對稱性，所涉及的節(jié)點關(guān)系、邊方向、邊權(quán)重等屬性具備明顯的事件變化特征。將轉(zhuǎn)移概率矩陣P轉(zhuǎn)化為有向加權(quán)圖，主要是為了滿足社區(qū)網(wǎng)絡(luò)節(jié)點在聚類分析中的聚簇劃分需要，能更好地了解社區(qū)結(jié)構(gòu)、功能以及預(yù)測節(jié)點分布的行為特征。因此，以馬爾科夫鏈形成的事件轉(zhuǎn)移過程可以抽象為一張有向加權(quán)圖。

2 有向加權(quán)圖的節(jié)點相似度

2.1 相似度算法分析

計算圖節(jié)點相似度是進行聚類分析的基礎(chǔ)，在社區(qū)劃分、協(xié)同過濾、信息檢索、人際關(guān)系網(wǎng)絡(luò)分析等領(lǐng)域有廣泛的應(yīng)用[11]。傳統(tǒng)的相似度算法采用局部網(wǎng)絡(luò)連接信息方法，通過比較鄰域節(jié)點的向量角度關(guān)系、距離大小或圖拓撲結(jié)構(gòu)特點來確定節(jié)點間的相似性，以反映兩個節(jié)點的相似程度。常見的算法有余弦相似度[12]、Jaccard 相似度[13]、SimRank 相似度[14]等。其中，余弦相似度衡量節(jié)點間的相似性是通過相鄰節(jié)點向量的夾角余弦值來確定，結(jié)果與向量的權(quán)重大小無關(guān)，僅與向量的方向相關(guān)；Jaccard相似度認為節(jié)點間的共同鄰居數(shù)越多，在與兩個節(jié)點相連的全部節(jié)點總數(shù)中占比越高，相似度就越高；SimRank 相似度認為如果有共鄰節(jié)點與兩個節(jié)點相連，共鄰節(jié)點之間相似度越高，兩個節(jié)點相似度也越高。以上算法僅考慮了共鄰節(jié)點的相關(guān)信息，但在節(jié)點間存在雙向轉(zhuǎn)移事件關(guān)系時，至少存在以下不足：（1）未考慮到共鄰節(jié)點做貢獻時具有雙向性，并且方向不同、大小不同，貢獻可能存在差異。（2）當兩個節(jié)點直接相連時，產(chǎn)生的親密性作用被忽略，假如不存在共鄰節(jié)點，則其相似度為0，與現(xiàn)實不符。（3）采用聚類分析進行聚簇劃分的準確率不高。從兩個節(jié)點之間的相似關(guān)聯(lián)程度來看，共鄰節(jié)點對節(jié)點間相似關(guān)系確實存在雙向強弱不同的影響，但是兩個節(jié)點之間的直接互動強度也在一定程度上反映了兩者的相似關(guān)聯(lián)性。因此，計算節(jié)點相似度時僅考慮共鄰節(jié)點的貢獻是不夠全面的。

2.2 有向加權(quán)圖的BDMS算法

為了更好地評價空間節(jié)點的相似性，本文采用BDMS算法來計算相似度，算法的基本流程如下：

步驟1：輸入由初始數(shù)據(jù)集形成的馬爾科夫鏈狀態(tài)轉(zhuǎn)移概率矩陣P（見式（1））。

步驟2：參照式（2），構(gòu)建有向加權(quán)圖G'=(V，→，W)。

步驟3：根據(jù)有向加權(quán)圖G'的節(jié)點間矢量信息完成節(jié)點間的相似度分解。

步驟4：根據(jù)節(jié)點邊權(quán)值、邊方向、出度和入度相似度的對稱性等信息，計算節(jié)點的相似度。

步驟5：輸出相似度鄰接矩陣。為下一步利用該矩陣進行聚類分析實現(xiàn)聚簇劃分做準備。

2.2.1 節(jié)點之間的相似度分解

馬爾科夫鏈的一個節(jié)點向其他節(jié)點轉(zhuǎn)出數(shù)量時，也可能接收其他節(jié)點轉(zhuǎn)入的數(shù)量，整個過程可以建立節(jié)點間的雙向局部連接關(guān)系，依照式（2）形成一個有向加權(quán)圖，然后通過節(jié)點間的雙向矢量關(guān)聯(lián)信息來計算相似度。如果將節(jié)點v3看作是v1、v2的共鄰節(jié)點，根據(jù)關(guān)聯(lián)矢量方向可以分解為：v3對v1和v2的轉(zhuǎn)移強度存在正反兩個方向，如圖1中（a）、（b）所示；v1和v2之間的互轉(zhuǎn)強度存在正反兩個方向，如圖1中（c）所示。

圖1 節(jié)點間關(guān)聯(lián)矢量分解示意圖

于是可以理解有向加權(quán)圖的兩個空間事件節(jié)點的相似度由以下三個部分組成：Sin——入度相似度；Sout——出度相似度；LT——兩個節(jié)點直接相連的親密度，即直連相似度。其中，入度相似度、出度相似度分別參照余弦相似度的計算方法,從單一方向上與傳統(tǒng)方法保持一致，計算公式分別如式（3）、式（4）所示。

其中，N+(i)、N-(i)、N+(j)、N-(j)分別表示節(jié)點i和j的入度和出度的鄰居節(jié)點集合，N+(i)∩N+(j)和N-(i)∩N-(j)分別表節(jié)點i和j的入度和出度的共鄰節(jié)點集合，Pki和Pkj表示共鄰節(jié)點k對節(jié)點i和j的入度轉(zhuǎn)移強度，Pik和Pjk表示節(jié)點i和j對共鄰節(jié)點k的出度轉(zhuǎn)移強度。

2.2.2 算法過程描述和實現(xiàn)

為了降低算法復(fù)雜度，在有向加權(quán)圖的相似性度量定義中，主要綜合考慮影響節(jié)點相似性的各個因素的作用。算法過程如下：定義兩個節(jié)點的相似度S(i，j)由共鄰相似度ST(i，j)和直連相似度LT(i，j)組成。其中，ST(i，j)由共鄰節(jié)點對兩個節(jié)點在雙向連接邊權(quán)值上的貢獻決定，并由入度相似度Sin(i，j)和出度相似度Sout(i，j)計算得出，算法計算時，針對不同方向，若兩個節(jié)點與共鄰節(jié)點之間有一個方向不直接相連，則該方向的相似度為0；否則，取其共鄰節(jié)點的邊權(quán)值納入計算；直連相似度LT(i，j)由兩個節(jié)點之間在雙向連接邊權(quán)值上的貢獻決定，算法計算時，若兩個節(jié)點之間有一個方向連接斷開，則兩者的直連相似度為0，否則取其雙向邊的權(quán)值納入計算。算法主要步驟如下：

步驟1：計算兩個節(jié)點的共鄰相似度ST(i，j)，如式(5)所示。

其中，Sin(i，j)、Sout(i，j)分別由式（3）、式（4）計算所得。式（5）的算法有兩個主要優(yōu)點：（1）Sin(i，j)和Sout(i，j)的值越大，ST(i，j)越大；（2）Sin(i，j)和Sout(i，j)的值越接近對稱，ST(i，j)遞增速度越快。式（5）利用共鄰節(jié)點的入度和出度相似度影響節(jié)點間的相似關(guān)聯(lián)程度，入度和出度相似度越大并且越具有對稱性，節(jié)點間相似性越強。為了計算方便，將ST(i，j)的取值范圍歸一化為[0,1]，取值變化如圖2（a）所示。假如簡單照搬余弦相似度算法，ST(i，j)會考慮取值為Sin(i，j)、Sout(i，j)中的任意一項，或者不考慮邊權(quán)方向而直接相加后納入計算，算法會忽略邊對稱性、方向性等因素所產(chǎn)生的作用，導(dǎo)致計算結(jié)果準確度不高，共鄰節(jié)點對相似度的貢獻差異不能充分地表現(xiàn)出來，以此來評估相似度會降低計算結(jié)果的有效性。

圖2 共鄰相似度與直連相似度的取值變化趨勢

步驟2：計算兩個節(jié)點的直連相似度LT(i，j)，沿用步驟1的算法思路，如式（6）所示。

其中，Wij和Wji分別為節(jié)點對之間直連兩個方向的邊權(quán)值，兩者乘積反映LT(i，j)的直連相似度。兩個邊權(quán)值越不對稱，LT(i，j)值變化幅度越大，越接近于0，其取值變化如圖2（b）所示。如果依據(jù)其他常用的相似度計算方法，LT(i，j)直接被認為等于0，忽略了其對節(jié)點相似度的影響。

步驟3：計算兩個節(jié)點之間的相似度S(i，j)，直接采用ST(i，j)和LT(i，j)兩者的平方平均數(shù)求得，如式（7）所示。

上述公式具有以下特點：

（1）對于有向加權(quán)圖，S(i，j)能較好地反映相鄰節(jié)點個數(shù)、不同方向的相似度、節(jié)點間直連相似度、邊權(quán)對稱性等因素對兩個節(jié)點相似度的綜合影響。

（2）當兩個節(jié)點不存在直接雙向相連的包含節(jié)點間僅有單向連接的情況，即LT(i，j)=0 時，兩個節(jié)點的相似度為，由共鄰節(jié)點對兩個節(jié)點在雙向連接邊權(quán)值的出度和入度相似度計算得出，通過比較與共鄰節(jié)點的關(guān)系來確定相似性，與大多數(shù)文獻提出的相似度算法思路一致。

（3）當兩個節(jié)點存在雙向相連并且無共鄰節(jié)點時，ST(i，j)=0，兩個節(jié)點的相似度減弱為。此時節(jié)點相似度由直連相似度決定，僅受兩個節(jié)點直連邊權(quán)值影響。

（4）當兩個節(jié)點存在雙向相連并且有共鄰節(jié)點時，節(jié)點相似度由共鄰相似度和直連相似度共同貢獻所得。特別地，當兩個節(jié)點間雙向直連權(quán)值越不對稱時，LT(i，j)遞減變化幅度越大，對S(i，j)產(chǎn)生的影響程度越小，此時ST(i，j)起主導(dǎo)作用。

步驟4：基于上述算法設(shè)計，遍歷所有空間位置節(jié)點，最終形成有向加權(quán)圖的相似度鄰接矩陣，如式（8）所示。

上述矩陣具有對稱性，S(i，j)=S(j，i)，對角線元素全為0，非對角線元素表示節(jié)點對的相似強度。

3 基于相似度鄰接矩陣的聚類分析

基于相似特性的鄰接矩陣S進行譜聚類分析，算法步驟如下：

步驟1：按照式（9）獲得標準化的拉普拉斯矩陣N。

步驟2：獲取矩陣N的特征值和特征向量?；诰仃嘚計算出以行向量存放的一維特征值矩陣λ和以列存放的特征向量矩陣F，F(xiàn)的每一列fi（i=1，2，…，n）代表一個特征向量。

步驟4：聚簇劃分。將F''中的每一行作為一個k維的樣本，共n個樣本，聚類維數(shù)為k，對這些新生成的樣本點進行K-means聚類，聚成k類，最后輸出聚類結(jié)果，得到不同聚簇劃分。

4 實例驗證

為了驗證本文相似度算法的有效性和合理性，本文以真實的高校學(xué)生生活和學(xué)習(xí)數(shù)據(jù)集作為實驗對象，按照上文的相似度算法構(gòu)建鄰接矩陣，采取譜聚類后從節(jié)點聚集模塊度、輪廓系數(shù)等方面進行對比分析。

4.1 數(shù)據(jù)集介紹

數(shù)據(jù)集1：高校學(xué)生消費群體由各類人群構(gòu)成，群體中成員具有不同的飲食習(xí)慣，對不同商戶的消費物品產(chǎn)生不同程度的偏好，消費物品在質(zhì)量、服務(wù)、價格、口味等方面各異，吸引不同人群在商戶之間進行選擇性消費，消費者在商戶之間發(fā)生馬爾科夫鏈轉(zhuǎn)移現(xiàn)象。學(xué)校以此來探詢各商戶分布結(jié)果是否具有更優(yōu)的合理性，并預(yù)測相似經(jīng)營商戶間的關(guān)聯(lián)程度，為學(xué)校優(yōu)化餐飲質(zhì)量提供決策參考。本實驗采用華中師范大學(xué)一卡通系統(tǒng)的刷卡消費數(shù)據(jù)集，涉及校園卡用戶數(shù)量為54243個，其中，2022年3月至6月消費流水總記錄為93951622條，每條記錄選取學(xué)生學(xué)號、商戶標識、消費物品名、消費時間等作為實驗數(shù)據(jù)參考點，其中消費物品名與商戶標識綁定。為了減少消費量極小的商戶對分析結(jié)果產(chǎn)生干擾，流水記錄總數(shù)低于1000條的商戶被過濾掉，最后進入分析的有效商戶數(shù)量有167個。消費流水總記錄100萬次以上的商戶占11.98%，50萬～100萬次的商戶占34.13%，10萬～50萬次的商戶占43.11%，10萬次以下的商戶占10.78%，能在最大程度上反映出用戶對商戶形成的選擇性消費趨勢。將上述商戶標識用vi（i=1，2，…，167）表示，得到有167 個節(jié)點的狀態(tài)空間。依據(jù)式（2）將商戶間的消費活動關(guān)系轉(zhuǎn)化為有向加權(quán)圖，圖中每一條方向線表明當前商戶vi的消費群體向另一個商戶vj轉(zhuǎn)出的概率Pij。狀態(tài)空間的商戶間轉(zhuǎn)移次數(shù)越多，轉(zhuǎn)移關(guān)系權(quán)重就越大。

數(shù)據(jù)集2：高校學(xué)生選修公選課時因課程熱度或個人需求不同出現(xiàn)選課次數(shù)互轉(zhuǎn)現(xiàn)象，采用以此形成的選修課聚簇分布來評估課程間的相關(guān)性、緊密性及相似熱度，方便學(xué)校教務(wù)部門及時了解公選課開設(shè)情況，并且要求評估的算法要具備比較高的準確度。實驗數(shù)據(jù)來源于華中師范大學(xué)2014—2023年的學(xué)生選課系統(tǒng)數(shù)據(jù)集，有效的選課記錄有2283226條，參與分析的課程有294門，參與選課的學(xué)生有44548位，在選課記錄中選取學(xué)生學(xué)號、課程代碼、學(xué)期標識、選課時間等參與分析。將上述學(xué)生選課活動的課程標識記為vi（i=1，2，…，294），共有294 個節(jié)點的狀態(tài)空間。依據(jù)式（2）將選課活動關(guān)系轉(zhuǎn)化為有向加權(quán)圖，圖中每一條方向線表明選修課程vi的學(xué)生群體向另一門課程vj轉(zhuǎn)出的概率Pij。

4.2 聚類模塊度對比

為了評價本文算法對實例數(shù)據(jù)集節(jié)點的劃分質(zhì)量，引入聚類模塊度進行分析。一般來說，聚類模塊度值越大，則對應(yīng)的社區(qū)聚類個數(shù)越準確，并且更加接近真實的社區(qū)結(jié)構(gòu)分布情況。以數(shù)據(jù)集1和2為例，分別選取BDMS、文獻[6]相似度、余弦相似度，按照本文譜聚類分析步驟進行實驗對比，聚類模塊度比較結(jié)果如表1和表2所示。經(jīng)過多次對商戶節(jié)點進行聚類合并后，當數(shù)據(jù)集1和2的聚類數(shù)量分別被劃分為2～5 個和2～7 個時，BDMS 結(jié)合譜聚類分析獲得的聚類模塊度值大于0.3，且高于對比算法。在聚類個數(shù)為3～10 個時，文獻[6]相似度和余弦相似度的聚類模塊度值都明顯低于本文算法的計算結(jié)果。綜上所述，BDMS 結(jié)合本文譜聚類算法在相似性度量及聚簇劃分上優(yōu)于對比算法，具有發(fā)現(xiàn)潛在的學(xué)生活動社區(qū)網(wǎng)絡(luò)節(jié)點的分布的能力。

表1 數(shù)據(jù)集1相關(guān)算法聚類模塊度比較

表2 數(shù)據(jù)集2相關(guān)算法聚類模塊度比較

4.3 聚類結(jié)果輪廓系數(shù)對比

聚類結(jié)果的輪廓系數(shù)是聚類的密集與分散程度的評價指標[19]。從輪廓系數(shù)評價算法原理可知，其取值范圍為（-1，1），且其值越接近于1，代表聚簇內(nèi)聚集度和聚簇間分離度效果越優(yōu)。通過評價指標不僅可以評估相似度計算針對不同聚類算法的有效性,而且還可以很好地了解給定有向加權(quán)圖的節(jié)點動態(tài)關(guān)系。針對數(shù)據(jù)集1 和2，將BDMS譜聚類與BDMS、余弦相似度、文獻[6]及文獻[7]相似度等進行K-means聚類對比實驗，同時檢驗BDMS算法采用傳統(tǒng)聚類分析的效果。聚類數(shù)k在2～30 取值，計算過程獲取一系列聚類的輪廓系數(shù)參與比較，結(jié)果見圖3。

圖3 不同相似度算法聚類結(jié)果的輪廓系數(shù)對比

從圖3 中可以看出，本文BDMS 聚類結(jié)果的輪廓系數(shù)在最優(yōu)時分別達到0.9534、0.7380，并且從整體上來看，不同聚類數(shù)的輪廓系數(shù)也明顯高于其他四種計算方式（不含余弦相似度+譜聚類），結(jié)果顯示，采用BDMS 結(jié)合譜聚類分析時對社區(qū)聚簇劃分具有較大優(yōu)勢。

進行K-means 聚類時，相比于余弦相似度、文獻[6]和文獻[7]提出的相似度算法，BDMS算法得到的輪廓系數(shù)從整體上看平穩(wěn)性相對較好。雖然文獻[6]考慮到有向加權(quán)圖的邊權(quán)和邊方向信息，文獻[7]提出以用戶參與同一事件次數(shù)越多和參與事件類別越多為條件，分別建立無向圖相似度模型，但當處于不同聚類數(shù)時，聚類結(jié)果的輪廓系數(shù)相對偏小。另外，針對余弦相似度采用譜聚類分析，根據(jù)圖3（a）和（b）的結(jié)果，其輪廓系數(shù)分布比較接近采用BDMS進行譜聚類分析的計算結(jié)果，但是與表1和表2中的聚類模塊度相比，兩者聚類劃分的評估結(jié)果差別較大，表明該方法不推薦在譜聚類中使用，而BDMS卻能很好地適應(yīng)譜聚類和傳統(tǒng)K-means聚類的分析。

5 結(jié)論

本文以社區(qū)活動形成的有向加權(quán)圖為研究對象，設(shè)計了一種雙向度量相似度的計算方法，并采用譜聚類無向切圖實現(xiàn)社區(qū)聚簇的最優(yōu)劃分，將有向加權(quán)圖節(jié)點劃分問題轉(zhuǎn)化為無向加權(quán)圖聚類問題。通過理論和實例分析，得出如下結(jié)論：

（1）BDMS算法思路簡單。依托馬爾科夫鏈現(xiàn)象存在的節(jié)點轉(zhuǎn)移關(guān)系，算法提取較少的樣本信息即可構(gòu)建有向加權(quán)圖，比較容易實現(xiàn)。

（2）BDMS算法能在很大程度上真實體現(xiàn)節(jié)點間的相似關(guān)系。算法綜合考慮了影響計算結(jié)果的諸多因素，并將各種因素的合理性在計算中體現(xiàn)出來，節(jié)點間關(guān)系的表示與實際接近。

（3）相比文中其他相似度算法，BDMS 算法結(jié)合譜聚類無向切圖，在聚類分析時輸出結(jié)果準確度高，能夠更好地發(fā)現(xiàn)潛在的社區(qū)結(jié)構(gòu)，同時在譜聚類和傳統(tǒng)K-means聚類分析中表現(xiàn)出很好的適應(yīng)性，并且在高校學(xué)生數(shù)據(jù)集的實例驗證中驗證了其有效性。為更充分地利用節(jié)點相似度進行快速聚簇劃分，后續(xù)還可在子圖內(nèi)節(jié)點聚集質(zhì)量和進一步優(yōu)化算法方面開展工作。