基于PageRank模糊聚類的網(wǎng)絡(luò)社團(tuán)挖掘

馬麗娜

(西安財(cái)經(jīng)大學(xué)行知學(xué)院，經(jīng)濟(jì)與統(tǒng)計(jì)學(xué)院， 陜西,西安 710038)

0 引言

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

1 相關(guān)理論

1.1 模糊C均值聚類

(1)

其中，m為控制模糊劃分的權(quán)重參數(shù)，一般設(shè)為2,dik為數(shù)據(jù)xi到簇k的歐式距離。

(2)

(3)

不斷更新每個(gè)簇的簇中心vk(k=1,2,…,C)和隸屬度矩陣U，使得目標(biāo)函數(shù)達(dá)到最小，可得到最優(yōu)劃分。

1.2 網(wǎng)絡(luò)重要度和模塊度

PageRank是一種常用的網(wǎng)絡(luò)重要性度量，計(jì)算式為

(4)

其中,Na為所有指向a的網(wǎng)頁(yè)的集合，Kb為網(wǎng)頁(yè)b指向的網(wǎng)頁(yè)個(gè)數(shù)。

最大最小模塊度是一種常用的衡量網(wǎng)絡(luò)社團(tuán)劃分準(zhǔn)確率的指標(biāo)，其定義如：

Qmax-min=Qmax-Qmin=

(5)

其中

(6)

Cx表示節(jié)點(diǎn)x所在的社團(tuán)

(7)

(8)

(9)

模塊度函數(shù)值越大，對(duì)應(yīng)的社團(tuán)劃分結(jié)果與網(wǎng)絡(luò)真實(shí)的社團(tuán)結(jié)構(gòu)越接近。

2 基于RangRank的聚類社團(tuán)挖掘

2.1 網(wǎng)絡(luò)初始種子選取

將復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)看成網(wǎng)頁(yè)，那么節(jié)點(diǎn)的重要性就相當(dāng)于節(jié)點(diǎn)所對(duì)應(yīng)的PageRank值的大小。但種子節(jié)點(diǎn)的選擇不僅要看節(jié)點(diǎn)的PageRank值，還要依據(jù)節(jié)點(diǎn)之間的差異性。節(jié)點(diǎn)之間的相似性定義為

(10)

其中，nij為節(jié)點(diǎn)i和節(jié)點(diǎn)j的公共節(jié)點(diǎn)數(shù)，ki、kj分別為節(jié)點(diǎn)i和節(jié)點(diǎn)j的度。

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

2.2 譜映射

設(shè)網(wǎng)絡(luò)的鄰接矩陣為

A=(aij)n×n

(11)

其中，當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j相連時(shí)，aij=1；否則，aij=0。記對(duì)角矩陣為

D=(dii)

(12)

其中，dii=∑aik表示與節(jié)點(diǎn)i相連的節(jié)點(diǎn)數(shù)量。譜映射的數(shù)據(jù)轉(zhuǎn)換過(guò)程如下：

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

(2) 取這n個(gè)特征向量的前k-1維，并將其標(biāo)準(zhǔn)化；

(3) 標(biāo)準(zhǔn)化的k-1維特征向量代表原始網(wǎng)絡(luò)中的節(jié)點(diǎn)。

2.3 基于RangRank的聚類算法

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

3 實(shí)驗(yàn)

選取2個(gè)真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)Karate和Football來(lái)驗(yàn)證PFCM算法的高效性，表1列出了真實(shí)網(wǎng)絡(luò)的數(shù)據(jù)。

表1 真實(shí)網(wǎng)絡(luò)的節(jié)點(diǎn)與邊

3.1 Karate網(wǎng)絡(luò)

對(duì)Karate網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行PFCM算法社團(tuán)劃分，不同社團(tuán)數(shù)量所對(duì)應(yīng)得最大最小模塊度值如圖2所示。

圖2 Karate網(wǎng)絡(luò)不同社團(tuán)數(shù)量對(duì)應(yīng)的最大最小模塊度值

圖2橫坐標(biāo)是社團(tuán)的數(shù)量，縱坐標(biāo)是最大最小模塊度值。從圖2中可以看出最大的最大最小模塊度所對(duì)應(yīng)的社團(tuán)的數(shù)量是2，這與Karate網(wǎng)絡(luò)的真實(shí)社團(tuán)劃分相符。

應(yīng)用標(biāo)準(zhǔn)互信息(NMI)、精確度(precision)、召回率(Re-call)和蘭德指數(shù)(RI)這4個(gè)評(píng)價(jià)指標(biāo)，對(duì)FCM和PFCM算法的社團(tuán)劃分結(jié)果進(jìn)行評(píng)價(jià)，如表2所示。PFCM算法除Precision外，在其他3個(gè)指標(biāo)(NMI、Recall、RI)上均優(yōu)于FCM算法，而Precision值兩算法的結(jié)果相差不大。FCM算法對(duì)Karate網(wǎng)絡(luò)進(jìn)行100次實(shí)驗(yàn)所得結(jié)果的NMI的平均值為0.033，社團(tuán)劃分結(jié)果很不理想。PFCM算法結(jié)果的Recall較FCM算法提升了40.4%，RI提升了40.9%。從上述結(jié)果綜合來(lái)看，PFCM算法優(yōu)于FCM算法。

表2 Karate網(wǎng)絡(luò)數(shù)據(jù)聚類效果評(píng)價(jià)指標(biāo)對(duì)比

3.2 Football網(wǎng)絡(luò)

對(duì)Football網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行PFCM算法社團(tuán)劃分，不同社團(tuán)數(shù)量所對(duì)應(yīng)得最大最小模塊度值如圖3所示。

圖3 Football網(wǎng)絡(luò)不同社團(tuán)數(shù)量對(duì)應(yīng)的最大最小模塊度值

由圖3可以看出，最大的最大最小模塊度值所對(duì)應(yīng)的社團(tuán)的數(shù)量是13。表3列舉了4種不同的評(píng)價(jià)標(biāo)準(zhǔn)對(duì)FCM算法和PFCM算法在Football網(wǎng)絡(luò)上實(shí)驗(yàn)所得結(jié)果的對(duì)比，F(xiàn)CM算法的4個(gè)評(píng)價(jià)指標(biāo)是100次實(shí)驗(yàn)結(jié)果的平均值。

表3 Football網(wǎng)絡(luò)數(shù)據(jù)聚類效果評(píng)價(jià)指標(biāo)對(duì)比

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

3.3 算法穩(wěn)定性對(duì)比分析

PFCM算法和FCM算法在真實(shí)網(wǎng)絡(luò)Karate和Football上進(jìn)行了100次實(shí)驗(yàn)。圖4展示了前5次實(shí)驗(yàn)的結(jié)果(100次實(shí)驗(yàn)結(jié)果呈現(xiàn)的趨勢(shì)與前五次類似，為了展示方便圖中只展示了前五次的結(jié)果)，2個(gè)子圖的橫坐標(biāo)表示算法進(jìn)行實(shí)驗(yàn)的次數(shù)，縱坐標(biāo)表示的是標(biāo)準(zhǔn)互信息(NMI)的值。

圖4中的紅色的線是PFCM算法的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果非常穩(wěn)定。藍(lán)色的線是FCM算法的實(shí)驗(yàn)結(jié)果，不同次實(shí)驗(yàn)得到的NMI的值不同，波動(dòng)非常大，實(shí)驗(yàn)結(jié)果的精確度具有隨機(jī)性。同時(shí)PFCM算法實(shí)驗(yàn)結(jié)果的NMI值普遍要高于由FCM算法的NMI值。這驗(yàn)證了PFCM算法不僅解決了FCM算法的實(shí)驗(yàn)結(jié)果受初始的種子節(jié)點(diǎn)的影響的缺點(diǎn)，而且算法的精確度高。

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

4 總結(jié)

本文提出了一種改進(jìn)的FCM算法(記為PFCM)，解決了傳統(tǒng)FCM算法受初始種子節(jié)點(diǎn)和需要事先給定網(wǎng)絡(luò)社團(tuán)個(gè)數(shù)的問(wèn)題。引入PageRank和最大最小模塊度確定網(wǎng)絡(luò)最優(yōu)社團(tuán)數(shù)量，利用譜映射方法將網(wǎng)絡(luò)鄰接矩陣轉(zhuǎn)換為向量空間上的數(shù)據(jù)，進(jìn)而執(zhí)行FCM算法實(shí)現(xiàn)網(wǎng)絡(luò)社團(tuán)劃分。在真實(shí)網(wǎng)絡(luò)上的數(shù)值實(shí)驗(yàn)表明，PFCM算法在準(zhǔn)確性與穩(wěn)定性上都有了明顯提升。