基于超圖和K-means改進(jìn)的異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

趙宇紅 張曉楠(內(nèi)蒙古科技大學(xué)信息工程學(xué)院 內(nèi)蒙古 包頭 014010)

0 引 言

信息網(wǎng)絡(luò)是對(duì)復(fù)雜關(guān)聯(lián)系統(tǒng)的抽象概括，表達(dá)了系統(tǒng)中的實(shí)體及實(shí)體間的關(guān)系。信息網(wǎng)絡(luò)的實(shí)例包括社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)和生物網(wǎng)絡(luò)等。挖掘信息網(wǎng)絡(luò)的結(jié)構(gòu)特性、演化規(guī)則和實(shí)體特征對(duì)于理解和應(yīng)用信息網(wǎng)絡(luò)有著重要意義。

信息網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)研究[1-2]就是挖掘和發(fā)現(xiàn)關(guān)聯(lián)緊密的實(shí)體群組，準(zhǔn)確的社區(qū)發(fā)現(xiàn)既可以幫助人類(lèi)了解網(wǎng)絡(luò)結(jié)構(gòu)的演化規(guī)則，也可以發(fā)現(xiàn)個(gè)體特征在群組形成中的作用，社區(qū)發(fā)現(xiàn)可以支持網(wǎng)絡(luò)分析、用戶(hù)管理、面向群組的網(wǎng)絡(luò)應(yīng)用。例如，廣告投放、商品推薦和輿情監(jiān)測(cè)都是社區(qū)發(fā)現(xiàn)的典型應(yīng)用。大多數(shù)社區(qū)發(fā)現(xiàn)算法的研究，都是在同質(zhì)網(wǎng)絡(luò)中展開(kāi)的，即將網(wǎng)絡(luò)中所有節(jié)點(diǎn)和節(jié)點(diǎn)間的連接都定義為同一種類(lèi)型。基于同質(zhì)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)研究可挖掘潛在的群組結(jié)構(gòu)，也實(shí)現(xiàn)了眾多有重要影響的應(yīng)用。然而，實(shí)際生活中大多數(shù)網(wǎng)絡(luò)都是異質(zhì)的，近些年，異質(zhì)網(wǎng)絡(luò)[3]這一概念受到很多關(guān)注。異質(zhì)網(wǎng)絡(luò)與實(shí)際網(wǎng)絡(luò)相符合，節(jié)點(diǎn)及節(jié)點(diǎn)間的關(guān)系是多種類(lèi)型的，這種多類(lèi)型的節(jié)點(diǎn)和連接關(guān)系使網(wǎng)絡(luò)變得異常復(fù)雜，如何能夠準(zhǔn)確且全面地度量多類(lèi)型節(jié)點(diǎn)以及節(jié)點(diǎn)之間錯(cuò)綜復(fù)雜的多種關(guān)聯(lián)，異質(zhì)網(wǎng)絡(luò)的提出給社區(qū)發(fā)現(xiàn)研究帶來(lái)了巨大挑戰(zhàn)。本文提出一種適用于異質(zhì)網(wǎng)絡(luò)，邏輯清晰、復(fù)雜度低且具有高準(zhǔn)確度的社區(qū)發(fā)現(xiàn)算法。

算法首先使用超圖[4]數(shù)據(jù)模型對(duì)異質(zhì)信息網(wǎng)絡(luò)進(jìn)行建模，利用網(wǎng)絡(luò)表示學(xué)習(xí)方法DeepWalk算法[5]對(duì)異質(zhì)信息網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行訓(xùn)練學(xué)習(xí)，得到節(jié)點(diǎn)的低維向量化表示。另外，針對(duì)K-means[6]聚類(lèi)中心隨機(jī)選取容易造成社區(qū)劃分結(jié)果不穩(wěn)定，即聚類(lèi)中心的敏感性問(wèn)題，提出一種新的聚類(lèi)中心選取方法，基于DeepWalk所獲得的節(jié)點(diǎn)向量信息重新定義了節(jié)點(diǎn)間距離度量，結(jié)合改進(jìn)的K-means算法實(shí)現(xiàn)了異質(zhì)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)，本文提出的基于超圖和DeepWalk改進(jìn)的K-means算法，簡(jiǎn)稱(chēng)為HD-K-means算法，算法在仿真實(shí)驗(yàn)中效果良好。

1 社區(qū)發(fā)現(xiàn)方法

Girvan等[7]提出了GN算法，利用邊界數(shù)對(duì)社區(qū)進(jìn)行劃分。GN算法是一個(gè)有效的社區(qū)發(fā)現(xiàn)算法，但算法的復(fù)雜度較高。接著Gregory[8]提出了一種基于GN的改進(jìn)算法CONGA，降低了算法的復(fù)雜度。之后，許多學(xué)者又相繼提出了K-means、HLCD[9]和基于邊緣加權(quán)[10]等社區(qū)發(fā)現(xiàn)算法，但這些算法都是基于同質(zhì)信息網(wǎng)絡(luò)結(jié)構(gòu)的。

近年來(lái)，一些基于異質(zhì)信息網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法相繼被提出。其中主成分分析(Principal Component Analysis，PCA)[11]是一種具有代表性的異質(zhì)信息網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法。PCA通過(guò)降維把各維度數(shù)據(jù)進(jìn)行線性無(wú)關(guān)的表示，繼而對(duì)主要的數(shù)據(jù)特征進(jìn)行提取，實(shí)現(xiàn)社區(qū)劃分。PCA具有無(wú)監(jiān)督性，在計(jì)算過(guò)程中無(wú)法使用類(lèi)別先驗(yàn)知識(shí)。之后，一種有監(jiān)督性的社區(qū)發(fā)現(xiàn)方法線性判別分析(Linear Discriminant Analysis，LDA)[12]被提出，在該算法中，LDA將數(shù)據(jù)在低維向量進(jìn)行投影，利用投影后的數(shù)據(jù)更容易被區(qū)分這一特點(diǎn)來(lái)達(dá)到社區(qū)劃分的目的。然而，通過(guò)PCA和LDA劃分出來(lái)的數(shù)據(jù)有正有負(fù)，在現(xiàn)實(shí)世界里，負(fù)數(shù)值的存在沒(méi)有實(shí)際的意義。針對(duì)這一問(wèn)題，非負(fù)矩陣分解算法(Non-negative Matrix Factorization，NMF)[13]被提出，算法將一個(gè)非負(fù)的原始矩陣分解成兩個(gè)非負(fù)矩陣相乘的形式來(lái)達(dá)到社區(qū)劃分的目的。

然而，大多數(shù)基于異質(zhì)信息網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法往往存在過(guò)程復(fù)雜、不易理解、復(fù)雜度高等問(wèn)題。一些基于同質(zhì)信息網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法，如K-means算法，具有邏輯簡(jiǎn)單、便于理解且易實(shí)現(xiàn)的特點(diǎn)。但是傳統(tǒng)的K-means算法本身存在聚類(lèi)中心選取隨機(jī)性的問(wèn)題，且是基于同質(zhì)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)的。本文提出一種基于超圖和DeepWalk改進(jìn)的K-means異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法HD-K-means，該算法繼承了傳統(tǒng)K-means算法簡(jiǎn)單高效的特點(diǎn)，改進(jìn)了K-means的聚類(lèi)中心隨機(jī)選取問(wèn)題，同時(shí)也考慮了異質(zhì)網(wǎng)絡(luò)的多類(lèi)型節(jié)點(diǎn)及關(guān)系。

2 算法設(shè)計(jì)

2.1 傳統(tǒng)的K-means算法

聚類(lèi)是社區(qū)發(fā)現(xiàn)算法中一種重要且常用的方法。作為一種經(jīng)典的聚類(lèi)算法，K-means原理簡(jiǎn)單，易于實(shí)現(xiàn)，且復(fù)雜度低。K-means算法通過(guò)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行聚類(lèi)來(lái)挖掘節(jié)點(diǎn)之間潛在的關(guān)系。其主要的思想如下：

(1) 隨機(jī)選取K個(gè)初始聚類(lèi)中心，生成對(duì)應(yīng)的K個(gè)簇。

(2) 遍歷所有節(jié)點(diǎn)，依據(jù)“距離”實(shí)現(xiàn)相似度度量，將每個(gè)節(jié)點(diǎn)劃分到“最近的”聚類(lèi)中心所在的簇。

(3) 更新聚類(lèi)中心為每簇的均值。

(4) 重復(fù)步驟(2)-步驟(3)，直到K個(gè)簇的中心點(diǎn)不再變化，或者達(dá)到預(yù)設(shè)的迭代次數(shù)為止。

在傳統(tǒng)的K-means算法中，聚類(lèi)中心是隨機(jī)選取的，這造成了極大敏感性，極易使得聚類(lèi)結(jié)果陷入局部最優(yōu)解。此外，K值的選取也是一個(gè)非常重要的問(wèn)題。

2.2 HD-K-means算法的基本思想

傳統(tǒng)的K-means算法是一種基于同質(zhì)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法，網(wǎng)絡(luò)中的節(jié)點(diǎn)都是由二維向量來(lái)表示的。通過(guò)歐氏距離來(lái)計(jì)算節(jié)點(diǎn)間的距離，衡量節(jié)點(diǎn)間的相似度，進(jìn)而實(shí)現(xiàn)聚類(lèi)。基于同質(zhì)網(wǎng)絡(luò)的節(jié)點(diǎn)向量表示忽略節(jié)點(diǎn)的類(lèi)型和節(jié)點(diǎn)之間可能存在的復(fù)雜關(guān)系這一實(shí)際情況，針對(duì)這一問(wèn)題，本文提出一種基于超圖建模的方法，利用超圖表示不同類(lèi)型節(jié)點(diǎn)間的復(fù)雜關(guān)系，之后通過(guò)DeepWalk算法實(shí)現(xiàn)對(duì)異質(zhì)網(wǎng)絡(luò)中的節(jié)點(diǎn)向量表示學(xué)習(xí)，得到更加準(zhǔn)確的節(jié)點(diǎn)向量低維表示，使節(jié)點(diǎn)間的距離度量(即相似度)更加準(zhǔn)確。

在K-means算法中聚類(lèi)中心的選取對(duì)于整個(gè)聚類(lèi)結(jié)果的好壞起著至關(guān)重要的作用，即聚類(lèi)中心敏感性問(wèn)題。可能由于選取的聚類(lèi)中心不同，最后得到的社區(qū)劃分的結(jié)果也不同，本文針對(duì)K-means算法的這一不足，提出一種新的聚類(lèi)中心選取方法。一種基于密度基尼系數(shù)的選取方法。HD-K-means算法流程如圖1所示。算法首先利用超圖建模，通過(guò)DeepWalk算法在異質(zhì)信息網(wǎng)絡(luò)下得到節(jié)點(diǎn)的向量表示，基于密度基尼系數(shù)選取聚類(lèi)中心，利用Skip-gram模型訓(xùn)練學(xué)習(xí)所獲得的節(jié)點(diǎn)向量計(jì)算節(jié)點(diǎn)距離(即相似度)完成聚類(lèi)，最終得到社區(qū)發(fā)現(xiàn)結(jié)果。

2.2.1基于超圖和DeepWalk的異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)

網(wǎng)絡(luò)表示學(xué)習(xí)(Network Representation Learning,NRL)[14]也被稱(chēng)為圖嵌入法(Graph Embedding Method,GEM)，旨在將網(wǎng)絡(luò)中的節(jié)點(diǎn)表示成低維、稠密的向量形式，該形式可以在向量空間中具有表示以及推理能力，進(jìn)而可將得到的向量表示運(yùn)用到社區(qū)發(fā)現(xiàn)、鏈路預(yù)測(cè)、可視化分類(lèi)，以及節(jié)點(diǎn)分類(lèi)等任務(wù)中。Word2vec[15]在自然語(yǔ)言處理中，將關(guān)聯(lián)的上下文詞信息經(jīng)訓(xùn)練學(xué)習(xí)表示為低維詞向量形式，詞向量應(yīng)用于情感分析、翻譯及語(yǔ)言學(xué)中，且取得了顯著的效果。基于這個(gè)思想，在網(wǎng)絡(luò)空間模型中，DeepWalk 算法被提出，該算法把網(wǎng)絡(luò)中的節(jié)點(diǎn)表示為自然語(yǔ)言中的單詞。把節(jié)點(diǎn)生成的序列看作是自然語(yǔ)言模型中的句子，在深度學(xué)習(xí)的基礎(chǔ)上將異質(zhì)信息網(wǎng)絡(luò)中的節(jié)點(diǎn)表示成低維的向量形式。

本文使用網(wǎng)絡(luò)表示學(xué)習(xí)中的DeepWalk算法實(shí)現(xiàn)對(duì)節(jié)點(diǎn)的低維向量表示。DeepWalk算法首先通過(guò)隨機(jī)游走生成一個(gè)游走序列，再基于Skip-gram模型進(jìn)行節(jié)點(diǎn)序列訓(xùn)練，輸出節(jié)點(diǎn)的低維向量表示。

但是DeepWalk算法是基于同質(zhì)網(wǎng)絡(luò)結(jié)構(gòu)的，為了能夠使該算法全面學(xué)習(xí)異質(zhì)網(wǎng)絡(luò)中的節(jié)點(diǎn)與節(jié)點(diǎn)的關(guān)聯(lián)信息，引入超圖實(shí)現(xiàn)對(duì)異質(zhì)信息網(wǎng)絡(luò)的建模，在超圖中嵌入DeepWalk算法完成對(duì)異質(zhì)信息網(wǎng)絡(luò)的表示學(xué)習(xí)。

(1) 基于超圖的深度隨機(jī)游走。超圖，可以把不同類(lèi)型的節(jié)點(diǎn)、不同語(yǔ)義的邊表達(dá)在一個(gè)網(wǎng)絡(luò)中，從而來(lái)表示異質(zhì)信息網(wǎng)絡(luò)中的多類(lèi)型節(jié)點(diǎn)及復(fù)雜關(guān)系。超圖由超邊集和節(jié)點(diǎn)集構(gòu)成，一條超邊包含多個(gè)節(jié)點(diǎn)，超圖的超邊異質(zhì)性和節(jié)點(diǎn)的多樣性，可以更全面地呈現(xiàn)網(wǎng)絡(luò)中的復(fù)雜關(guān)系，有助于支持更豐富的網(wǎng)絡(luò)結(jié)構(gòu)信息的挖掘。

超圖的結(jié)構(gòu)如圖2所示。

圖2 超圖的結(jié)構(gòu)

首先，利用超圖對(duì)異質(zhì)信息網(wǎng)絡(luò)進(jìn)行建模。在異質(zhì)信息網(wǎng)絡(luò)中，通過(guò)異質(zhì)網(wǎng)絡(luò)中復(fù)雜的節(jié)點(diǎn)關(guān)系進(jìn)行隨機(jī)游走，在給定當(dāng)前根節(jié)點(diǎn)v的情況下，首先隨機(jī)選取一個(gè)與v相關(guān)的超邊e，然后隨機(jī)地選取下一個(gè)節(jié)點(diǎn)vx∈e，最終得到步長(zhǎng)為l的節(jié)點(diǎn)序列ωv。傳統(tǒng)DeepWalk算法中，網(wǎng)絡(luò)中的節(jié)點(diǎn)是基于等概率隨機(jī)游走得到游走序列，但實(shí)際網(wǎng)絡(luò)中關(guān)系越緊密的兩個(gè)節(jié)點(diǎn)之間應(yīng)該有更高的轉(zhuǎn)移概率，通過(guò)轉(zhuǎn)移概率得到下一個(gè)可能游走到的節(jié)點(diǎn)。模型的轉(zhuǎn)移概率可以通過(guò)式(1)進(jìn)行計(jì)算。

(1)

最終，節(jié)點(diǎn)v在進(jìn)行γ次游走之后，得到γ個(gè)深度隨機(jī)游走序列。將隨機(jī)游走序列、滑動(dòng)窗口大小c作為Skip-gram模型的輸入進(jìn)行節(jié)點(diǎn)訓(xùn)練，得到節(jié)點(diǎn)的向量表示φ。

(2) Skip-gram模型。Skip-gram模型包括輸入層、映射層和輸出層。它通過(guò)一個(gè)改進(jìn)的神經(jīng)網(wǎng)絡(luò)模型進(jìn)行節(jié)點(diǎn)向量的訓(xùn)練。該模型結(jié)構(gòu)如圖3所示。

圖3 Skip-gram模型結(jié)構(gòu)

Skip-gram模型是一種語(yǔ)言模型，它可以在已知中心詞的情況下，預(yù)測(cè)其所在句子的上下文。引入Skip-gram模型可以通過(guò)某個(gè)節(jié)點(diǎn)和其所在的節(jié)點(diǎn)序列來(lái)預(yù)測(cè)該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。圖3中，ω(t)表示當(dāng)前輸入節(jié)點(diǎn)，與傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)模型相比所不同的是，輸入節(jié)點(diǎn)不是標(biāo)量值，而是一個(gè)向量，即不只表示大小，還表示方向，使用one-hot的形式表示。在映射層中，Skip-gram將所有輸入的節(jié)點(diǎn)的累計(jì)作為一個(gè)向量，投影到輸出層。輸出層為中間節(jié)點(diǎn)上下鄰居節(jié)點(diǎn)向量。

經(jīng)過(guò)Skip-gram模型學(xué)習(xí)輸出的低維節(jié)點(diǎn)向量，是以超圖深度游走的游走序列的輸入訓(xùn)練所獲取的，游走序列中獲取節(jié)點(diǎn)的順序表達(dá)了節(jié)點(diǎn)間的關(guān)聯(lián)程度，在深度學(xué)習(xí)下，更精確地表示了異質(zhì)網(wǎng)絡(luò)節(jié)點(diǎn)的信息，從而也提高了本文提出的HD-K-means算法中節(jié)點(diǎn)間距離度量(即相似度)結(jié)果的準(zhǔn)確性。

2.2.2聚類(lèi)中心的選取

通常作為聚類(lèi)中心的點(diǎn)應(yīng)具有如下特征：(1) 密度往往比與其相鄰的其他節(jié)點(diǎn)的密度大；(2) 各個(gè)聚類(lèi)中心之間相距往往較遠(yuǎn)。基于聚類(lèi)中心的這兩個(gè)特點(diǎn)，本文提出一種基于密度基尼系數(shù)的聚類(lèi)中心的選取方法。

輸入：節(jié)點(diǎn)集X={x1,x2,…,xn}(n是節(jié)點(diǎn)的數(shù)量)，社區(qū)個(gè)數(shù)為K。

輸出：劃分好的K個(gè)社區(qū)。

(1) 首先計(jì)算節(jié)點(diǎn)集X中的任意節(jié)點(diǎn)xi的局部密度ρxi。以xi點(diǎn)為圓心，dc為半徑，ρxi的計(jì)算式表示為：

(2)

(3)

式中：χ(x)是密度基尼系數(shù)估計(jì)的函數(shù)；dij表示節(jié)點(diǎn)xi到節(jié)點(diǎn)xj的距離，xi和xj是節(jié)點(diǎn)集X中的任意兩個(gè)節(jié)點(diǎn)。ρxi的值越大，說(shuō)明節(jié)點(diǎn)xi的密度越大，通過(guò)計(jì)算得到密度最大的節(jié)點(diǎn)xi作為第一個(gè)聚類(lèi)中心。

(2) 通過(guò)計(jì)算其他剩余節(jié)點(diǎn)到第一個(gè)聚類(lèi)中心的距離，距離最大的節(jié)點(diǎn)即為第二個(gè)聚類(lèi)中心，再重新計(jì)算剩余節(jié)點(diǎn)到第一個(gè)聚類(lèi)中心和第二個(gè)聚類(lèi)中心的距離，距離最大節(jié)點(diǎn)為第三個(gè)聚類(lèi)中心。依次計(jì)算，直到選出K個(gè)初始聚類(lèi)中心。

(3) 將網(wǎng)絡(luò)中的節(jié)點(diǎn)根據(jù)距離(即相似度)進(jìn)行聚類(lèi)，最終得到K個(gè)社區(qū)劃分結(jié)果。

基于超圖利用DeepWalk算法獲得異質(zhì)信息網(wǎng)絡(luò)中節(jié)點(diǎn)的向量表示，假定φ(xi)=[xi1xi2…xid]表示節(jié)點(diǎn)集X中任意節(jié)點(diǎn)xi的向量，d表示輸出維度。本文使用歐氏距離來(lái)度量節(jié)點(diǎn)間的距離,計(jì)算式表示為：

(4)

本文提出的聚類(lèi)中心選取方法，根據(jù)定義的節(jié)點(diǎn)密度，對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行密度排序，依據(jù)節(jié)點(diǎn)密度值的大小選取初始聚類(lèi)中心，解決了聚類(lèi)中心的選取敏感性，消除局部最優(yōu)解問(wèn)題，從而使得社區(qū)劃分更為穩(wěn)定、準(zhǔn)確。

2.3 參數(shù)的取值

DeepWalk算法參數(shù)的取值：窗口大小c=5；以每個(gè)節(jié)點(diǎn)開(kāi)始的路徑數(shù)量γ=10；每條路徑的長(zhǎng)度l=40；輸出維度d=64。

半徑dc的取值:基尼系數(shù)[16]是關(guān)于系統(tǒng)不確定性的度量，基尼系數(shù)越大，說(shuō)明系統(tǒng)的不確定性越大；反之，說(shuō)明系統(tǒng)的不確定性越小。基尼系數(shù)計(jì)算式表示為：

(5)

式中：n指節(jié)點(diǎn)的總數(shù)量；Pi指第i類(lèi)節(jié)點(diǎn)的數(shù)量占總數(shù)量節(jié)點(diǎn)的比例。半徑dc的設(shè)置定義了局部結(jié)構(gòu)范圍，也影響了節(jié)點(diǎn)的密度。如果dc的值過(guò)大，會(huì)導(dǎo)致關(guān)聯(lián)不緊密的節(jié)點(diǎn)也聚類(lèi)在一個(gè)簇中，如果dc的值過(guò)小，則會(huì)導(dǎo)致一個(gè)簇的分裂，這種隨機(jī)性決定了半徑dc也是一個(gè)不確定性的度量，因此，引入基尼系數(shù)解決半徑dc的合理設(shè)置問(wèn)題。給定n個(gè)節(jié)點(diǎn)的局部密度估計(jì)ρ1,ρ2,…,ρn。如果節(jié)點(diǎn)的局部密度值越小，則說(shuō)明節(jié)點(diǎn)分布的不確定性越大，具有最大基尼系數(shù)。由此可以引入密度基尼系數(shù)衡量節(jié)點(diǎn)局部密度估計(jì)聚類(lèi)中心選取的合理性，密度基尼系數(shù)用H表示。H和Q的計(jì)算式分別表示為：

(6)

(7)

式中：參數(shù)Q指的是n個(gè)節(jié)點(diǎn)的總密度。通過(guò)式(6)分析參數(shù)半徑dc不斷增大密度基尼系數(shù)H的變化，當(dāng)H最大時(shí)所對(duì)應(yīng)的dc即為最佳的局部密度計(jì)算所設(shè)定的半徑值。

社區(qū)數(shù)K的取值：傳統(tǒng)的K-means算法中K值的計(jì)算是一個(gè)非常經(jīng)典的問(wèn)題，有不少學(xué)者就此問(wèn)題給出了很多解決方案[17-18]。本文采用Elbow method即肘方法[18]。對(duì)于n個(gè)節(jié)點(diǎn)的數(shù)據(jù)集，迭代計(jì)算K的值從1取到n。在每次社區(qū)劃分結(jié)束之后，計(jì)算其他節(jié)點(diǎn)到簇心的距離的平方和，當(dāng)K值不斷增加，距離的平方和就逐漸減少，節(jié)點(diǎn)的聚類(lèi)會(huì)更加準(zhǔn)確，每個(gè)簇的內(nèi)部聚合程度會(huì)逐漸提高，距離的平方和自然會(huì)逐漸減小。當(dāng)K值小于最佳聚類(lèi)數(shù)時(shí)，隨著K的增大會(huì)大幅度增加每個(gè)簇的聚合程度，所以距離的平方和下降的速度比較快；當(dāng)K達(dá)到最佳的聚類(lèi)數(shù)時(shí)，再增加K值聚合程度會(huì)迅速變小，距離的平方和下降幅度會(huì)驟減，然后隨著K值的繼續(xù)增大趨于平緩。所以我們根據(jù)距離平方和和K值得到一個(gè)手肘形狀的關(guān)系圖，而這個(gè)“肘”點(diǎn)對(duì)應(yīng)的K值即為最佳的聚類(lèi)數(shù)。

3 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)環(huán)境以及平臺(tái)是Intel(R) Core(TM)i7-8700處理器、32 GB內(nèi)存。運(yùn)行環(huán)境為Python3.7。

3.1 相關(guān)數(shù)據(jù)集的介紹

該實(shí)驗(yàn)在兩個(gè)真實(shí)的異質(zhì)信息網(wǎng)絡(luò)數(shù)據(jù)集下面進(jìn)行有效驗(yàn)證，數(shù)據(jù)集的詳細(xì)介紹如下。

DBLP數(shù)據(jù)集：一個(gè)作者合作網(wǎng)絡(luò),網(wǎng)絡(luò)中包含作者、論文、類(lèi)型和會(huì)議四種類(lèi)型的節(jié)點(diǎn)，不同類(lèi)型節(jié)點(diǎn)之間包含不同的連接關(guān)系。

Aminer數(shù)據(jù)集:一個(gè)作者合作網(wǎng)絡(luò)數(shù)據(jù)集，網(wǎng)絡(luò)中包含四種類(lèi)型的節(jié)點(diǎn)。與DBLP不同的是，這四種類(lèi)型的節(jié)點(diǎn)分別是作者、論文、會(huì)議和參考。節(jié)點(diǎn)之間通過(guò)潛在的關(guān)系進(jìn)行連接。數(shù)據(jù)集的統(tǒng)計(jì)情況如表1所示，其中：n代表數(shù)據(jù)集中的節(jié)點(diǎn)數(shù)；e代表節(jié)點(diǎn)之間的連邊數(shù)；K代表社區(qū)數(shù)。

表1 數(shù)據(jù)集參數(shù)

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

使用準(zhǔn)確率precision和標(biāo)準(zhǔn)化互信息NMI作為評(píng)價(jià)指標(biāo)。準(zhǔn)確率precision可以作如下定義：在給定的數(shù)據(jù)集中，劃分正確的節(jié)點(diǎn)數(shù)據(jù)與總節(jié)點(diǎn)數(shù)據(jù)的比值。計(jì)算式表示為：

(8)

式中：對(duì)于函數(shù)ζ(x,y)，如果x=y，函數(shù)值為1，否則，其值為0；對(duì)于任意的節(jié)點(diǎn)i，lpi為通過(guò)社區(qū)劃分算法得到的結(jié)果，lti為節(jié)點(diǎn)i實(shí)際所歸屬的社區(qū)；n表示總的節(jié)點(diǎn)個(gè)數(shù)。準(zhǔn)確率的值越大，說(shuō)明社區(qū)劃分的結(jié)果越準(zhǔn)確。

標(biāo)準(zhǔn)化互信息(Normalized Mutual Information,NMI)用于衡量社區(qū)劃分結(jié)果的準(zhǔn)確度，取值在0到1之間，NMI計(jì)算式表示為：

(9)

3.3 實(shí)驗(yàn)驗(yàn)證

3.3.1基于密度基尼系數(shù)半徑dc的設(shè)置驗(yàn)證

半徑dc的設(shè)置直接影響到初始聚類(lèi)中心的選擇。為克服dc的不確定性，提出一種基于密度基尼系數(shù)的算法。仿真實(shí)驗(yàn)中，對(duì)參數(shù)半徑dc的敏感性及選擇算法的有效性進(jìn)行分析與驗(yàn)證。實(shí)驗(yàn)結(jié)果如圖4所示，其中橫軸為半徑dc的取值(0.1～0.8)，以0.1為步長(zhǎng)不斷增加，縱坐標(biāo)是相應(yīng)半徑下對(duì)應(yīng)的密度基尼系數(shù)值。

隨著半徑dc的不斷增加，密度基尼系數(shù)H也會(huì)不斷增加，系統(tǒng)的不確定性不斷減小，在某個(gè)半徑dc值下密度基尼系數(shù)H達(dá)到最大，系統(tǒng)的不確定性達(dá)到最小，此時(shí)的半徑dc值為0.36。隨著半徑dc的值不斷增大，密度基尼系數(shù)H開(kāi)始不斷減小，系統(tǒng)的不確定性開(kāi)始增加。那么，當(dāng)系統(tǒng)的不確定性最小，即半徑dc等于0.36為最佳dc值。

通過(guò)評(píng)價(jià)指標(biāo)NMI和準(zhǔn)確率實(shí)驗(yàn)對(duì)本文算法進(jìn)行驗(yàn)證，結(jié)果如圖5和圖6所示。

圖5 不同的dc值在DBLP和Aminer數(shù)據(jù)集下的NMI值

圖6 不同的dc值在DBLP和Aminer數(shù)據(jù)集下的precision值

將NMI作為評(píng)價(jià)指標(biāo)，通過(guò)數(shù)據(jù)集DBLP和Aminer驗(yàn)證半徑dc的取值是否準(zhǔn)確。如圖5所示，半徑dc的值從0.1開(kāi)始到0.8不斷增大，當(dāng)半徑dc的值為0.36時(shí)，分別得到DBLP數(shù)據(jù)集和Aminer數(shù)據(jù)集下對(duì)應(yīng)的最大NMI值。可以得出，本文提出的參數(shù)dc值的設(shè)定是可行的，并且取得了較好的效果。

在圖6中，將precision作為評(píng)價(jià)指標(biāo)，通過(guò)數(shù)據(jù)集DBLP和Aminer驗(yàn)證半徑dc的取值是否準(zhǔn)確。通過(guò)驗(yàn)證，最終得到的半徑dc的值，是一個(gè)最優(yōu)的參數(shù)值，可以得到準(zhǔn)確的社區(qū)劃分結(jié)果。

3.3.2社區(qū)發(fā)現(xiàn)準(zhǔn)確性的驗(yàn)證

實(shí)驗(yàn)中，首先利用肘方法和節(jié)點(diǎn)密度估計(jì)合理性來(lái)確定聚類(lèi)個(gè)數(shù)K和參數(shù)dc的值。其次，為了保證準(zhǔn)確性，讓每次實(shí)驗(yàn)都在給定的網(wǎng)絡(luò)數(shù)據(jù)集中重復(fù)20次，度量指標(biāo)取實(shí)驗(yàn)的平均值。接著將本文提出的HD-K-means與傳統(tǒng)的K-means、基于特征提取進(jìn)行社區(qū)劃分的主成分分析(PCA)、具有拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)的非負(fù)矩陣分解(NMF)三種社區(qū)發(fā)現(xiàn)算法在異質(zhì)信息網(wǎng)絡(luò)數(shù)據(jù)集下作對(duì)比，驗(yàn)證HD-K-means算法社區(qū)劃分的效果。實(shí)驗(yàn)結(jié)果如表2所示。

通過(guò)NMI和precision值來(lái)觀察社區(qū)劃分結(jié)果。將本文提出的HD-K-means算法與傳統(tǒng)的K-means算法作比較，該算法使用超圖建模，更全面地表示網(wǎng)絡(luò)中不同類(lèi)型節(jié)點(diǎn)的復(fù)雜連接關(guān)系，并利用DeepWalk算法得到節(jié)點(diǎn)的低維向量表示，以獲得節(jié)點(diǎn)間更準(zhǔn)確的距離度量。仿真實(shí)驗(yàn)表明，在異質(zhì)信息網(wǎng)絡(luò)中HD-K-means算法能夠得到更好的社區(qū)劃分結(jié)果，且改善了傳統(tǒng)K-means算法的聚類(lèi)中心選擇敏感性問(wèn)題。另外，HD-K-means算法與其他三種異質(zhì)網(wǎng)絡(luò)社區(qū)劃分方法的對(duì)比結(jié)果表明，本文提出的HD-K-means算法在評(píng)價(jià)指標(biāo)NMI和precision上均有所提升。仿真實(shí)驗(yàn)驗(yàn)證了該方法適用于異質(zhì)信息網(wǎng)絡(luò)，且可以得到更準(zhǔn)確的社區(qū)劃分結(jié)果。

4 結(jié) 語(yǔ)

本文研究并提出一種應(yīng)用于異質(zhì)信息網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法HD-K-means，算法在網(wǎng)絡(luò)表示學(xué)習(xí)的支持下獲得節(jié)點(diǎn)向量表示，并將得到的節(jié)點(diǎn)向量根據(jù)歐氏距離計(jì)算節(jié)點(diǎn)距離(即相似度)，使用密度基尼系數(shù)選取聚類(lèi)中心，結(jié)合節(jié)點(diǎn)距離進(jìn)行聚類(lèi)并最終得到社區(qū)劃分結(jié)果。該方法在異質(zhì)信息網(wǎng)絡(luò)中繼承了傳統(tǒng)K-means算法邏輯簡(jiǎn)單、易于實(shí)現(xiàn)的特點(diǎn)，與此同時(shí)，基于密度基尼系數(shù)聚類(lèi)中心的選取方法與傳統(tǒng)K-means算法相比，無(wú)須迭代計(jì)算即可得到聚類(lèi)中心，降低了算法的復(fù)雜度。最終，通過(guò)實(shí)驗(yàn)驗(yàn)證了HD-K-means算法可行性和有效性。