基于PageRank模糊聚類的網絡社團挖掘

馬麗娜

(西安財經大學行知學院，經濟與統計學院， 陜西,西安 710038)

0 引言

近年來涌現出許多網絡社團挖掘(也稱為社團發現)算法[1-2]，從數學意義上來看，復雜網絡中的社團劃分是對具有連接相似關系的節點進行的聚類[3-4]。基于類原型的聚類算法，例如c均值聚類、模糊c均值(FCM)等，已在網絡社團挖掘中得到廣泛應用[5-6]，但是這些聚類方法的結果易受初始種子節點的影響，實驗結果不穩定，并且需要事先給定網絡社團個數。本文提出一種基于PageRank重要度和模糊c均值聚類的社團發現算法。該算法可以視為一種適用于網絡數據的改進FCM算法。首先，根據節點的PageRank值確定種子節點候選集，利用相似性閾值和最大最小模塊度自適應確定社團個數和最優種子集合。用譜映射的思想將網絡數據映射成特征空間上的向量數據，進而實施模糊c均值聚類，得到節點所屬各個社團的隸屬度值。在真實網絡上的數據實驗證明了所提出算法的有效性。

1 相關理論

1.1 模糊C均值聚類

(1)

其中，m為控制模糊劃分的權重參數，一般設為2,dik為數據xi到簇k的歐式距離。

(2)

(3)

不斷更新每個簇的簇中心vk(k=1,2,…,C)和隸屬度矩陣U，使得目標函數達到最小，可得到最優劃分。

1.2 網絡重要度和模塊度

PageRank是一種常用的網絡重要性度量，計算式為

(4)

其中,Na為所有指向a的網頁的集合，Kb為網頁b指向的網頁個數。

最大最小模塊度是一種常用的衡量網絡社團劃分準確率的指標，其定義如：

Qmax-min=Qmax-Qmin=

(5)

其中

(6)

Cx表示節點x所在的社團

(7)

(8)

(9)

模塊度函數值越大，對應的社團劃分結果與網絡真實的社團結構越接近。

2 基于RangRank的聚類社團挖掘

2.1 網絡初始種子選取

將復雜網絡中的節點看成網頁，那么節點的重要性就相當于節點所對應的PageRank值的大小。但種子節點的選擇不僅要看節點的PageRank值，還要依據節點之間的差異性。節點之間的相似性定義為

(10)

其中，nij為節點i和節點j的公共節點數，ki、kj分別為節點i和節點j的度。

首先將節點按PageRank值大小降序排列，把PageRank值后25%的節點從種子節點候選集中去掉。預先設置一個相似性閾值，選擇PageRank值最大的節點作為第一個種子節點，然后計算PageRank值次大節點和PageRank值最大節點之間的相似性。如果這個相似性的值小于預先設置的閾值，則將該節點加入到種子節點集中。以此類推，直到選出來的前75%的節點集中沒有節點滿足設定的相似性閾值就結束算法。通過不斷的調整相似性的閾值，可以得到不同數量的種子節點集，從而得到所有可能的初始的種子節點集。

2.2 譜映射

設網絡的鄰接矩陣為

A=(aij)n×n

(11)

其中，當節點i和節點j相連時，aij=1；否則，aij=0。記對角矩陣為

D=(dii)

(12)

其中，dii=∑aik表示與節點i相連的節點數量。譜映射的數據轉換過程如下：

(1) 計算Ax=tDx的n個特征向量；

(2) 取這n個特征向量的前k-1維，并將其標準化；

(3) 標準化的k-1維特征向量代表原始網絡中的節點。

2.3 基于RangRank的聚類算法

設相似度閾值的集合為A=(A1,A2,…,An)，令M0=0,i=1，初始的社團劃分記為U。基于PageRank的聚類算法記為PFCM，算法具體流程如圖1所示。

3 實驗

選取2個真實的網絡數據Karate和Football來驗證PFCM算法的高效性，表1列出了真實網絡的數據。

表1 真實網絡的節點與邊

3.1 Karate網絡

對Karate網絡數據進行PFCM算法社團劃分，不同社團數量所對應得最大最小模塊度值如圖2所示。

圖2 Karate網絡不同社團數量對應的最大最小模塊度值

圖2橫坐標是社團的數量，縱坐標是最大最小模塊度值。從圖2中可以看出最大的最大最小模塊度所對應的社團的數量是2，這與Karate網絡的真實社團劃分相符。

應用標準互信息(NMI)、精確度(precision)、召回率(Re-call)和蘭德指數(RI)這4個評價指標，對FCM和PFCM算法的社團劃分結果進行評價，如表2所示。PFCM算法除Precision外，在其他3個指標(NMI、Recall、RI)上均優于FCM算法，而Precision值兩算法的結果相差不大。FCM算法對Karate網絡進行100次實驗所得結果的NMI的平均值為0.033，社團劃分結果很不理想。PFCM算法結果的Recall較FCM算法提升了40.4%，RI提升了40.9%。從上述結果綜合來看，PFCM算法優于FCM算法。

表2 Karate網絡數據聚類效果評價指標對比

3.2 Football網絡

對Football網絡數據進行PFCM算法社團劃分，不同社團數量所對應得最大最小模塊度值如圖3所示。

圖3 Football網絡不同社團數量對應的最大最小模塊度值

由圖3可以看出，最大的最大最小模塊度值所對應的社團的數量是13。表3列舉了4種不同的評價標準對FCM算法和PFCM算法在Football網絡上實驗所得結果的對比，FCM算法的4個評價指標是100次實驗結果的平均值。

表3 Football網絡數據聚類效果評價指標對比

由表4可以看出，PFCM算法結果的NMI較FCM算法提升了34.6%，Precision提升了12.8%，Recall 提升了100%，RI提升了8.06%。

3.3 算法穩定性對比分析

PFCM算法和FCM算法在真實網絡Karate和Football上進行了100次實驗。圖4展示了前5次實驗的結果(100次實驗結果呈現的趨勢與前五次類似，為了展示方便圖中只展示了前五次的結果)，2個子圖的橫坐標表示算法進行實驗的次數，縱坐標表示的是標準互信息(NMI)的值。

圖4中的紅色的線是PFCM算法的實驗結果，實驗結果非常穩定。藍色的線是FCM算法的實驗結果，不同次實驗得到的NMI的值不同，波動非常大，實驗結果的精確度具有隨機性。同時PFCM算法實驗結果的NMI值普遍要高于由FCM算法的NMI值。這驗證了PFCM算法不僅解決了FCM算法的實驗結果受初始的種子節點的影響的缺點，而且算法的精確度高。

圖4 PFCM算法和FCM算法的比較

4 總結

本文提出了一種改進的FCM算法(記為PFCM)，解決了傳統FCM算法受初始種子節點和需要事先給定網絡社團個數的問題。引入PageRank和最大最小模塊度確定網絡最優社團數量，利用譜映射方法將網絡鄰接矩陣轉換為向量空間上的數據，進而執行FCM算法實現網絡社團劃分。在真實網絡上的數值實驗表明，PFCM算法在準確性與穩定性上都有了明顯提升。