程澤凱，張佳玉

（安徽工業(yè)大學 計算機學院，安徽 馬鞍山243032）

0 引 言

社會網(wǎng)絡是指社會個體成員之間因為互動而形成的相對穩(wěn)定的關系體系，這些個體成員擁有共同的興趣、同屬某一特定的主題或是共有某種屬性［1］。隨著社會關系網(wǎng)絡中關系數(shù)據(jù)的日益豐富，對關系數(shù)據(jù)的鏈接挖掘也成為各大研究者的熱門課題。社會網(wǎng)絡挖掘中，社會網(wǎng)絡可形式化描述為社會關系網(wǎng)絡圖，通過聚類方法將其劃分為不同的子圖，即抽取出其中隱含的子模式，就是節(jié)點聚類［2］，也就是社團發(fā)現(xiàn)。研究發(fā)現(xiàn)，社團結構是社會網(wǎng)絡具有的一個共同性質，滿足同一社團內部節(jié)點連接相對緊密、不同社團間節(jié)點連接相對稀疏的特點。社團內部成員具有很大的相似性，研究社團結構對于了解網(wǎng)絡結構與分析網(wǎng)絡特性，充分利用網(wǎng)絡價值都很重要。

社會網(wǎng)絡中除了存在拓撲結構信息外，還存在豐富的節(jié)點屬性信息，如何充分利用各方面的信息有效地發(fā)現(xiàn)社團結構成為社團發(fā)現(xiàn)中的基本問題，這種有效性體現(xiàn)在兩個方面：如何充分利用拓撲結構及節(jié)點屬性提高算法的準確率和如何提高算法的執(zhí)行效率。

1 社會網(wǎng)絡社團發(fā)現(xiàn)

通過對現(xiàn)有的社會網(wǎng)絡社團發(fā)現(xiàn)算法進行分析研究，我們將其分為兩類：基于優(yōu)化的圖聚類算法和基于啟發(fā)式的圖聚類算法［3］。第一類基于優(yōu)化的圖聚類算法通過設定聚類目標函數(shù)提出試探性的算法來獲取近似的社團結構。典型的有基于Laplace圖特征值的譜平分法［4］和在GN算法基礎上改進的基于modularity極值近似的 MEA算法［5］等等。該類算法并不能保證一個較高的Q值對應的就是較優(yōu)的社團結構，算法準確率較低。第二類基于啟發(fā)式的圖聚類算法通過設計符合現(xiàn)實意義的啟發(fā)式規(guī)則來識別社團結構。典型的有基于馬爾可夫隨機游走模型的啟發(fā)式符號網(wǎng)絡聚類算法 （FEC）［6］和能夠識別重疊網(wǎng)絡簇的派系過濾算法 （CPM）［7］等等。該 類算法一般都具有較高的時 間復雜度。

以上兩大類都是圖分割算法，此類算法只依賴圖的拓撲結構，這樣不充分的劃分條件導致社團劃分準確率低。具有相似屬性的節(jié)點之間更可能產生鏈接關系，在合著網(wǎng)絡中，一個組織內的成員不僅存在著合著關系 （關系數(shù)據(jù)），同時也具有較為相似的研究興趣 （屬性數(shù)據(jù)）［8］。為了得到更優(yōu)化的社團結構，研究者提出了解決圖聚類問題的新思路。程鴻等人提出一種統(tǒng)一隨機游走距離測量相似度的基于結構和屬性的SA－cluster圖聚類算法［9］；徐曉偉等人提出一種基于結構情境相似性的思想來計算網(wǎng)絡中節(jié)點相似度的SCAN算法［10］；林友芳等人設計和實現(xiàn)了一種將個體和鏈接屬性有效融合的社區(qū)發(fā)現(xiàn)算法CIG＿ESC［11］。

本文在分析現(xiàn)有算法的基礎上，針對算法只考慮圖的拓撲結構而忽略節(jié)點屬性影響及算法的時間復雜度高的問題，提出了一種基于節(jié)點相似度的社團發(fā)現(xiàn)算法，遵循圖聚類問題的另一種解決思路，即先綜合結構和屬性的影響求出節(jié)點相似度，然后使用傳統(tǒng)的空間聚類方法進行聚類。本算法結合SA－cluster算法中構建屬性擴展圖的思想，將屬性的影響加入拓撲結構圖中，然后使用SCAN算法中結構化相似度的計算方法求得屬性擴展圖中節(jié)點的相似度，最后設計一種基于節(jié)點相似度的k－means聚類算法來發(fā)現(xiàn)社會網(wǎng)絡圖中的社團結構。本算法在多個基準網(wǎng)絡數(shù)據(jù)集上的測試結果均驗證了算法在準確率和時間復雜度上的有效性。

2 基于節(jié)點相似度的社團發(fā)現(xiàn)算法

2.1 基本概念

2.1.1 屬性擴展圖

社會網(wǎng)絡的原始拓撲結構圖G＝（V，E，M）由圖中的節(jié)點集V、節(jié)點之間的邊集E和與節(jié)點關聯(lián)的m個屬性值的集合M ＝ ｛a1，.....，am｝組成，定義節(jié)點集V中的節(jié)點為結構節(jié)點，個數(shù)為N，邊集E中的邊為結構邊，用實線表示，原始圖如圖1所示。構造屬性擴展圖的步驟如下：將待考慮屬性的m個取值作為m個屬性節(jié)點加入原始圖中，若某結構節(jié)點具有該屬性，則在此結構節(jié)點和該屬性節(jié)點之間添加一條屬性邊，用虛線表示。構造后的屬性擴展圖G′可表示為G′＝ （V′，E′，M），V′為 ∪Vi和 ∪Vai的集合，如圖2所示。

圖1 原始圖

圖2 屬性擴展

圖1原始圖中含10個結構節(jié)點，圖中標明的是節(jié)點的類別屬性，含兩個值txt和xml，構造屬性擴展圖時，在原始圖中添加屬性節(jié)點R1：xml和R2：txt，并且在含該屬性的結構節(jié)點和該屬性節(jié)點之間添加屬性邊，從圖2中可以發(fā)現(xiàn)，屬性邊的加入使得屬性相同的節(jié)點之間連接更加緊密。

2.1.2 基于結構情境的相似度

基于結構情境相似性的思想來源于以下規(guī)則：在社會網(wǎng)絡中如果兩個節(jié)點有相似的近鄰，則這兩節(jié)點就是相似的，即在現(xiàn)實的社會網(wǎng)絡中，兩個從共同朋友那里接受推薦的人常常做出相似的決策。

定義 給定無向圖G＝（V，E，M），對于節(jié)點u∈V，u的領域定義為

使用情境化相似度的思想，用規(guī)范化的公共鄰域大小來度量兩節(jié)點u，v之間的相似性，該值越大，兩節(jié)點相似度越高。結構化相似度定義如下

上述定義是針對相鄰節(jié)點的，對于非相鄰節(jié)點，這種局部性定義不能正確表達節(jié)點間的距離，這里我們定義非相鄰節(jié)點間的結構化相似度由最短路徑上相鄰節(jié)點對的結構相似度的乘積的最大值來表達。其中，最短路徑使用廣度優(yōu)先遍歷方法得到

式中：vi、vj——圖中的 非 相 鄰 節(jié) 點，vh、vk——vi、vj的 最短路徑上的相鄰節(jié)點對。

2.1.3 社團模塊度

社團模塊度用于衡量整個網(wǎng)絡的劃分質量。假設網(wǎng)絡劃分為k個社團，定義k階矩陣E＝（eij）k＊k，eij表示網(wǎng)絡中連接兩不同社團i和j的節(jié)點的邊在所有邊中所占的比例。模塊度Q值定義為

式中：Tre＝∑eii為E對角線上元素之和，表示網(wǎng)絡中連接某一社團內部各節(jié)點的邊在所有邊中所占的比例；ai＝∑eij是每行中個元素之和，表示第i個社團中的節(jié)點與其它節(jié)點相連的邊在所有邊中所占的比例。模塊度Q值越大說明社團結構越明顯。

2.2 社團發(fā)現(xiàn)算法SASK

2.2.1 算法描述

給定無向圖G＝ （V，E，M），V 中節(jié)點總數(shù)為 N，M ＝｛a1，.....，am｝，其中ai（i＝1，.....，m）是節(jié)點關聯(lián)屬性的m個取值，在原始圖G中加入屬性節(jié)點和屬性邊構造屬性擴展圖，針對屬性擴展圖G′＝ （V′，E′，M）使用基于結構情境的相似度計算方法計算每個結構節(jié)點的結構相似度，屬性邊的加入會使得具有同一屬性的節(jié)點之間的相似度增大，對于每個屬性節(jié)點，計算其到所有與之相連的結構節(jié)點的轉移概率，并將此轉移概率與節(jié)點的結構相似度相結合計算出最終的節(jié)點相似度，最后使用改進的k－means聚類算法在節(jié)點相似度的基礎上對節(jié)點進行聚類，求得最終的社團結構，其中聚類初始中心點的選取遵循最大最小原則。該算法可簡稱為 SASK （K－means based on node similarity with structure and attributes）。

SASK算法流程描述如下：

輸入：無向網(wǎng)絡圖G＝（V，E，M）；

輸出：網(wǎng)絡G的社團結構；

步驟1 如果V為空，算法結束；否則，讀入原始圖G＝（V，E，M），根據(jù)屬性與節(jié)點的從屬關系構造屬性擴展圖G′＝ （V′，E′，M），得到G′中節(jié)點的鄰接矩陣；

步驟2 根據(jù)式 （1）～式 （3）計算得到屬性擴展圖G′中節(jié)點的結構相似度矩陣；

步驟3 當屬性節(jié)點與其它節(jié)點相鄰時，用屬性節(jié)點的轉移概率矩陣更新節(jié)點的結構相似度，得到節(jié)點相似度矩陣；

步驟4 使用改進的k－means算法對圖G′中的節(jié)點聚類。根據(jù)最大最小原則確定K個初始聚類中心點，即首先選擇度數(shù)最大的節(jié)點k1加入初始簇心core中，該類節(jié)點有較大的凝聚力，然后采用最小相似度原則將與已入簇節(jié)點的平均相似度S最小的節(jié)點作為新的初始聚類中心點加入初始簇心集合。其中，為了排除孤立點的影響，選取節(jié)點度數(shù)平均值作為候選簇心的篩選閾值；

步驟5 更新簇。將除初始聚類中心點以外的其它節(jié)點劃分到相似度較高的簇心所在的簇中，確定此次迭代后得到的社團結構；

步驟6 更新簇心集合。計算節(jié)點在已劃分好的社團內部的度數(shù)，將度數(shù)最大的節(jié)點作為新的簇心，得到新的簇心集合core。若新的簇心與上次迭代的簇心不同，則重復步驟5；若相同，則停止迭代，輸出最終的社團結構。

2.2.2 算法時間復雜度分析

假設網(wǎng)絡圖中含n個節(jié)點，m條邊。通過上述分析，節(jié)點結構化相似度的計算的時間復雜度取決于查詢節(jié)點的度deg（vi），總 代 價 為 O（deg（v1）＋...＋ deg（vn）），相當于每條邊都要被計算兩次的次數(shù)，因此時間復雜度為O（m）；使用最大最小原則選取k個初始聚類中心點時，每選取一個要比較的次數(shù)為n，因此中心點確立的時間復雜度為O（kn）；n個節(jié)點往k個簇中歸類時，需要比較的次數(shù)是kn，迭代次數(shù)是t，時間復雜度為O（nkt）。由此可得，算法總體上時間復雜度為線性復雜度O（（t＋1）kn＋m）。

3 實驗結果分析

3.1 帶屬性的人工構造的二社團網(wǎng)絡

如圖3所示是由11個節(jié)點構成的作者合著關系圖，兩節(jié)點之間有邊即代表兩作者合著一篇論文，xml和skyline是作者所著論文文獻類別屬性的兩個取值。

圖4是加入兩屬性值后構造得到的屬性擴展圖。通過算法驗證，屬性擴展圖的構造使得屬性的影響增大了，屬性相同的節(jié)點間的結構化相似度增加，用改進的k－means聚類算法作用于得到的節(jié)點相似度，迭代一次得到最終社團結構。其中，篩選閾值為度數(shù)平均值3。表1所示為去除算法第一步屬性擴展圖的構造得到的社團發(fā)現(xiàn)結果和SASK算法得到的結果，結果分析如下：

3.2 不帶屬性的數(shù)據(jù)集

圖3 作者合著關系

圖4 圖3的屬性擴展

表1 基于結構的結果與本文算法的結果對比

為了進一步驗證該算法的有效性和通用性，我們在將其在另外兩個社會網(wǎng)絡社團發(fā)現(xiàn)領域的基準數(shù)據(jù)集上進行測試，并將SASK算法的時間復雜度、準確率等性能指標與一些經(jīng)典算法在這些數(shù)據(jù)集上的測試結果進行對比。

3.2.1 Zachary’s Club空手道俱樂部網(wǎng)絡

Zachary空手道俱樂部網(wǎng)絡是 Wayne Zachary構造的美國空手道俱樂部成員關系網(wǎng)，如圖5所示，網(wǎng)絡由34個節(jié)點、78條邊組成，節(jié)點表示俱樂部成員，邊表示成員之間存在關系。該俱樂部就是否抬高俱樂部收費問題產生分歧，分成了以主管和校長為中心的兩個小社團。作為驗證社團發(fā)現(xiàn)算法的基準網(wǎng)絡，“Zachary空手道俱樂部網(wǎng)絡”常用于測試算法能否根據(jù)觀察到的網(wǎng)絡結構預測出最終的分裂情況。

圖5 Zachary空手道俱樂部網(wǎng)絡

根據(jù)上述算法步驟計算出節(jié)點相似度，使用最大最小原則選取兩個初始簇心，將最大度節(jié)點34（度數(shù)為17）作為第一個中心點加入簇心，在個節(jié)點度數(shù)大于篩選閾值為度數(shù)平均值5的條件下，節(jié)點1與節(jié)點34之間的有最小相似度0.11，根據(jù)最小相似度原則將節(jié)點1加入初始簇心；使用k－means算法迭代一次得到最終的社團結構。結果如圖5所示，是以節(jié)點1為中心的圓形標記的社團和以節(jié)點34為中心的方形標記的社團。事實上，節(jié)點1和節(jié)點34表示俱樂部的主管和校長。SASK算法與其它經(jīng)典算法在該數(shù)據(jù)集上的準確率及時間復雜度對比見表2。

表2 Zachary空手道俱樂部網(wǎng)絡準確率對比

表2的對比結果驗證了算法在該數(shù)據(jù)集上的有效性。

3.2.2 American College Football美國大學足球網(wǎng)絡

美國大學足球網(wǎng)絡是由Girvan和Newman針對美國大學生足球聯(lián)賽抽取出的社會網(wǎng)絡模型，其中，每個節(jié)點代表一個足球隊，節(jié)點間的邊表示兩球隊進行過比賽，該網(wǎng)絡含115個節(jié)點和616條邊。按地理位置劃分，球隊可分為12個聯(lián)盟，根據(jù)規(guī)定，聯(lián)盟內的球隊比賽的次數(shù)比不同聯(lián)盟的球隊多。該網(wǎng)絡是驗證社團發(fā)現(xiàn)算法的另一個常用基準網(wǎng)絡，但是網(wǎng)絡中含有一些噪聲節(jié)點，噪聲節(jié)點的存在會影響社團識別的準確率。

根據(jù)上述算法步驟，該數(shù)據(jù)集上最終得到的12個社團結構見表3。其中，上行是該網(wǎng)絡的實際社團結構，下行是SASK算法得到的社團結構，社團劃分的準確率根據(jù)正確劃分到該社團中的節(jié)點在正確社團節(jié)點中所占的比例來計算。

SASK算法識別出的社團結構與實際社團相比，有11個節(jié)點識別錯誤。由于孤立點及最大最小原則選取初始簇心時篩選閾值的設置的影響，其中一個簇心選擇錯誤，使得該簇中的節(jié)點被錯誤地分到其它簇中；其余的節(jié)點均能被識別出來，基本上與真實社團結構相符合，劃分的社團的準確率整體上可達86.7%，經(jīng)典的Newman快速算法在該數(shù)據(jù)集上的準確率為78%；趙鳳霞提出的k－means復雜網(wǎng)絡社團發(fā)現(xiàn)算法［12］在該數(shù)據(jù)集上的準確率為83%。

表3 SASK算法對美國大學足球網(wǎng)絡社團發(fā)現(xiàn)的結果

SASK算法共迭代6次，通過模塊度計算發(fā)現(xiàn)，迭代總體上向著模塊度增加的方向，表明迭代使得社團結構越來越明顯。每次迭代的模塊度Q值及變化趨勢如圖6所示。SASK算法發(fā)現(xiàn)的社團模塊度Q值為0.585，Newman快速算法中得到的最優(yōu)模塊度Q值為0.546。

圖6 模塊度Q值隨迭代次數(shù)的變化趨勢

4 結束語

本文創(chuàng)新點在于綜合了結構和屬性的因素，結合屬性擴展圖和結構化相似度的思想，提出了一種基于節(jié)點相似度的社團發(fā)現(xiàn)算法SASK，將圖聚類問題轉化為基于節(jié)點相似度的k－means空間聚類問題。與現(xiàn)有的社團發(fā)現(xiàn)算法相比，該算法發(fā)現(xiàn)的社團結構準確度更高，且時間復雜度是線性的。該算法在多個數(shù)據(jù)集上的測試結果均驗證了算法的有效性。圖節(jié)點間的鏈接關系也蘊含著豐富的信息，可用來衡量關系的強度，在未來研究中，可以將鏈接關系構造成邊權值，與圖拓撲結構和節(jié)點屬性融合起來處理社團發(fā)現(xiàn)問題。

［1］Han J，Kamber M，Pei J.Data mining：Concepts and techniques ［M］.3rd ed.San Francisco：Morgan Kaufmann Publishers，2011.

［2］Tan PN，Steinbach M，Kumar V.Introduction to data mining［M］.Beijing：Posts and Telecom Press，2011.

［3］YANG Bo，LIU Dayou，LIU Jiming.Complex network clustering algorithms ［J］.Journal of Software，2009，20 （1）：54－66 （in Chinese）.［楊博，劉大有，Liu Jiming.復雜網(wǎng)絡聚類方法 ［J］.軟件學報，2009，20 （1）：54－66.］

［4］Shiga M，Takigawa I，Mamitsuka H.A spectral clustering approach to optimally combining numerical vectors with a modular network ［C］／／NewYork：Proc of the 13th ACM SIGKDD Int’l Conf on Knowledge Discovery and Data Mining，2007：647－656.

［5］ZHU Xiaohu，SONG Wenjun，WANG Chongjun，et al.Improved algorithm based on Girvan－Newman algorithm for community detection ［J］.Computer Science and Technology，2010，4（12）：1101－1108. ［朱小虎，宋文軍，王崇駿，等.用于社團發(fā)現(xiàn)的Girvan－Newman改進算法 ［J］.計算機科學與探索，2010，4 （12）：1101－1108.］

［6］Yang B，Cheung W K，Liu J.Community mining from signed social networks ［J］.EEE Trans on Knowledge and Data Engineering，2007，19 （10）：1333－1348.

［7］Palla G，F(xiàn)arkas I J.Directed network modules ［J］.New Journal of Physics，2007，9 （6）：186－207.

［8］Ester M，Ge R，Gao B J，et al.Joint cluster analysis of attribute data and relationship data：The connected k－center problem ［J］.ACM Trans Know Discov，2008，2 （2）：1－35.

［9］Zhou Y，Cheng H，Yu J X.Graph Clustering Based on Structural／Attribute Similarities ［C］／／Proceedings of the 35th International Conference on Very Large Data Bases，2009：718－729.

［10］Xu X，Yuruk N，F(xiàn)eng Z，et al.SCAN：A structural clustering algorithm for networks ［C］／／CA，San Jose：Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2007：824－833.

［11］LIN Youfang，WANG Tianyu，TANG Rui，et al.An effective model and algorithm for community detection in social net－works ［J］.Journal of Computer Research and Development，2012，49 （2）：337－345 （in Chinese）.［林友芳，王天宇，唐銳，等.一種有效的社會網(wǎng)絡社區(qū)發(fā)現(xiàn)模型和算法 ［J］.計算機研究與發(fā)展，2012，49 （2）：337－345.］

［12］ZHAO Fengxia，XIE Fuding.Detecting community in com－plex networks using K－means cluster algorithm ［J］.Application Research of Computer，2009，26 （6）：2401－2404 （in Chinese）.［趙鳳霞，謝福鼎.基于K－means聚類算法的復雜網(wǎng)絡社團發(fā)現(xiàn)新方法 ［J］.計算機應用研究，2009，26（6）：2401－2404.］