以社區(qū)發(fā)現(xiàn)為導(dǎo)向的網(wǎng)絡(luò)嵌入模型研究*

陳慧瑩 寇 月 申德榮 聶鐵錚

（東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽 110819）

1 引言

社交媒體網(wǎng)絡(luò)包含了豐富的網(wǎng)絡(luò)信息。聯(lián)系緊密的個(gè)體及其關(guān)聯(lián)關(guān)系形成了社交網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。傳統(tǒng)的網(wǎng)絡(luò)分析方法難以處理復(fù)雜多樣的數(shù)據(jù)且易丟失豐富的節(jié)點(diǎn)信息。網(wǎng)絡(luò)表示學(xué)習(xí)是將蘊(yùn)含豐富信息的數(shù)據(jù)表示成簡單低維的向量形式，并且同時(shí)直觀高效的保留原有的特征信息。如圖1所示，節(jié)點(diǎn)1與節(jié)點(diǎn)2、節(jié)點(diǎn)12原本分屬兩個(gè)不同的社區(qū)。若采用傳統(tǒng)的網(wǎng)絡(luò)嵌入方法，將可能導(dǎo)致三個(gè)節(jié)點(diǎn)被劃分為同一個(gè)社區(qū)。原因在于忽略了節(jié)點(diǎn)固有的社區(qū)結(jié)構(gòu)。對于同屬于一個(gè)社區(qū)的節(jié)點(diǎn)，應(yīng)該比隸屬于不同社區(qū)的節(jié)點(diǎn)更加相似。因此，考慮節(jié)點(diǎn)所體現(xiàn)出的社區(qū)特征，可以提高社區(qū)劃分的準(zhǔn)確性?，F(xiàn)有少數(shù)網(wǎng)絡(luò)嵌入方法考慮了網(wǎng)絡(luò)固有的社區(qū)結(jié)構(gòu)。例如，文獻(xiàn)［1］在網(wǎng)絡(luò)嵌入時(shí)考慮了社區(qū)特征，但沒有將社區(qū)特征與節(jié)點(diǎn)屬性特征相結(jié)合。文獻(xiàn)［2］也通過非負(fù)矩陣分解保持了社區(qū)結(jié)構(gòu)，但其目標(biāo)在于學(xué)習(xí)節(jié)點(diǎn)的嵌入表示，而非社區(qū)發(fā)現(xiàn)。針對以上不足，在學(xué)習(xí)節(jié)點(diǎn)的嵌入表示時(shí)，同時(shí)考慮節(jié)點(diǎn)屬性特征和社區(qū)特征，并且將嵌入表示應(yīng)用到社區(qū)發(fā)現(xiàn)中，以提高社區(qū)劃分的準(zhǔn)確性。貢獻(xiàn)如下：

圖1 具有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)

1）提出了一種以社區(qū)發(fā)現(xiàn)為導(dǎo)向的網(wǎng)絡(luò)嵌入模型（Community Detection-oriented Network Embedding，CDNE）。與傳統(tǒng)模型不同，該模型同時(shí)考慮了節(jié)點(diǎn)屬性特征和更高階的隱含特征（即網(wǎng)絡(luò)中固有的社區(qū)特征），同時(shí)體現(xiàn)了網(wǎng)絡(luò)的局部特征與全局特征。

2）提出了一種基于CDNE的兩階段社區(qū)發(fā)現(xiàn)算法。第一階段為合并社區(qū)；第二階段基于待合并社區(qū)重新構(gòu)建網(wǎng)絡(luò)。通過兩個(gè)階段的交替迭代執(zhí)行，來提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確性。

3）在真實(shí)數(shù)據(jù)集上設(shè)計(jì)對比實(shí)驗(yàn)，證明了該方法具有一定的優(yōu)勢。

2 相關(guān)工作

本節(jié)首先介紹了社區(qū)發(fā)現(xiàn)、網(wǎng)絡(luò)表示學(xué)習(xí)的相關(guān)工作并作出了比較。

早期Girvan等提出了GN算法［3］，該算法采用邊介數(shù)代表邊的強(qiáng)弱，通過不斷移除網(wǎng)絡(luò)中邊介數(shù)最大的邊得到社區(qū)結(jié)構(gòu)。Newman等提出基于模塊度Q的區(qū)挖掘算法［4］，該算法應(yīng)用了貪婪思想。Bagrow提出了一種局部社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法［5］。2013年，Yang等提出CESNA算法［6］，有效提高社區(qū)劃分的質(zhì)量。Yang等提出了一個(gè)條件模型來進(jìn)行鏈接分析以及一個(gè)歧視性模型來進(jìn)行內(nèi)容分析［7］。

傳統(tǒng)的網(wǎng)絡(luò)表示學(xué)習(xí)都是針對同質(zhì)信息網(wǎng)絡(luò)。異質(zhì)信息網(wǎng)絡(luò)中包括基于隨機(jī)游走、分解和針對應(yīng)用任務(wù)的網(wǎng)絡(luò)表示學(xué)習(xí)。Yu［80］等作者提出了基于元路徑［9］的Metapath2vec算法。Tang［10］等提出分解的思想，將異構(gòu)文本網(wǎng)絡(luò)中復(fù)雜的數(shù)據(jù)轉(zhuǎn)化為簡單高效的表現(xiàn)形式。Sun［11］等首先研究異質(zhì)信息網(wǎng)絡(luò)中同一類型頂點(diǎn)上的相似搜索方法Path-Sim。

本文提出的技術(shù)與上述不同之處在于：傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法極少考慮到網(wǎng)絡(luò)中更高階的社區(qū)結(jié)構(gòu)對社區(qū)發(fā)現(xiàn)的重要性。因此提出一種以社區(qū)發(fā)現(xiàn)為導(dǎo)向的網(wǎng)絡(luò)嵌入模型。此外，許多方法都采用傳統(tǒng)的網(wǎng)絡(luò)存儲(chǔ)方式耗費(fèi)了較高的存儲(chǔ)資源，考慮的特征也很單一，因此本文通過網(wǎng)絡(luò)嵌入將拓?fù)涮卣?，屬性特征以及社區(qū)特征有效地綜合起來，應(yīng)用到社區(qū)發(fā)現(xiàn)當(dāng)中，提高劃分的準(zhǔn)確性。

3 問題定義

定義1（屬性網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題）旨在從圖中G(V，E，W，S)找到T∈Rn×n個(gè)社區(qū)，其中T∈Rn×n表示T∈Rn×n個(gè)節(jié)點(diǎn)的集合，T∈Rn×n是邊的集合，T∈Rn×n表示邊T∈Rn×n的權(quán)重。S表示節(jié)點(diǎn)的屬性矩陣。并且理想的社區(qū)發(fā)現(xiàn)結(jié)果需滿足相同社區(qū)內(nèi)的節(jié)點(diǎn)屬性特征相似，不同社區(qū)內(nèi)的節(jié)點(diǎn)屬性相差較大。

定義2（網(wǎng)絡(luò)嵌入）定義圖T∈Rn×n，對所有節(jié)點(diǎn)T∈Rn×n，學(xué)習(xí)映射關(guān)系T∈Rn×n，將原節(jié)點(diǎn)表示成一個(gè)低維稠密的實(shí)數(shù)向量T∈Rn×n。

定義3（節(jié)點(diǎn)表示矩陣）節(jié)點(diǎn)表示矩陣T∈Rn×n，通過網(wǎng)絡(luò)嵌入方法得到節(jié)點(diǎn)低維的向量表示T∈Rn×n。

4 以社區(qū)發(fā)現(xiàn)為導(dǎo)向的網(wǎng)絡(luò)嵌入模型

為了充分利用并整合網(wǎng)絡(luò)的多種特征，以提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確性，提出了一種以社區(qū)發(fā)現(xiàn)為導(dǎo)向的網(wǎng)絡(luò)嵌入模型——CDNE。

4.1 CDNE模型的基本思想

模型有兩大部分組成：保持社區(qū)特征的網(wǎng)絡(luò)嵌入以及基于網(wǎng)絡(luò)嵌入的社區(qū)劃分（如圖2所示）。網(wǎng)絡(luò)中往往蘊(yùn)含了大量的信息，其中節(jié)點(diǎn)也具有豐富的屬性特征。同時(shí)，網(wǎng)絡(luò)中也可能存在原有的一些社區(qū)結(jié)構(gòu)。模型將這三種特征有機(jī)地結(jié)合起來，通過非負(fù)矩陣分解方法得到節(jié)點(diǎn)的低維表示。然后使用Louvain［12］社區(qū)發(fā)現(xiàn)算法完成社區(qū)劃分。

圖2 社區(qū)為導(dǎo)向的網(wǎng)絡(luò)嵌入模型CDNE

4.2 保持社區(qū)特征的網(wǎng)絡(luò)嵌入

在原始網(wǎng)絡(luò)中，從宏觀上看，網(wǎng)絡(luò)本就存在其固有的社區(qū)結(jié)構(gòu)，某些節(jié)點(diǎn)屬于同一潛在的社區(qū)結(jié)構(gòu)。

圖3 網(wǎng)絡(luò)嵌入

1）保持社區(qū)特征的學(xué)習(xí)

首先，找到關(guān)系矩陣進(jìn)行分解來獲得節(jié)點(diǎn)在低維空間中的映射。定義了模塊化矩陣B∈Rn×n，滿足式（1），其中Ki，Kj代表的是點(diǎn)i，j的度數(shù)，e代表的是邊的數(shù)目。

其中h=[hi]∈Rn是社區(qū)成員隸屬度向量。將社區(qū)成員隸屬度表示為矩陣H∈Rn×k。因此有約束t r(HT H)=n，得到了式（2）：

2）保持屬性特征的學(xué)習(xí)

社區(qū)不僅具有緊密連接的結(jié)構(gòu)，而且同一社區(qū)應(yīng)該具有相似的屬性。不同的社區(qū)也偏好不同的屬性。定義節(jié)點(diǎn)的余弦屬性相似度矩陣T∈Rn×n。

如式（3），通過分解屬性相似度矩陣ΔQ來得到節(jié)點(diǎn)表示矩陣U∈Rn×n，另引入一個(gè)輔助非負(fù)矩陣Ci即第i行表示一個(gè)社區(qū)的表示向量。因此進(jìn)行聯(lián)合建模，聯(lián)合損失函數(shù)如式（4）：

此外，通過控制非負(fù)參數(shù)α，β的大小來調(diào)節(jié)兩種特征的貢獻(xiàn)程度。目標(biāo)函數(shù)的優(yōu)化采用M-NMF中的迭代更新規(guī)則進(jìn)行優(yōu)化。

5 基于網(wǎng)絡(luò)嵌入的兩階段社區(qū)發(fā)現(xiàn)算法

基于CDNE模型，首先提出一種社區(qū)發(fā)現(xiàn)算法，該算法在Louvain算法的基礎(chǔ)上進(jìn)行改進(jìn)。

5.1 第一階段：合并社區(qū)

Louvain算法具有快速、準(zhǔn)確的優(yōu)點(diǎn)。但該算法忽略了網(wǎng)絡(luò)中固有的社區(qū)結(jié)構(gòu)，只考慮節(jié)點(diǎn)間的鏈接關(guān)系。針對它存在問題，本文考慮將節(jié)點(diǎn)屬性和社區(qū)特征應(yīng)用到Louvain算法中，實(shí)驗(yàn)證明在真實(shí)網(wǎng)絡(luò)中可以提高社區(qū)劃分的準(zhǔn)確性。

學(xué)習(xí)到節(jié)點(diǎn)的嵌入后，計(jì)算節(jié)點(diǎn)i與j向量的余弦相似度S(i，j)并作為節(jié)點(diǎn)間邊的權(quán)重。每個(gè)節(jié)點(diǎn)都當(dāng)做社區(qū)，遍歷所有節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)i分別加入每個(gè)鄰居節(jié)點(diǎn)所在的社區(qū)并計(jì)算加入前后模塊度的變化。根據(jù)模塊度增量ΔQ最大值將該節(jié)點(diǎn)i分配至對應(yīng)的鄰居節(jié)點(diǎn)社區(qū)，直至網(wǎng)絡(luò)中所有節(jié)點(diǎn)的分配穩(wěn)定得到初步劃分好的網(wǎng)絡(luò)。

5.2 第二階段：重構(gòu)網(wǎng)絡(luò)

這時(shí)將社區(qū)當(dāng)做一個(gè)新節(jié)點(diǎn)重構(gòu)網(wǎng)絡(luò)，分別計(jì)算這些新節(jié)點(diǎn)之間的連邊的權(quán)重，其值為先前網(wǎng)絡(luò)中跨社區(qū)之間連邊的相似度之和。重復(fù)階段一直到節(jié)點(diǎn)的社區(qū)分配基本穩(wěn)定，得到融合社區(qū)特征和節(jié)點(diǎn)屬性特征的網(wǎng)絡(luò)社區(qū)近似最優(yōu)劃分。

5.3 算法描述

基于網(wǎng)絡(luò)嵌入的兩階段社區(qū)發(fā)現(xiàn)算法過程如下。

算法1 基于嵌入的社區(qū)發(fā)現(xiàn)算法輸入 屬性網(wǎng)絡(luò)G；

輸出 G的社區(qū)劃分結(jié)果partition

1 For each node｛u，v｝∈E

2 Calcualte node similarity Cs；

3 End

4 Initialize each node into individual communities and calculating modularity，denoted by Q；

5 For each i in｛v｝

6 Calculate the neighbors｛k｝of node i；

7 For（j in neighbors｛k｝）

8 Delete node i from the pre_community；

9 Add node i into communoty of neighbor j

10 CalculateΔQ；

11 Choose the maximumΔQ and add the node i into the new community ofΔQ；

12 Calculate Q；

13 End

14 Regard each community as a new node and repeat the above steps；

15 Return the result；

6 實(shí)驗(yàn)與結(jié)果

6.1 實(shí)驗(yàn)數(shù)據(jù)集

本文在Cornell、Wisconsin和Texas三個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，三個(gè)數(shù)據(jù)集統(tǒng)計(jì)信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集的統(tǒng)計(jì)信息

|V|代表節(jié)點(diǎn)數(shù)，|E|代表邊數(shù)，s代表屬性數(shù)量，k代表社區(qū)數(shù)量；AS代表社區(qū)的平均大小。

6.2 評價(jià)指標(biāo)

NMI是一種常用的評價(jià)社區(qū)發(fā)現(xiàn)算法精度的指標(biāo)。模塊度是根據(jù)社區(qū)內(nèi)部節(jié)點(diǎn)和邊的疏密程度來量化社區(qū)結(jié)構(gòu)的質(zhì)量。

6.3 對比算法

基于初始結(jié)構(gòu)的Louvain算法。SCI算法［13］提出了一種非負(fù)矩陣分解模型。SNMF［14］是一種基于非負(fù)矩陣分解的社區(qū)發(fā)現(xiàn)算法。PCL-DC［15］是一種綜合鏈接和內(nèi)容的社區(qū)發(fā)現(xiàn)算法。

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

1）參數(shù)敏感性分析

以下在Cornell數(shù)據(jù)集上進(jìn)行了CDNE的參數(shù)敏感性分析。α，β分別控制節(jié)點(diǎn)屬性、社區(qū)特征的貢獻(xiàn)度；由圖可知，當(dāng)α=1，β=2時(shí)可取到NMI最大值為0.368。

2）對比算法實(shí)驗(yàn)結(jié)果分析

本文將CDNE與四種基線算法做了性能比較。采用NMI和模塊度兩種評價(jià)指標(biāo)來衡量。圖5中結(jié)果表明CDNE算法都明顯要優(yōu)于其他算法。相比較可知，通過網(wǎng)絡(luò)嵌入融合社區(qū)特征與節(jié)點(diǎn)屬性特征有效地提高了社區(qū)發(fā)現(xiàn)的準(zhǔn)確性。

圖4 Cornell中參數(shù)α，β對NMI的影響

圖5 對比算法實(shí)驗(yàn)結(jié)果分析

7 結(jié)語

針對現(xiàn)有的社區(qū)發(fā)現(xiàn)算法的不足，本文提出了一種以社區(qū)發(fā)現(xiàn)為導(dǎo)向的網(wǎng)絡(luò)嵌入模型（CDNE），充分考慮了網(wǎng)絡(luò)中的社區(qū)特征，節(jié)點(diǎn)屬性信息，利用非負(fù)矩陣分解將三者有機(jī)地融合起來。此外本文提出基于網(wǎng)絡(luò)嵌入的兩階段社區(qū)發(fā)現(xiàn)算法。采用Louvain算法進(jìn)行社區(qū)劃分，融合社區(qū)特征和節(jié)點(diǎn)屬性特征的同時(shí)有效地提高了社區(qū)發(fā)現(xiàn)的準(zhǔn)確性。