圖聚類的算法及其在社會關系網絡中的應用

袁璐 鄭策 山東工程職業技術大學

在大數據時代下，聚類這種不用監督的學習算法占有非常重要的地位。隨著科技的不斷發展，聚類算法的研究也取得了非常大的進步。而本文主要對圖聚類的算法進行分析和研究，并在劃分的圖聚類中，對點和點之間距離的計算方法重點進行比較同時也比較其對聚類結果的硬性。還有因社會關系網絡圖中的點是沒有坐標值的，因此無法使用曼哈坦距離和歐幾里得距離，但可以使用K-medoids 聚類算法。在使用此聚類算法時，可以使用隨機漫步距離算法和最短距離算法，社會關系網絡圖通過DBLP 數據集構成各個子圖，并結合相關實驗數據對兩種算法的優缺點進行驗證，從而進一步得到最短距離算法獲得的聚類效果最佳。

一、聚類、圖聚類以及社會網絡綜述

聚類指的是把數據集分成若干類或簇的過程，從而使不同類數據對象的相似度較低的讓同時使同類數據對象的相似度較高。而目前的聚類算法有：層次聚類算法、網格聚類算法、劃分聚類算法、密度聚類算法以及模型聚類算法等。

在對聚類進行分析時，其變體是一項非常有挑戰的研究課題，即圖聚類。而其主要指的是把圖中相關的邊分以及相對連接緊密的結點組成一個可以用一個抽象結點來表示的子圖。其子圖內各結點的相似性比較高，但子圖之間的結點只有較低的相似性。另外圖聚類有許多不同的方式，突出的有基于密度的聚類、Markov 聚類以及譜聚類等。

社會網絡分析在20 世紀30 年代被提出，并成為一種相對比較重要的社會定量研究方法。其主要指社會成員以及社會成員之間關系的集合，并用來表示成員間各種社會關系的邊以及各成員的節點，從而組成圖結構，進而對社會網絡進行描述[2]。另外，社會關系有很多種表現形式，例如：上下級之間的關系、文章合著關系、朋友之間的關系以及科研合作關系等。還有社會網絡關系的圖聚類算法主要有：Kernighan-lin 算法、G-N 算法、Newman 算法、過濾算法以及譜平分算法等。

二、圖聚類的算法

1、最短路徑距離算法

在圖論研究中比較經典的一個算法問題就是最短路徑問題，而最短路徑問題時在圖中的兩個點之間找一個最短的路。最短路徑距離算法也叫作Dijkstra 算法，其思想是：設G=（V,E,W）的帶權有向圖。也就是說先把圖中的頂點幾何V 組成兩組，一組是對最短路徑的頂點集合（S）已求出，另一組是對其余最短路徑的頂點集合（U）未求出，然后把未求出最短路徑的頂點根據最短路徑長度的增長順序依次加入到已求出最短路徑的頂點集合中去。

2、隨機漫步距離算法

若P 是一個由多個（N）頂點組成的圖GN×N 轉移概率矩陣，那么此矩陣的第i 行第j 列的元素為第i 個頂點一步跳轉到第j 個頂點的概率值；若 是隨機漫步從第i 個頂點到第j 個頂點走的最大步長，并假設隨機漫步起始概率為c ∈（0,1），那么隨機漫步的第i 個頂點到第j 個頂點距離的定義為：其中T 指的是第i 個頂點到第j 個頂點的一條路徑，步長使lengh（T），對應的轉移概率是P（T）。而隨機漫步距離矩陣指的是各頂點之間的隨機漫步距離組成的矩陣，其公示為：，其中，P 是圖G 的轉移概率，Ri是l 步內可達到的隨機漫步距離矩陣。

3、K-medoids 算法

K-medoids 算法的工作過程為：先隨機從n 個數據對象中挑選k 個對象當作初始聚類的中心，而剩下的其他對象就按照他們和這些聚類中心的距離依次分配到和其最相似的聚類；其次，對各個聚類的新聚類中心進行再次計算時，可選擇此聚類中距離均值點最近的真實點，并不斷對這個過程進行重復，從而使各個點的分配不在出現變化的同時也能得到滿足。在這個算法中，初始聚以K 個對象為中心點，之后以局部最佳結束，但這個方法對孤立點非常敏感。因此，在對這個算法進行改進時，初始聚類的中心點先隨機選取一個來當做對象；其次，對第二個聚類中心點進行選取時，其和初始聚類的中心點的距離要最遠；然后到選取去第三個聚類中心點時，和第二個聚類中心點的挑取一樣，并依次類推，直到第k 個聚類中心點為止。

三、實驗

1、衡量指標

衡量指標用density 來表示，若圖是無向圖，那么就先要對整個大圖進行統計，而圖在沒有進行分割之前，總共有n 條邊，然后依次計算k 類的每類包含的點之間的邊數，假如分別是n1,n2,...,nk,那么最后的計算就是density=（n1+n2+...+nk）/n。

當用程序將這個算法進行實現后，其運行程序收集數據，指在每個K 值的情況下，需要進行10 次分類，之后取10 次分類比率的比均值當做前k 值下的最后比率density，通過兩個算法的density 值比較出優劣，其中，最短距離算法得到的比率用density1 表示，隨機漫步距離算法得到的比率用density2 表示，對比如圖1 所示。

圖1 隨機漫步距離和最短距離的比率圖

從圖中可以看出，隨著分的類逐漸增多，類和類之間的邊也就增多，相反類內部的邊就越少，因此density 呈現下降趨勢；還有最短距離算法和隨機漫步距離算法相比，最短距離算法獲得的density 較高。

2、聚類效果

使用最短距離算法，把大小數據劃分成15 小類，每類數據是相同領域合著關系比較緊密的作者編號，通過實驗證明，分類成效非常理想。結合每個作者之間合著文章的論文數量，畫出分類之前的分布圖（如圖2），經過重復迭代，最后分成15 小類，而這時的分布圖如圖3.最后實驗情況和實際情況相同，分類結果比較理想。

圖2 分類前的點分布圖

圖3 分類后的點分布圖

四、結束語

在圖聚類進行研究時，使用隨機漫步算法和最短距離算法這兩種不同的距離算法來衡量各個點之間的相異度。而DBLP 數據集建立的合作關系社會網絡圖，使用K-medoids 聚類算法，把大圖分為K 類，使相同領域合著關系比較緊密的劃分在同一類當中，最后通過實驗數據得出，最短距離算法獲得的聚類效果比較理想。