基于符號(hào)網(wǎng)絡(luò)的社團(tuán)檢測(cè)

劉鵬翼

（山西金融職業(yè)學(xué)院信息技術(shù)系，太原 030008）

0 引言

相比于普通復(fù)雜網(wǎng)絡(luò)只能表示節(jié)點(diǎn)之間有無關(guān)系，符號(hào)網(wǎng)絡(luò)可以表示節(jié)點(diǎn)之間的正負(fù)關(guān)系從而可以隱含更多信息[1]。許多現(xiàn)實(shí)世界的系統(tǒng)可以用符號(hào)網(wǎng)路來表示。例如，在在線社交網(wǎng)絡(luò)中，節(jié)點(diǎn)之間的正關(guān)系可以表示“贊同”、“朋友”。節(jié)點(diǎn)之間的負(fù)關(guān)系可以表示“反對(duì)”、“敵人”。

許多社交網(wǎng)絡(luò)已經(jīng)被發(fā)現(xiàn)具有社團(tuán)結(jié)構(gòu)。在普通的復(fù)雜網(wǎng)絡(luò)中，社團(tuán)結(jié)構(gòu)表現(xiàn)為同一社團(tuán)內(nèi)的節(jié)點(diǎn)之間的聯(lián)系比不同社團(tuán)間節(jié)點(diǎn)間的聯(lián)系更加緊密。而符號(hào)網(wǎng)路因?yàn)楣?jié)點(diǎn)間負(fù)關(guān)系的存在使得社團(tuán)結(jié)構(gòu)更加復(fù)雜。它表現(xiàn)為同一社團(tuán)內(nèi)部節(jié)點(diǎn)多為正連接，不同社團(tuán)節(jié)點(diǎn)間多為負(fù)連接。用來發(fā)現(xiàn)這種社團(tuán)結(jié)構(gòu)的社團(tuán)檢測(cè)是社交網(wǎng)絡(luò)分析（Social Network Analysis，SNA）最重要的任務(wù)之一。在過去一段時(shí)間，雖然有各種各樣的社團(tuán)檢測(cè)方法被提出，但是他們大多數(shù)都是基于普通復(fù)雜網(wǎng)絡(luò)的[2-4]。雖然近幾年也有一些基于符號(hào)網(wǎng)絡(luò)的社團(tuán)檢測(cè)方法被提出，但是它的發(fā)展依然很有限。

在本文中，基于符號(hào)網(wǎng)絡(luò)中存在負(fù)關(guān)系的特性，我們巧妙地將符號(hào)網(wǎng)絡(luò)分隔為正負(fù)兩個(gè)分量。然后在正負(fù)兩個(gè)分量上分別利用非負(fù)矩陣分解進(jìn)而得到符號(hào)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。我們?cè)谌斯ど傻臄?shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。驗(yàn)證了我們的方法具有很高的有效性和準(zhǔn)確性。

1 符號(hào)網(wǎng)絡(luò)社團(tuán)檢測(cè)方法

近幾年，一些符號(hào)網(wǎng)絡(luò)社團(tuán)檢測(cè)的方法被提出。這些算法可以大致分為以下幾類：基于平衡理論、基于符號(hào)模塊度優(yōu)化、基于生成模型。

1.1 基于平衡理論

二十世紀(jì)四十年代，Heider[5]基于個(gè)體的感知和態(tài)度提出了結(jié)構(gòu)平衡理論，這是關(guān)于符號(hào)網(wǎng)絡(luò)最重要的社會(huì)理論基礎(chǔ)。五十年代，Cartwright和Harary[6]進(jìn)一步在圖模型的基礎(chǔ)上發(fā)展了結(jié)構(gòu)平衡理論。結(jié)構(gòu)平衡理論應(yīng)用在符號(hào)網(wǎng)絡(luò)中的主要內(nèi)容是：在符號(hào)網(wǎng)絡(luò)中，社團(tuán)內(nèi)部節(jié)點(diǎn)間的聯(lián)系多為正關(guān)系，不同社團(tuán)節(jié)點(diǎn)間的聯(lián)系多為負(fù)關(guān)系。相對(duì)應(yīng)與符號(hào)網(wǎng)絡(luò)中結(jié)構(gòu)平衡理論的內(nèi)容，提出了符號(hào)網(wǎng)絡(luò)中噪聲的定義，即社團(tuán)內(nèi)部節(jié)點(diǎn)間的負(fù)關(guān)系和不同社團(tuán)節(jié)點(diǎn)間的正關(guān)系。隨后基于平衡理論的思想許多符號(hào)網(wǎng)絡(luò)社團(tuán)檢測(cè)的方法被提出。Doreian P、Mrvar A提出了一個(gè)最小化符號(hào)網(wǎng)絡(luò)噪聲的方法[7]來進(jìn)行符號(hào)網(wǎng)絡(luò)的社團(tuán)檢測(cè)。Bansal等人提出了一個(gè)Correlation Clustering（CC）的方法[8]來最大化社團(tuán)內(nèi)節(jié)點(diǎn)正關(guān)系和不同社團(tuán)節(jié)點(diǎn)間負(fù)關(guān)系進(jìn)而對(duì)符號(hào)網(wǎng)絡(luò)進(jìn)行社團(tuán)檢測(cè)。相似地，Larusso等人[9]運(yùn)用相同的思想進(jìn)行符號(hào)網(wǎng)絡(luò)社團(tuán)檢測(cè)。Traag[14]基于平衡理論擴(kuò)展原有的Potts模型結(jié)合符號(hào)網(wǎng)絡(luò)中的負(fù)連接來挖掘符號(hào)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。

1.2 基于符號(hào)模塊度優(yōu)化

標(biāo)準(zhǔn)模塊度是基于普通復(fù)雜網(wǎng)絡(luò)的。它度量了網(wǎng)絡(luò)中實(shí)際的連接與隨機(jī)連接的偏離程度。普通復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)可以通過優(yōu)化標(biāo)準(zhǔn)模塊度目標(biāo)函數(shù)得到[11]。但它的求解實(shí)質(zhì)是一個(gè)離散組合問題[10]。即NP-hard問題。所以可以通過一些啟發(fā)式算法來求解，例如模擬退火算法。Gomez S[12]通過模塊化重構(gòu)來分析普通復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。而符號(hào)模塊度是由Li Y[13]通過改進(jìn)標(biāo)準(zhǔn)模塊度來定義的，使符號(hào)模塊度可以處理符號(hào)網(wǎng)絡(luò)中負(fù)關(guān)系的情況。符號(hào)模塊度通過調(diào)節(jié)符號(hào)網(wǎng)絡(luò)正負(fù)分量上權(quán)重來平衡節(jié)點(diǎn)間正連接形成社團(tuán)和節(jié)點(diǎn)間負(fù)連接破壞社團(tuán)的趨勢(shì)。它本質(zhì)上是標(biāo)準(zhǔn)模塊度的加權(quán)融合，所以它的求解同樣屬于NP-hard問題。對(duì)此一些優(yōu)化算法被提出。例如，Anchuri和Magdon_Ismail基于普通復(fù)雜網(wǎng)絡(luò)模塊度優(yōu)化的算法[11]擴(kuò)展提出了一個(gè)譜聚類[15]的方法來進(jìn)行符號(hào)網(wǎng)絡(luò)社團(tuán)檢測(cè)。

2 基于生成模型

以上的基于符號(hào)網(wǎng)絡(luò)的社團(tuán)檢測(cè)都是基于優(yōu)化目標(biāo)函數(shù)或者啟發(fā)式的方法，并不關(guān)心網(wǎng)絡(luò)的生成。所以一些基于生成模型的算法被提出。例如，Yang等人[16]提出了一個(gè)基于代理的隨機(jī)游走模型（FEC）來挖掘符號(hào)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。Zhao等人[17]提出了一種概率模型（SISN）來對(duì)符號(hào)網(wǎng)絡(luò)進(jìn)行建模，并推導(dǎo)出基于期望最大化的參數(shù)估計(jì)方法來挖掘符號(hào)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。Chen等人[18]提出了一個(gè)重疊社團(tuán)檢測(cè)方法-符號(hào)概率最大化模型（Signed Probabilistic Mixture，SPM）。Jonathan Q.Jiang提出了一個(gè)廣義隨機(jī)塊模型（Stochastic Block Model，SBM）[19]，通過將表現(xiàn)出相似的正負(fù)連接輪廓的頂點(diǎn)分組到同一簇中來探索符號(hào)網(wǎng)絡(luò)的介觀結(jié)構(gòu)。Yang等人[20]提出的符號(hào)隨機(jī)塊模型（Signed Stochastic Block Model，SSBM）?；谝环N隨機(jī)的觀點(diǎn)生成連接的密度和符號(hào)，刻畫并生成符號(hào)網(wǎng)絡(luò)的塊結(jié)構(gòu)，并基于變分貝葉斯進(jìn)行優(yōu)化，自動(dòng)確定社團(tuán)個(gè)數(shù)。

然而上述的方法社團(tuán)檢測(cè)的結(jié)果的準(zhǔn)確性上都不是很高。為此我們基于非負(fù)矩陣分解的思想提出了一個(gè)新的符號(hào)網(wǎng)絡(luò)社團(tuán)檢測(cè)的方法。

3 研究與改進(jìn)

3.1 非負(fù)矩陣分解

非負(fù)矩陣分解作為無監(jiān)督學(xué)習(xí)中最受歡迎的方法之一由Lee D D在1999年[21]提出并廣泛應(yīng)用在網(wǎng)絡(luò)分析中。利用非負(fù)矩陣分解在普通復(fù)雜網(wǎng)絡(luò)中的社團(tuán)檢測(cè)可以表示為：

A表示為具有n個(gè)節(jié)點(diǎn)的普通復(fù)雜網(wǎng)絡(luò)的鄰接矩陣，H表示節(jié)點(diǎn)的指示矩陣，每個(gè)元素Hir表示了第i個(gè)節(jié)點(diǎn)在社團(tuán)r中的可能性，W代表基矩陣。

3.2 改進(jìn)

由于符號(hào)網(wǎng)絡(luò)中存在負(fù)關(guān)系，不能直接應(yīng)用非負(fù)矩陣分解在符號(hào)網(wǎng)絡(luò)中。我們巧妙地將符號(hào)網(wǎng)絡(luò)分解為正負(fù)兩個(gè)分量。給定一個(gè)符號(hào)網(wǎng)絡(luò)G，它的鄰接矩陣A可以分解為正分量鄰接矩陣A+和負(fù)分量A-。其中A=A+-A-。W+和W-分別為正分量和負(fù)分量上的基矩陣。H表示節(jié)點(diǎn)的指示矩陣，每個(gè)元素Hir表示了第i個(gè)節(jié)點(diǎn)在社團(tuán)r中的可能性。

算法步驟

符號(hào)網(wǎng)絡(luò)社團(tuán)檢測(cè)非負(fù)矩陣分解算法

輸入

符號(hào)網(wǎng)絡(luò)G的鄰接矩陣A；

迭代次數(shù)iter；

社團(tuán)個(gè)數(shù)k；

輸出：

節(jié)點(diǎn)指示矩陣H

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

4.1 數(shù)據(jù)集

我們通過人工生成了符號(hào)網(wǎng)絡(luò)數(shù)據(jù)集，其中包括了以下幾個(gè)參數(shù) c、n、pin、p+、p-、c是社團(tuán)個(gè)數(shù)，n 網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)，pin是社團(tuán)內(nèi)節(jié)點(diǎn)連邊的可能性，p+、p-分別表示了社團(tuán)內(nèi)部節(jié)點(diǎn)間負(fù)連接的比例和不同社團(tuán)節(jié)點(diǎn)間正連接的比例（代表了符號(hào)網(wǎng)絡(luò)中的噪聲）。我們?cè)O(shè)置數(shù)據(jù)集中的參數(shù)如下并生成了兩種符號(hào)網(wǎng)絡(luò)：c=4，n=128。

（1）無噪聲符號(hào)網(wǎng)絡(luò)：pin從0.2到1逐漸增加，p+=0，p-=0；

（2）噪聲逐級(jí)增大：pin=0.8，p+從 0 到 0.5，p-從 0到0.5；

4.2 評(píng)價(jià)指標(biāo)

我們利用歸一化互信息（Normalized Mutual Information，NMI）去評(píng)價(jià)我們提出方法的性能[A.Strehl and J.Ghosh,Journal of Machine Learning Research 3,583（2002）.]。

Where C和C’分別表示了真實(shí)社團(tuán)劃分和算法得到的社團(tuán)劃分，k是社團(tuán)個(gè)數(shù)，n是節(jié)點(diǎn)個(gè)數(shù)，nij表示了真實(shí)在第i個(gè)社團(tuán)被算法劃分到第j個(gè)社團(tuán)的節(jié)點(diǎn)個(gè)數(shù)，ni（1）表示了真實(shí)在第 i個(gè)社團(tuán)的節(jié)點(diǎn)個(gè)數(shù)，nj（2）是算法得到的社團(tuán)劃分中第j個(gè)社團(tuán)中的節(jié)點(diǎn)個(gè)數(shù)。NMI介于0到1之間，值越大表明算法的性能越好。

4.3 實(shí)驗(yàn)一（無噪聲符號(hào)網(wǎng)絡(luò)數(shù)據(jù)集上）

我們將提出的方法同以前的一些算法在無噪聲符號(hào)網(wǎng)路上（符號(hào)網(wǎng)絡(luò)中相同社團(tuán)內(nèi)只有正連接，不同社團(tuán)間只有負(fù)連接）進(jìn)行了對(duì)照實(shí)驗(yàn)（如圖1），表明我們的方法要更優(yōu)于之前的一些算法。

4.4 實(shí)驗(yàn)二（噪聲逐漸增大符號(hào)網(wǎng)路數(shù)據(jù)集）

我們通過控制社團(tuán)內(nèi)部節(jié)點(diǎn)間負(fù)連接的比例p-和不同社團(tuán)節(jié)點(diǎn)間正連接的比例p+來控制符號(hào)網(wǎng)絡(luò)中的噪聲。增大符號(hào)網(wǎng)絡(luò)中的噪聲并于其他以前的算法（SSL、SISN、FEC）進(jìn)行對(duì)照實(shí)驗(yàn)（實(shí)驗(yàn)結(jié)果如圖 2），表明我們提出方法的魯棒性要優(yōu)于其他算法。

圖1

圖2

5 結(jié)語(yǔ)

在本文中，我們將非負(fù)矩陣分解的思想運(yùn)用到符號(hào)網(wǎng)路的社團(tuán)檢測(cè)中。巧妙地將符號(hào)網(wǎng)絡(luò)轉(zhuǎn)化為正負(fù)兩個(gè)分量，分別對(duì)兩個(gè)分量進(jìn)行非負(fù)矩陣分解從而得到符號(hào)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，在不同性質(zhì)人工生成的符號(hào)網(wǎng)絡(luò)上的與其他算法的對(duì)照實(shí)驗(yàn)也證明我們提出方法性能優(yōu)于之前的一些算法。有著很好的準(zhǔn)確性和魯棒性。未來我們將進(jìn)一步應(yīng)用該算法在真實(shí)的符號(hào)網(wǎng)絡(luò)數(shù)據(jù)集上，例如構(gòu)建新浪微博等在線社交網(wǎng)絡(luò)的符號(hào)網(wǎng)絡(luò)，挖掘微博網(wǎng)絡(luò)等在線社交網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。