基于符號網絡的社團檢測

劉鵬翼

（山西金融職業學院信息技術系，太原 030008）

0 引言

相比于普通復雜網絡只能表示節點之間有無關系，符號網絡可以表示節點之間的正負關系從而可以隱含更多信息[1]。許多現實世界的系統可以用符號網路來表示。例如，在在線社交網絡中，節點之間的正關系可以表示“贊同”、“朋友”。節點之間的負關系可以表示“反對”、“敵人”。

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

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

1 符號網絡社團檢測方法

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

1.1 基于平衡理論

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

1.2 基于符號模塊度優化

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

2 基于生成模型

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

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

3 研究與改進

3.1 非負矩陣分解

非負矩陣分解作為無監督學習中最受歡迎的方法之一由Lee D D在1999年[21]提出并廣泛應用在網絡分析中。利用非負矩陣分解在普通復雜網絡中的社團檢測可以表示為：

A表示為具有n個節點的普通復雜網絡的鄰接矩陣，H表示節點的指示矩陣，每個元素Hir表示了第i個節點在社團r中的可能性，W代表基矩陣。

3.2 改進

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

算法步驟

符號網絡社團檢測非負矩陣分解算法

輸入

符號網絡G的鄰接矩陣A；

迭代次數iter；

社團個數k；

輸出：

節點指示矩陣H

4 實驗

4.1 數據集

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

（1）無噪聲符號網絡：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是社團個數，n是節點個數，nij表示了真實在第i個社團被算法劃分到第j個社團的節點個數，ni（1）表示了真實在第 i個社團的節點個數，nj（2）是算法得到的社團劃分中第j個社團中的節點個數。NMI介于0到1之間，值越大表明算法的性能越好。

4.3 實驗一（無噪聲符號網絡數據集上）

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

4.4 實驗二（噪聲逐漸增大符號網路數據集）

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

圖1

圖2

5 結語

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