劉鵬翼

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

0 引言

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

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

在本文中，基于符號網(wǎng)絡(luò)中存在負關(guān)系的特性，我們巧妙地將符號網(wǎng)絡(luò)分隔為正負兩個分量。然后在正負兩個分量上分別利用非負矩陣分解進而得到符號網(wǎng)絡(luò)的社團結(jié)構(gòu)。我們在人工生成的數(shù)據(jù)集上進行了實驗。驗證了我們的方法具有很高的有效性和準確性。

1 符號網(wǎng)絡(luò)社團檢測方法

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

1.1 基于平衡理論

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

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

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

2 基于生成模型

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

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

3 研究與改進

3.1 非負矩陣分解

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

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

3.2 改進

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

算法步驟

符號網(wǎng)絡(luò)社團檢測非負矩陣分解算法

輸入

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

迭代次數(shù)iter；

社團個數(shù)k；

輸出：

節(jié)點指示矩陣H

4 實驗

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

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

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

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

4.2 評價指標

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

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

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

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

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

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

圖1

圖2

5 結(jié)語

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