一種基于鏈路預測的圖聚類算法

金 超，張龍波，王 雷，安建瑞，懷 浩，王曉丹

(山東理工大學 計算機科學與技術學院，山東 淄博 255049)

?

一種基于鏈路預測的圖聚類算法

金 超，張龍波，王 雷，安建瑞，懷 浩，王曉丹

(山東理工大學 計算機科學與技術學院，山東 淄博 255049)

通過重新定義傳統GN算法的邊介數計算，提出了一種基于鏈路預測方法的圖聚類算法；并且在分析GNRA仍舊存在的不足的基礎上，給出了其改進算法IGNRA. 通過對常用的四組數據集進行實驗比較發現：所提出的GNRA算法在效率上比傳統的GN算法能夠明顯提高，而IGNRA相比較GNRA、GN具有最低的計算復雜度.

圖聚類；GN算法；鏈路預測；

聚類是將物理或抽象對象集合劃分為簇的過程.每一個簇內盡可能相似，簇間盡可能相異.圖聚類是聚類分析中一個重要的研究方向，它是將圖中連接緊密的結點與邊劃分為一個子圖，子圖內結點相似性較高，子圖間結點相似性較低.在社會關系網絡分析[1-2]中，圖聚類可以發現其中的“小世界”，即：發現社會網絡中潛藏的社會結構.

1 相關研究

近年來，隨著社會關系網絡分析的廣泛應用，圖作為一種數據結構在社會關系網絡分析中所起到的作用越來越大.使用圖聚類[3-5]的方法對社會關系網絡挖掘是目前的一個研究熱點.例如，文獻[6]中介紹了一種基于凝聚的層次聚類算法，即：FN(Fast Newman algorithm)算法.該算法定義了一個優化函數，每次合并時通過使優化函數值增大最多或者減少最少.該算法能夠得到較好聚類結果，時間復雜度較高.文獻[7]提出了一種基于結構相似性的圖聚類算法，SCAN(Structural Clustering Algorithm for Networks，SCAN) 算法.該算法首先通過參數閾值獲得核心結點，然后通過核心結點進行簇擴充.算法時間復雜度較低，參數好壞對聚類質量影響較大.

GN(Girvan-Newman)算法[8]是一種經典的基于分裂的層次聚類算法.在一個擁有m條邊，n個結點的簡單圖中，通過不斷的移除邊介數最大的邊來獲得社區的劃分,其中邊介數是指圖中通過該邊的最短路徑的數目.GN算法能夠得到較為準確的劃分結果，但是其邊介數的計算，時間復雜度較高，為O(mn).當前GN算法的改進主要有兩種策略，即：1.使用其他相似性度量函數取代邊介數計算的策略； 2.將GN算法并行化的策略.第一種策略主要用到的方法有蒙特卡洛方法[9]，結點中心度[10]等.該方法主要是以犧牲算法的聚類精度以提升算法的運行效率.第二種策略則主要有兩種方式，一個是從多源點出發計算邊介數[11]，然后求和；另一個是使用Mapreduce來進行并行化計算邊介數[12].使用這種策略，聚類精度較好，但編程過于復雜，對硬件要求較高.本文使用第一種策略，通過對鏈路預測方法的分析，利用鏈路預測中局部相似性指標RA(Resource Allocation, RA)[13]來取代GN算法中復雜的邊介數計算，提出一種基于鏈路預測的圖聚類算法GNRA(Girvan-Newman algorithm based on Resource Allocation, GNRA)及其改進算法IGNRA(improved Girvan-Newman algorithm based on Resource Allocation, IGNRA)算法.

2 GNRA算法

鏈路預測[14-16]是指通過已知的網絡結構等信息預測網絡中尚未產生連邊的兩個結點之間產生連邊的可能性.鏈路預測可以發現網絡中的缺失邊.在一個網絡中，假設擁有連邊的兩個結點邊缺失，預測這兩個結點之間生成連邊的可能性.可以用這個可能性度量任意兩個結點間的相似性.文獻[13]從網絡資源分配的角度提出一種指標Resource Allocation，簡稱RA.RA的計算主要考慮兩個結點之間的共同鄰居結點，因此計算時間復雜度較低.采用RA相似性代替GN算法中復雜的邊介數計算，能夠使算法時間復雜度得到有效降低.

2.1 相關定義

本文提出的GNRA是一種基于分裂的層次聚類算法，使用該算法不需要輸入參數即可發現網絡中的簇結構.該算法主要針對無向、非加權圖的簡單圖G=(V,E)，V表示一系列的結點，E表示邊.圖中邊數用m表示，結點數用n表示.

定義1 鄰居結點

令u∈V，u的鄰居結點用Nu來表示，則

(1)

定義2 RA相似性

(2)

其中u,v∈V，Nu表示結點u的鄰居結點，k(z)表示結點z的度.

定義3 邊結構

定義4 模塊度

(3)

其中，m是圖中的邊數，Auv表示結點u和結點v之間的邊數(通常為0或1).kukv/2m 表示結點u和v之間期望的邊數，ku表示結點u的度數.δsu,sv是克羅內克函數，若結點u，v在同一個簇內，則為1，否則為0.使用模塊度來描述得到的聚類結果的緊湊程度.

2.2 GN算法描述

GN算法是由Newman和Girvan兩位在2002年提出來的.它是一個經典的基于分裂的社區發現算法.該算法的思想是不斷的從網絡中移除邊介數最大的邊，加入模塊度[17]Q后其主要流程如下所示：

1) 計算網絡中所有邊的邊介數.

2) 刪除網絡中邊介數最大的邊，若出現新的社區，則重新計算模塊度Q，記錄此時網絡結構.

3) 重新計算新的網絡的所有邊的邊介數.

4) 重復步驟2,3，直到網絡中每一個結點就是一個社區為止.選取模塊度Q值最大時的狀態作為該網絡的最終狀態.

算法流程圖如圖1所示.

GN算法的準確度較高，但是計算速度慢，邊介數計算的開銷過大，時間復雜性高，為O(m2n).因此，它只適合處理中小規模的網絡.

2.3 GNRA算法描述

GN算法在計算邊介數的過程當中，時間復雜度比較高，算法運行效率很低.針對GN算法的缺點，采用鏈路預測中的RA方法來代替GN算法中的邊介數計算，提出了一種基于鏈路預測的圖聚類算法GNRA，算法的時間復雜度得到明顯的改善.GNRA算法的主要步驟如下：

圖1 GN算法流程圖

圖2 GNRA算法流程圖

(1) 計算網絡中所有邊的相似性g(z)，不相鄰的結點之間相似性記為0.

(2) 找到相似性最小的邊，并將其從網絡當中移除.如果出現新的社區，則計算此時模塊度并記錄此時社區結構.

(3) 重新計算網絡中邊的相似性.

(4) 重復步驟2,3，直到每一個結點是一個社區為止.

(5) 將網絡中的獨立結點進行劃分，若僅與一個簇相連，則將該結點加入該簇，若與兩個及兩個以上簇相連記為中心點，不與任何簇相連記為離群點.

算法流程圖如圖2所示.

3 IGNRA算法

GNRA算法相對于GN算法時間復雜度得到了降低，但是仍然較高.在實驗的過程當中，嘗試只計算一次RA相似性，然后逐步的刪除相似性較小邊的過程.同時發現在計算RA的過程當中，出現了許多擁有相同相似性的邊，因此試著同時刪除這些邊.改進的GNRA算法過程如下：

(1) 計算網絡中所有邊的相似性g(z)，不相鄰的結點之間相似性記為0.

(2) 找到相似性最小的邊(邊可能不只有一條)，并將其從網絡當中移除.如果出現了新的社區，則計算此時模塊度并記錄此時社區結構.

(3) 重復步驟2，直到每一個結點是一個社區為止.

(4) 劃分獨立結點：獨立結點與同一個簇相連則歸入該簇；若與不同簇相連則為中心點；不與任何簇相連則為離群點.

(5) 選擇模塊度最大的劃分作為最終劃分.

算法流程圖如圖3所示.

圖3 GNRA算法流程圖

同GNRA算法相同，給出一個擁有m條邊，n個結點的簡單圖，計算RA相似性所需要的時間復雜度為O(m)，刪除邊的過程最多需要刪除m條邊，因此，刪除邊的過程時間復雜度也為O(m)，因此改進的GNRA算法的時間復雜度為O(m+m)，即為O(m)，該算法的時間復雜度呈線性.

4 實驗結果及分析

為了驗證提出算法的有效性，實驗采用四組常用數據集進行測試，具體數據集見表1.實驗環境：處理器為Intel(R)Core(TM)i5-3470，CPU為3.2GHz，內存4GB，操作系統MicrosoftWindows7，使用Java作為編程語言，借助Eclipse開發平臺，實現了GNRA算法和IGNRA算法.

表1 常用數據集

數據集結點數邊數平均度平均路徑長度KDD-toy14253.5712.4zachary-karate34784.5882.4college-football11561310.6612.5football20061807878.7443

首先，分別采用GN算法和GNRA算法對上述數據集進行試驗，得到運行時間對比結果見表2.

表2 算法運行時間對比 ms

數據集GNGNRAIGNRAKDD-toy365415zachary-karate21114879college-football842065750462football200635295313620752

由以上分析，GN算法與GNRA算法時間復雜度分別為O(m2n)和O(m2)，算法運行時間與邊數平方的關系如圖4所示.

圖4 GN與GNRA算法運行時間與邊數平方的關系

GNRA算法與IGNRA算法時間復雜度分別為O(m2)和O(m)，算法運行時間與邊數的關系如圖5所示.

圖5 GNRA與IGNRA算法運行時間與邊的關系

GN算法計算邊介數所需要的時間復雜度為O(mn)，刪除m條邊所需要的時間復雜度為O(m)，因此總共所需要的時間復雜度為O(m2n).由2.3節知道GNRA算法的時間復雜度為O(m2).由表2及圖4可以清楚的看出，GNRA算法相較于GN算法來說，時間復雜度大大降低，其時間復雜度與邊的平方成正比.由理論分析、表1、圖5可以看出，IGNRA算法時間復雜度得到進一步降低，其時間復雜度與邊的數目成正比.因此，從理論與實驗上證明了IGNRA算法比GNRA算法具有更低的時間復雜度.

本文采用模塊度對聚類結果質量進行度量.一般情況下，一個網絡(圖)的模塊度在0.3～0.7之間，模塊度越高，表示聚類的結果越好，簇越緊密.模塊度度量結果見表3.

表3 GN算法與GNRA、IGNRA算法模塊度對比

數據集GNGNRAIGNRAKDD-toy0.4960.48960.4864zachary-karate0.40980.41110.3914college-football0.59420.59630.5865football20060.58360.56770.5579

由表3可以看出，GN算法與GNRA算法相比，模塊度不相上下.GNRA算法與IGNRA算法相比，模塊度有所下降.當然模塊度高卻不一定與真實情況相符，但在一般情況下，真實的聚類結果與模塊度最高時相差不大.

5 結束語

針對傳統GN算法時間復雜度高的缺點，本文在GN算法的基礎上，引入鏈路預測中RA相似性計算方法，提出了改進的GN算法，稱為GNRA算法.并且，對GNRA算法進一步分析，提出了其改進版本IGNRA算法.與GN算法相比，GNRA算法能明顯降低時間復雜度，并能夠分辨中心點和離群點.同時，通過對模塊度的對比，可以發現：GNRA算法得到的簇結構與GN算法得到的簇結構相差不大.而IGNRA與GNRA相比，時間復雜度得到進一步的降低.由于所提算法是利用鏈路預測中的RA相似性來進行簇劃分的，當遇到稀疏圖(平均度較低)情況時，劃分結果還不甚理想，如何克服這一不足將是下一步的研究重點.

[1] OCHAB J K, BURDA Z. Maximal entropy random walk in community finding[J]. European Physical Journal Special Topics, 2012, 216(1):73-81.

[2] 辛宇, 楊靜, 謝志強. 基于隨機游走的語義重疊社區發現算法[J]. 計算機研究與發展, 2015, 52(2):499-511.

[3] MORADI P, AHMADIAN S, AKHLAGHIAN F. An effective trust-based recommendation method using a novel graph clustering algorithm[J]. Physica A Statistical Mechanics & Its Applications, 2015, 436:462-481.

[4] 薛潔, 劉希玉. 基于DNA計算的層次圖聚類算法[J]. 計算機工程, 2012, 38(12):188-190.

[5] TABRIZI S A, SHAKERY A, ASADPOUR M, et al. Personalized PageRank Clustering: A graph clustering algorithm based on random walks[J]. Physica A Statistical Mechanics & Its Applications, 2013, 392(22):5772-5785.

[6] NEWMAN M E J. Fast algorithm for detecting community structure in networks [J]. Physical Review E, 2004, 69(6):279-307.

[7] XU X, YURUK N, FENG Z, et al. SCAN: a structural clustering algorithm for networks [C].//ACM SIGKDD Intermational Conference on knowledge Discovery and Data Mininy.ACM,2007:824-833.

[8] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7 821-7 826.

[9] TYLER J R, WILKINSON D M, HUBERMAN B A. E-Mail as Spectroscopy: Automated Discovery of Community Structure within Organizations[J]. Information Society, 2005, 21(2):143-153.

[10]戴愛明, 高學東, 王立敏. 一個基于中心度的社團結構發現新算法[J]. 計算機應用研究, 2011, 28(8):2 909-2 911.

[11] 楊文文.基于改進的GN算法的社區發現技術 [D].吉林大學，2012.

[12]于靜雯, 楊冰. 基于MapReduce框架下的復雜網絡社團發現算法[J]. 微型機與應用, 2014(22):74-76.

[13] ZHOU T, LYU L, ZHANG Y C. Predicting missing links via local information[J]. The European Physical Journal B - Condensed Matter and Complex Systems, 2009, 71(4):623-630.

[14] 呂琳媛. 復雜網絡鏈路預測[J]. 電子科技大學學報, 2010, 39(05):651-661.

[15] 黃立威, 李德毅, 馬于濤,等. 一種基于元路徑的異質信息網絡鏈路預測模型[J]. 計算機學報, 2014(04):848-858.

[16] 胡文斌, 彭超, 梁歡樂,等. 基于鏈路預測的社會網絡事件檢測方法[J]. 軟件學報, 2015(9):2 339-2 355.

[17] NEWMAN M E J. Communities, modules and large-scale structure in networks [J]. Nature Physics, 2012, 8(1): 25-31.

(編輯：劉寶江)

A graph clustering algorithm based on link prediction

JIN Chao, ZHANG Long-bo, WANG Lei, AN Jian-rui, HUAI Hao, WANG Xiao-dan

(School of Computer Science and Technology,Shandong University of Technology, Zibo 255049, China)

By redefining how to compute the edge betweenness of the traditional Girvan-Newman (GN) algorithm, a graph clustering algorithm which is named Girvan-Newman algorithm based on Resource Allocation (GNRA) is proposed by using the link prediction. Besides, on the base of analyzing the drawback of the GNRA, the improved Girvan-Newman algorithm based on Resource Allocation (IGNRA), which is the improved version of the GNRA, is also shown. The experimental results on four commonly used groups of the datasets demonstrate that the proposed GNRA algorithm performs better than the traditional GN algorithm in efficiency and the IGNRA has the lowest computation complexity in the three algorithms.

graph clustering; Girvan-Newman algorithm; link prediction;

2016-03-07

國家自然科學基金青年科學基金項目(61502282)

金超，男，jin_chao_hi@163.com; 通信作者：張龍波，男，zhanglb@sdut.edu.cn

1672-6197(2017)01-0017-05

TP301

A