一種基于因子圖模型的半監督社區發現方法

黃立威　李彩萍　張海粟　劉玉超　李德毅　劉艷博

一種基于因子圖模型的半監督社區發現方法

黃立威1李彩萍1張海粟2劉玉超3李德毅4劉艷博1

社區發現是社交網絡分析中一個重要的研究方向.當前大部分的研究都聚焦在自動社區發現問題，但是在具有數據缺失或噪聲的網絡中，自動社區發現算法的性能會隨著噪聲數據的增加而迅速下降.通過在社區發現中融合先驗信息，進行半監督的社區發現，有望為解決上述挑戰提供一條可行的途徑.本文基于因子圖模型，通過融入先驗信息到一個統一的概率框架中，提出了一種基于因子圖模型的半監督社區發現方法，研究具有用戶引導情況下的社交網絡社區發現問題.在三個真實的社交網絡數據（Zachary社會關系網、海豚社會網和DBLP協作網）上進行實驗，證明通過融入先驗信息可以有效地提高社區發現的精度，且將我們的方法與一種最新的半監督社區發現方法（半監督Spin-Glass模型）進行對比，在三個數據集中F-measure平均提升了6.34%、16.36%和12.13%.

社交網絡，半監督社區發現，因子圖，社交網絡分析，概率推理

引用格式黃立威，李彩萍，張海粟，劉玉超，李德毅，劉艷博.一種基于因子圖模型的半監督社區發現方法.自動化學報，2016，42（10）:1520-1531

社交網絡中，用戶由于共同的興趣和特征結成群體，群體體現了關系的局部聚集特性.在網絡科學研究中，人們把用戶視為節點，關系視為邊，群體視為社區［1］.社區通常由功能相近或性質相似的網絡節點組成，在一定程度上反映了用戶自發、無序行為背后的局部弱規則性和全局有序性.對社交網絡的社區結構的深入研究不僅有助于揭示相對獨立而又相互關聯的社區如何形成錯綜復雜的社交網絡，幫助人們更好地理解系統在不同層次上的結構和功能特性，而且具有很多的實用價值，例如通過發現網絡中的社區揭示具有共同興趣或相似社會背景的社會團體.因此，社區發現已成為社交網絡分析領域中一個非常重要的研究方向.

目前大部分社區發現的研究都是面向自動社區發現問題，即根據網絡結構，通過算法自動地發現網絡中的社區，是一種無監督的方法.但自動的社區發現通常存在兩個重要的問題：

1）在面對具有鏈路缺失或具有噪聲數據的網絡時，自動社區發現的性能會大大下降［2］，很難有效地揭示網絡中的真實社區結構；

2）類似于流行的模塊度優化的社區發現方法［3］，通過近似優化方法最大化模塊度來發現社區，通常得不到最優的社區劃分［4］.

導致第一個問題的原因通常是，社區發現的時候僅僅考慮了當前的網絡信息，其前提是將網絡作為一個正確的、完全的網絡處理，但通常情況下，我們獲得的網絡包含了大量包括錯誤連接在內的噪聲數據，網絡連接通常也是不完全的.在這樣的情況下，即使最好的自動社區發現方法在遇到具有噪聲的網絡時其性能也會急劇下降.第二個問題是由于通過優化方法最大化模塊度得到的是一個近似解，導致發現的社區是多種多樣的，即使模塊度的值差得很小，也可能導致差異非常大的社區劃分，不能得到一個最優的劃分結果，也很難發現特定情境下滿足特定需求的社區結構.

在數據挖掘領域，針對具體的任務，往往會考慮加入用戶引導或約束到挖掘任務中，提高數據挖掘的性能.事實上，在社交網絡環境下，已知部分社區劃分信息的情況也普遍存在，例如我們可能已知部分用戶屬于某一個社區，或者已知兩個用戶屬于相同或不同的社區.通過將這些信息融入到社區劃分中，進行半監督的社區發現，往往可以有效提高社區劃分的準確度，提高噪聲環境下社區劃分的魯棒性，而且還能幫助發現滿足特定需求的社區劃分.

在本文中，我們針對兩種類型的先驗信息，即已知部分節點的社區劃分以及用戶之間存在的成對的必須連接約束（Must-link constraints）和不能連接約束（Cannot-link constraints），研究半監督社區發現問題，提出了一種基于因子圖模型的半監督社區發現方法，將原始的社交網絡與兩種先驗信息融合到一個統一的半監督概率框架中，既可以使得發現的社區滿足先驗條件，又可以符合網絡的整體社區結構.本文提出的模型具有高的適應性，因為通過定義更高階的因子特征函數，我們可以將兩個以上節點之間的約束融合到社區發現問題中.文獻［5］研究了利用因子圖模型進行社區發現的問題，但并沒有考慮先驗信息.據我們所能得到的信息，本文是第一次從概率推理的視角研究半監督社區發現問題，或許能夠為我們進一步探索社區發現的不確定性提供一些有用的啟發.

1　相關工作

2002年，Girvan和Newman［6］提出一種分裂式層次聚類方法，簡稱GN算法.在該方法中，作者為網絡中的每條邊定義了一個邊介數（Edge betweenness）的量，一條邊的邊介數定義為網絡的所有最短路徑中經過該邊的路徑數目占最短路徑總數的比例.邊介數反映了相應的邊在整個網絡中的橋接作用，當按照邊介數由高到低依次刪除邊時，網絡分裂的速度要遠快于隨機刪除連邊時的網絡分裂速度.因此，Girvan等提出一個迭代過程，每次迭代過程中通過計算網絡中每條邊的介數然后去除介數最大的邊，一直到網絡中所有的邊被去除，每個節點自成一個社區，迭代過程停止.這種方法面臨的困難在于切割位置的選擇，即選擇合并或分裂停止的時機，該問題的本質在于缺乏一種度量網絡劃分質量的有效手段.為解決網絡劃分質量度量這一本質問題，Newman等提出了著名的模塊度（Modularity）的概念［3］.模塊度選擇一個假定不存在社區結構的網絡（一般使用配置模型產生）作為參照網絡，給定一個網絡劃分，通過對比原有網絡和參照網絡中處于該劃分的各個分量內部邊的比例，給出一種度量網絡劃分質量的手段.一般認為，對于同一個網絡的不同劃分，模塊度越高，該劃分越能體現網絡固有的社區結構.如此一來，網絡社區發現問題變成了一個模塊度優化問題，即從網絡的所有可能劃分中尋找一個劃分，使該劃分具有最大的模塊度，該劃分的各個分量視為社區.模塊度的提出很大程度上推動了社區發現的研究，研究人員開始探索基于模塊度優化的算法.Brandes等指出模塊度優化問題是一個NP難問題［7］，因此，人們引入各種啟發式的模塊度優化方法，如貪婪算法［8］、極值優化方法［9］、模擬退火［10］和譜聚類［11］等.

目前模塊度優化方法已成為復雜網絡社區發現的基準方法，并得到廣泛的應用.然而，進一步的研究發現模塊度優化方法在處理各種具體網絡時存在一些問題：1）文獻［12］發現由于隨機波動模塊度方法中所采用的參照網絡也會呈現出偽社區結構，從而對模塊度方法中采用參照網絡提出了質疑，并基于統計顯著性給出了相應的改進辦法；2）文獻［13］指出對于給定的網絡，模塊度優化方法存在一個固有的分辨率，使得模塊度優化方法不能識別出該分辨率以下的社區，這就是所謂的“分辨率限制”問題.因此，小社區往往會被大的社區吸納，從而淹沒在大的網絡社區中而無法被識別出來；3）文獻［14］發現模塊度優化方法不能很好地處理節點度分布高度差異的網絡，而真實網絡中的節點度分布往往服從冪率分布，研究通過引入尺度（Rescaling）變換解決了該問題.

進一步的研究表現，真實世界中的網絡社區之間普遍存在重疊節點，這些節點在不同社區間起著橋梁作用，在社區中發揮著重要影響，是社區間信息擴散的媒介和社區演化的推手.鑒于這個問題，人們開始著眼于重疊社區結構的研究.最初，Palla等在Nature上發表論文［15］，指出了社區重疊這一重要現象，并提出了一種基于完全子圖滲流（Clique percolation）的重疊社區發現方法.隨后，該算法被擴展應用到有向網絡、有權網絡和二部網絡等.直到現在，完全子圖滲流算法依然是重疊社區發現研究中應用最為廣泛的方法之一.

社區演化是社區發現研究中的另一個重要問題.演化是真實網絡所具有的基本特性，社區演化是網絡自身結構和在其上頻繁發生的交互過程相互作用的結果.社區演化分析主要研究社區隨時間變化的情況，并分析導致社區演化的原因以及內在的機制.文獻［16］基于他們提出的完全子圖滲流社區發現方法研究社區演化，得到一個有趣的結論：小社區的穩定性是保證其存在的前提，而大社區的動態性是其存在的基礎.文獻［17］通過擴展模塊度研究異構關系網絡中隨時間演化的、多尺度社區結構.更多社區發現的研究可以參考文獻［1］.

目前半監督社區發現的研究還較少.事實上，半監督社區劃分與傳統數據挖掘中的半監督聚類密切相關，Ma等［18］通過組合對稱的非負矩陣因子分解和半監督聚類方法，融合成對的約束進行半監督社區發現.Allahverdyan等［19］通過融合部分已知的社區標簽到社區發現中，分析了先驗信息對于社區發現的影響.Eaton等［2］分別考慮已知部分社區標簽和成對約束的兩種情形，提出一種半監督的Spin-Glass模型，進行社區發現，可以有效地抵消噪聲帶來的影響.Liu等［20］提出了一種基于離散勢理論的半監督社區發現算法，考慮了已知部分節點社區標簽的先驗信息.Li等［21］提出一種基于極值優化的半監督社區發現方法，這種方法利用了成對節點之間的社區約束信息.Yang等［22］基于隱空間相似性提出一種統一的半監督框架，可以在多種社區發現模型中融入社區先驗信息.針對半監督信息難以獲取的問題，Yang等［23］提出一種主動鏈路選擇框架，研究了如何標注最不確定或最具信息量的先驗信息，從而可以通過更少的先驗信息達到相同的社區發現效果.但以上的研究中，都沒有考慮同時融合多種先驗信息的情形，本文提出的方法可以同時融入多種先驗信息到一個統一的概率框架中，并通過優化方法確定不同的信息的權重.

2　問題定義

為了融合先驗信息到社區發現中，我們基于因子圖模型，對社交網絡中的半監督社區發現問題進行建模，提出一種基于因子圖的半監督社區發現方法（Factor graph-based semi-supervised community detection，FG-SSCD）.為了更清晰地對問題進行描述，首先我們給出社區發現的定義：

定義1（社區發現）.給定社交網絡G=（V，E，A，Y）以及期望的社區集合L=｛l1，l2，···，lK｝，其中V是所有用戶的集合，|V|=N，E?V×V是所有用戶關系的集合，A是網絡對應的鄰接矩陣，Y是所有用戶的社區標簽，在一般的社區劃分問題中，它在初始階段是未知的，L表示所有社區標簽集合.社區發現的目標是為每個用戶vi確定其社區標簽yi，yi∈｛l1，l2，···，lK｝，表示vi屬于的社區.

在半監督社區發現問題中，通常考慮兩種形式的先驗知識：1）已知部分節點的社區標簽；2）成對節點之間的必須連接和不能連接約束.在兩種先驗信息之間不存在沖突的前提下，本文研究的問題是如何同時考慮這兩種信息，將其融入到一個統一的概率模型中，引導我們進行半監督社區劃分.因此可以給出本文研究的半監督社區發現問題的定義.

定義2（半監督社區發現）.給定社交網絡G=（V，E，A，Y），期望的社區集合L=｛l1，l2，···，lK｝，必須連接約束的集合M=｛（xi，xj）｝和不能連接約束的集合C=｛（xi，xj）｝，約束侵犯代價矩陣W 和其代表每個約束被侵犯需要付出的代價，也可以理解為每個約束的重要性權重，以及部分已知的用戶社區標簽YL和未知的用戶社區標簽YU，滿足YU∩YL=?，YU∪YL=Y.半監督社區發現的目標是針對未確定社區劃分的用戶vi，預測它們的社區標簽yi，yi∈｛l1，l2，···，lK｝，即vi所屬于的社區.

此外，針對每個社區lk存在一個變量集合Xk，用于表示社區lk中的用戶集合.

3　基于因子圖模型的半監督社區發現方法

3.1模型建立

在本節中，考慮融合先驗信息到社區劃分問題中，借鑒Tang等［24］提出的部分因子圖模型的思想，建立一個基于因子圖的半監督社區發現模型FGSSCD，將半監督的社區發現問題建模到一個統一的框架中.

本文接下來給出FG-SSCD模型的一個簡單例子.如圖1所示，左側的圖展示了一個網絡示例，包含了5個用戶｛v1，v2，···，v5｝以及相應的社會關系.右側的圖是由左側的網絡作為輸入所建立的FG-SSCD模型，圖中觀測變量是網絡中給定的用戶｛v1，v2，···，v5｝，模型的隱變量即每個用戶的社區標簽｛y1，y2，···，y5｝，假設整個網絡中的用戶劃分為兩個社區，即社區標簽為｛1，2｝，網絡中已知用戶v1，v2，v5的社區標簽，分別為1，1，2，需要預測用戶v3，v4的社區劃分.為了對模型進行更加清晰的描述，下面對模型的基本要素分別進行詳細介紹：

圖1　FG-SSCD模型的圖結構Fig.1　Graphical structure of FG-SSCD

1）變量節點

模型中包含了兩類變量節點，分別為：隱變量和觀測變量.

隱變量節點：模型中包含一個隱變量的集合｛y1，y2，···，yn｝，是不能直接觀測到的，在圖中用白色的圓圈表示，代表每個用戶vi的社區標簽，是問題需要預測的值.

觀測變量節點：模型中包含一個觀測變量的集合｛v1，v2，···，vn｝，在圖中用灰色的圓圈表示，每一個觀測變量由條件概率分布P（vi|yi）所產生，在模型中，當給定社區劃分的情況下，隨機變量V的產生是條件獨立的，即

2）因子節點

根據用戶自身的特征，用戶之間存在的社會關系以及在社區發現中的約束，可以在模型中定義相關的因子函數：

節點特征因子：f（yi）是定義在單個隱變量上的節點特征因子，其表示在給定節點社區標簽yi產生觀測數據vi的概率P（vi|yi）.

關聯特征因子：g（yi，yj）是定義在節點對之間的關聯特征因子，反映了隱變量之間存在的關聯，在本文模型中，僅僅考慮了成對的關聯，根據不同類型的關聯，定義了三類關聯特征因子gR（yi，yj）、gM（yi，yj）和gC（yi，yj）·gR（yi，yj）表示用戶之間由于存在的社會關系所定義的關聯特征函數，gM（yi，yj）是根據用戶之間存在的必須連接約束所定義的關聯特征函數，gC（yi，yj）是根據用戶之間存在的不能連接約束所定義的關聯特征函數，我們將gM（yi，yj）和gC（yi，yj）也稱為約束勢函數.

根據Hammersley-Clifford定理［25］，一個具體的社區標簽配置的概率能夠使用吉布斯分布［26］所表示，因此我們可以得到：

其中，α，β，γ分別表示特征函數gR，gM和gC所占的權重，Z1是歸一化因子，也稱為劃分函數（Partition function），其形式為：

同樣，λ表示特征函數f的權重，Z2是歸一化因子，其形式為：

根據貝葉斯理論，條件概率分布P（Y|V）可以表示為：

結合式（1）和（3），可以進一步得到：

其中，用θ=｛α，β，γ，λ｝表示所有參數的集合，Z是歸一化因子，可以表示為：

3.2因子函數定義

在給出模型的通用框架之后，我們進一步對模型中的因子函數進行定義.

我們針對網絡中的每條邊（yi，yj）定義一個邊特征函數gR（yi，yj），用于表示邊上的（即有關聯的）兩個節點選擇同一個社區的可能性.其取值不僅僅與用戶之間的關系權重有關，而且與每個用戶的鄰居個數有關，借鑒文獻［5］中對邊特征函數的定義，我們將其定義為：

其中1（·）是指示函數，即如果對應的條件滿足則函數取值為1，否則取0.其中ki是節點vi與所有鄰居的邊的總權重，即是節點vi的鄰居集合，m是網絡的總權重，即從定義可以看出，邊特征函數gR（yi，yj）具有如下直觀的含義：如果兩個節點之間的權值越大，且兩節點與它們各自鄰居的權重相對網絡的總權重越小，則兩節點屬于同一社區的概率越大.不難發現，gR（yi，yj）的定義事實上是借鑒了模塊度的定義.

對于先驗信息中的約束條件，我們定義了兩種關聯特征函數gM（yi，yj）和gC（yi，yj），借鑒Basu等［27］在使用隱馬爾科夫隨機場（Hidden Markov random field，HMRF）進行半監督聚類時選擇Potts勢［28］定義約束勢函數的方式，將gM（yi，yj）和gC（yi，yj）分別定義為：

其中?ij為用戶vi，vj在網絡中的距離，通常可以是最短路徑，本文使用隨機游走路徑，?max為網絡中的節點最大距離.本文在約束關聯特征函數中考慮了用戶之間的距離，因為如果兩個用戶距離很近，他們更可能屬于同一個社區，應該以更大的概率滿足必須連接約束條件，以及更小的概率滿足不能連接約束條件；反之亦然.因此對二者的定義正好可以確保社區劃分以更大的概率滿足約束條件.

根據模塊度的定義，通過將所有邊特征函數gR（yi，yj）的乘積最大化足以保證社區結構達到與模塊度最優化相同的最大顯著性，但是由于通過這種方式得到的各個社區之間并無差別，該算法并不能反映每個用戶的主體行為.因此，我們通過定義節點特征函數，描述了一個節點vi選擇加入某個社區的可能性，反映了用戶自身的主體性.代替考慮用戶與用戶所屬社區中的所有用戶的相似度，我們簡單地使用其相鄰用戶所屬于的社區來反映單個用戶的社區偏好：

從定義可以看出，節點具有更大的概率與其更親密的鄰居具有相同的社區標簽.我們注意到節點特征函數中的變量yi和|Xyi|的值應該直到整個網絡的社區劃分確定后才能被獲得，因此我們簡單地使用｛yi｝的中間結果計算節點特征函數.因此一旦yi和|Xyi|的值確定之后，節點特征函數都是常量.

3.3參數估計

接下來我們需要對模型中的參數θ=｛α，β，γ，λ｝進行評價.在我們的問題中，已知部分用戶的社區劃分，需要預測剩余用戶的社區劃分.我們需要通過整個網絡的結構，融合成對用戶之間的約束，部分用戶的社區標簽，來決定整個網絡的社區劃分.這里，我們使用Y|YL表示由部分用戶標簽推導而來的一個社區劃分，通過采用log最大似然估計方法，得到log似然目標函數l（θ），如式（12）所示.

最大化目標函數，便可以獲得估計的參數配

置θ?，即：

在本文中，我們采用梯度下降方法，對參數進行優化，參數的更新過程為：

其中，η為所有參數θ的迭代步長，以λ為例，針對目標函數求λ的偏導數，如式（15）所示.

為了計算梯度，需要計算邊緣概率分布 P（yi，yj|YL，V），P（yi|YL，V），P（yi，yj|V）和P（yi|V）.由于需要計算歸一化因子Z，使得計算精確的期望值非常困難.此外，模型中的圖結構是任意的，可能包含環路，因此本文選擇迭代信念傳播算法（Loopy belief propagation，LBP）［29］來近似計算梯度值.此外，我們針對每個用戶vi定義的節點特征因子f（yi），不僅僅取決于yi的值，而且與其相鄰的用戶的社區劃分以及vi所屬社區的大小相關，這就導致我們在計算f（yi）的時候需要整個網絡的社區劃分，但這是本文需要求解的問題，這兩者之間是矛盾的.針對這個問題，我們采取了一種近似方法.在模型訓練的初始階段，對于網絡中未知社區劃分的用戶，我們采用K最近鄰居方法，選擇與其距離最近的K個用戶的社區標簽，來決定用戶的初始社區劃分，然后計算每個用戶的節點特征因子f（yi），對于K值的選擇，通常根據網絡的規模、網絡的稀疏程度，以及已知社區劃分的用戶在網絡中的分布決定.而在使用LBP計算期望的每次迭代過程中，我們既使用Sum-product方法計算節點的邊緣概率P（yi，yj|YL，V），P（yi|YL，V），P（yi，yj|V）和P（yi|V），又使用Max-product計算整個網絡中隱變量的當前最佳配置Y?，從而得到中間階段整個網絡的社區劃分，然后重新計算每個用戶的節點特征因子f（yi），即每次迭代之后，f（yi）的值隨著社區劃分的改變而變化.參數估計的具體過程如算法1所示.

算法1.FG-SSCD模型的參數學習算法

輸入.社交網絡G=（V，E，A，Y），期望的社區集合L=｛l1，l2，···，lK｝，已知的用戶社區標簽YL，必須連接約束的集合M=｛（xi，xj）｝和不能連接約束的集合侵犯約束代價W 和以及學習速率η；

輸出.模型參數θ=｛α，β，γ，λ｝

算法步驟:

對于每個未知社區標簽的用戶，用K最近鄰居方法初始化社區標簽YU，計算f（yi）初始化θ

重復

1）使用LBP計算各個期望值

3）按照下式，使用學習效率η更新參數θ:

4）使用LBP計算未知社區劃分用戶的社區標簽YU，重新計算f（yi）

直至參數θ 取值收斂

3.4模型推理

接下來，根據學習所得到的參數θ，我們需要推斷每個未知社區標簽用戶的社區標簽，所采用的方法就是尋找使目標函數最大化的一個標簽配置，即：

這里我們需要再一次使用LBP算法，通過此算法計算出未知社區標簽用戶的社區標簽.通過計算邊緣分布函數P（yi|YL，V），然后取此邊緣分布函數取得最大值的變量值，作為未知社區標簽用戶的社區標簽，從而獲得社交網絡的最終社區劃分.

值得注意的是，雖然文章研究的問題的前提是兩種先驗信息之間不存在沖突，但是我們同時也考慮了更多的情況.對于兩種先驗信息，如果從一種直接可以推出另一種，或者說兩種數據提供的信息是等價的，表明此時存在信息冗余，我們僅僅利用類標簽信息；若二者存在沖突，表明此時存在噪聲數據，我們忽略所有相沖突的先驗信息.此外，分析我們的概率模型中加入的兩類先驗信息，對于已知的用戶社區標簽，因為是作為訓練的標記數據，最終得到的社區劃分一定符合這些信息；但對于必須連接和不能連接約束，通過定義約束勢函數，因為是盡量從概率的角度滿足約束，因此不能確保最終得到的社區劃分一定滿足這兩類約束條件.通過以上兩種方式，確保在我們的方法中，不會出現兩種先驗信息相互沖突的情況.

4　實驗分析

本文從兩個方面對提出的半監督社區發現方法進行評價，一個是考慮在具有噪聲的網絡中，評價本文提出的社區發現方法的魯棒性，另一個是與其他社區發現方法進行比較，展現本文提出方法的有效性.

4.1數據集

本文選擇了3個真實的數據集進行實驗，其中包括兩個較小的數據集-Zachary社會關系網絡和海豚關系網，以及一個大的數據集-DBLP協作網.這3個數據集都擁有清晰的社區結構，能夠方便對試驗結果進行驗證.

Zachary社會關系網是社交網絡分析領域中經常被用到的一個小型測試網絡.20世紀70年代，Wayne Zachary花了三年時間（1970～1972年）觀察美國一所大學空手道俱樂部成員間的社會關系，然后構造了一個俱樂部成員社會關系網（Zachary′s karate club network）.網絡中的每個節點代表一個俱樂部成員，如果兩個成員經常一起出現在俱樂部活動（如空手道訓練、俱樂部聚會等）之外的其他場合，代表在俱樂部之外他們可以被稱為朋友，則兩個成員之間存在連邊，整個網絡包含34個節點，78條邊.在調查過程中發現，因為俱樂部教練Mr.Hi（v1）與主管John A.（v34）之間的爭執，該俱樂部被分裂為了2個各自以他們為核心的小集團.Zachary社會關系網是常用于檢驗社團發現算法有效性的網絡［1，3，9］，該網絡真實社團結構如圖2所示，圖中不同顏色的節點代表分裂后的不同集團的成員.

海豚關系網也是社交網絡分析領域中常被使用到的一個真實網絡［30］.Lusseau等花了7年的時間，通過對新西蘭Doubtful Sound峽灣棲息的一個海豚群體（該群體由2個家族共62只寬吻海豚組成）進行觀察，構造了一個海豚關系網.網絡中的節點表示一個海豚，邊代表兩個海豚之間存在頻繁的接觸，最終的網絡包含了62個節點和159條邊.其真實社區結構如圖3所示，不同家族的海豚成員使用不同的顏色進行區分，較大的海豚家族擁有了42個成員節點，而較小的家族僅僅擁有20個節點.

圖2　Zachary網絡的真實社團結構Fig.2　Community structure of Zachary′s karate club network

圖3　海豚關系網的真實社團結構Fig.3　Community structure of dolphin social network

第三個是DBLP數據集，我們使用Yang等［31］提取的DBLP共同作者關系網絡，網絡中的兩個作者至少合作過一篇文章，則他們之間具有一條連邊.整個網絡包括317080個節點，1049866條邊，平均聚類系數為0.6324.數據集中包含了Ground-truth社區，節點被劃為13477個社區.數據能夠在斯坦福網絡分析平臺1被下載.

注意，在3個數據集中，根據已知的社區劃分設置我們的模型中期望的社區集合，即將社區個數設置為已知的社區標簽的數據.

4.2度量指標

為了度量社區發現的質量，我們選擇成對F-measure（Pairwise F-measure）［32］作為度量指標，Basu通過將信息領域中的F-measure引入到半監督聚類中，提出成對F-measure的定義，用來度量半監督聚類算法的質量.本文選擇成對F-measure來測試社區發現算法的質量.我們首先給出社區發現中的準確率和召回率的定義：

其中，Epred是預測到的社區內的節點對的集合，Esame是真實情況下社區內的節點對的集合，Ecorrect=Epred∩Esame是正確預測的在社區內的節點對的集合，因此我們可以得到成對F-measure的定義：

顯然F-measure越大，表示社區發現的預測結果越好.

4.3抗噪聲能力評價

大量的工作已經證明［1，3，6，8，30］，在網絡數據真實地反映了社交網絡中用戶之間真實關系的情況下，包括模塊度優化方法在內的很多社區發現方法都可以很好地發現網絡中的社區結構.但是通常情況下，真實的社交網絡中常常包含一些錯誤的或缺失的用戶關系，例如在Twitter和微博中，存在很多廣告用戶，相比真實用戶之間的關注關系，他們對真實用戶的關注有很大的區別，甚至可以當作噪聲連接；再如，在Facebook中，生活中親密的朋友可能并未在網絡中建立朋友關系，存在缺失的連邊，因此并未獲得完全的社會關系.在這些情況下，使得我們發現的社區常常難以反映網絡的真實社區結構.因此，在本小節中，我們希望在噪聲環境下，驗證通過融入先驗信息到社區發現中是否可以有效地提高預測的精度.

在實驗中，首先通過在真實的社交網絡中隨機地加入和刪除用戶關系，來增加噪聲，然后在各種噪聲比例下，通過加入不同程度的用戶引導信息，進行半監督的社區發現，進而比較不同情形下社區發現的F-measure值.對于先驗信息的融入，我們區分兩種情況，分別為僅僅考慮已知部分用戶社區標簽的情況，以及同時考慮已知部分用戶社區標簽和增加用戶約束的情況.下面我們首先在兩個網絡中，分別給出在幾種情況下進行半監督社區劃分的例子.

圖4（a）中給出了沒有噪聲的情況下，Zachary社會關系網絡中通過融合5個已知用戶（7、13、15、27和28）的社區標簽，使用我們的半監督社區發現方法FG-SSCD預測得到的社區劃分，得到的F-measure結果為0.9462，有1個節點（10號）產生了誤分.圖4（b）中是沒有噪聲的情況下，海豚社會網中通過融合5個已知用戶（14、22、31、37和50）的社區標簽，我們的半監督社區發現方法預測得到的社區劃分，F-measure得到的結果為0.9723，有2個節點（29號和40號）產生了誤分.

為了加入噪聲數據到網絡中，我們隨機選擇一定比例的節點對，如果它們之間沒有連接，我們使其產生連接，如果它們之間存在連接，則刪除這個連接.當在 Zachary網絡中加入5個噪聲數據（增加了5個新的連接（13，14）、（17，31）、（20，25）、（22，34）、（10，26）），加入5個已知類標簽（4，5，16，24，26），此外加入5個約束（必須連接約束：（5，17）、（4，22）、（16，29），不能連接約束：（14，33）、（7，25））的情況下，圖5（a）中給出了 FG-SSCD 模型獲得的社區劃分，得到的 F-measure結果為 0.9462，僅僅 1個節點（31號）產生了誤分.在海豚社會網中，當加入5個噪聲數據（增加了5個新的連接（3，24）、（9，37）、（14，46）、（28，52）、（47，62）），加 入5個 已 知 類 標 簽（7，17，44，46，60），此外加入10個約束（必須連接：（34，45）、（24，40）、（20，26）、（3，38）、（48，51）、（8，58）、（9，29），不能連接：（15，55）、（2，25）、（7，50））的情況下，FG-SSCD模型獲得的社區劃分如圖5（b）所示，F-measure為0.9432，有3個節點（40，47，54）產生了誤分.

圖4　FG-SSCD模型發現的社區結構（無噪聲）Fig.4　Community structure from FG-SSCD（without noise）

以上幾種情況下，不管有無噪聲數據，在兩個網絡中進行的半監督社區發現，都取得了較高的F-measure值，獲得了較好的社區發現結果.為了進一步驗證我們的半監督社區發現方法在噪聲環境下的有效性，我們選擇了兩種著名的無監督的社區發現算法進行對比，以驗證融入先驗信息對于社區發現的影響.

圖5　FG-SSCD模型發現的社區結構（有噪聲）Fig.5　Community structure from FG-SSCD（with noise）

1）快速Newman算法（Fast-Newman，FN）［8］，FN算法是Newman等提出的一種基于模塊度優化的貪婪算法.該算法是在使得模塊度不斷增加的基礎上進行，即每次合并沿著使模塊度增多最大和減小最少的方向進行.在Zachary和海豚社會網的實驗中，根據實際存在的社區個數，我們將FN算法的社區個數指定為2，而在DBLP中，最終社區個數根據模塊度最大值設置.

2）基于信息論的算法（Information-theoretic approach，IT）［33］，這種方法將社區發現過程轉化為一個信號通信過程.通過在信息過程中對網絡結構信息進行信號編碼和解碼，信息丟失最少時，編碼后得到的社區結構為最優的社區劃分.這種方法并沒有設定發現社區的個數.

我們將網絡中的噪聲比例分別設置為2%、4%、6%、8%、10%，由于我們的方法是隨機產生噪聲和先驗信息，因此我們在不同比例的噪聲環境下，選擇50次的平均結果作為實驗的最終結果進行比較.圖6中給出了不同噪聲比例下，分別執行FN和IT算法，以及融入不同比例的先驗信息的情況下通過FG-SSCD模型，得到的社區劃分實驗對比結果.從圖中可以看出，在Zachary和海豚社會網中，IT算法的性能顯著低于其他算法，這是因為IT并沒有預先設定社區個數.事實上，社區個數也是一種先驗信息，這從另一個側面也反映出先驗信息有利于提高社區發現的魯棒性.三個不同的網絡中，在無噪聲環境下，我們的方法通過融合先驗信息未必能獲得比FN算法更好的社區劃分.可是在添加噪聲數據之后，在不同的噪聲比例下，通過我們的方法，融合不同比例的先驗信息，都能顯著地提高社區發現的精度，而且先驗信息越多，得到的預測精度越高.因為現實世界的網絡中，通常都包含了大量的噪聲，因此通過融入先驗信息到社區發現中，能夠提高社區發現算法的魯棒性，發現的社區更能夠有效地揭示現實世界的網絡中的真實社區結構.

圖6　不同噪聲比例下的社區發現預測精度對比Fig.6　The prediction accuracy with different noise rate

4.4有效性評價

為了體現我們提出的半監督社區發現算法的有效性，我們選擇Eaton等最新提出的半監督的Spin-Glass模型［2］與我們的FG-SSCD模型進行對比，半監督的Spin-Glass模型既可以融入已知的節點社區劃分，又可以考慮節點之間的約束，在后面的內容中我們將其簡稱為Spin-Glass模型.由于在Eaton等的實驗中并沒有同時考慮兩種先驗信息，為了與FG-SSCD模型進行對比，在我們的實驗中同時將兩種信息融入到Spin-Glass模型中，這樣可以在考慮了相同的先驗信息的情況下將FG-SSCD模型與Spin-Glass模型的社區劃分結果進行對比.此外，Spin-Glass模型中的參數設置與文獻［2］相同，全部為1.

我們分別在三個網絡中，在設置不同的噪聲比例的情況下，對每一項實驗獨立重復50次，然后取F-measure的平均值，圖7給出了我們提出的半監督社區發現算法與半監督的Spin-Glass模型的比較結果.從圖中可以看出，在網絡中有噪聲的情況下，不管是Zachary網絡還是海豚社會網中，本文的結果一致優于Spin-Glass模型的社區發現結果.三個網絡中，本文算法得到的平均F-measure比Spin-Glass模型分別提高了6.34%、16.36%和12.13%.因為兩種半監督社區發現方法都融入了相同的先驗信息，相比Spin-Glass模型通過用戶的經驗知識設置參數以確定各類信息的權重，本文方法通過自動優化特征因子函數的權重，可以自動確定各種信息對于社區劃分的貢獻程度，有助于提高社區劃分的精度.

5　結論

本文研究了社區發現這一社交網絡分析中長期關注的問題，但當前大部分的研究都聚焦在如何在網絡中自動發現社區的問題，在大量具有數據缺失或噪聲的網絡中，自動社區發現方法往往難以發現網絡中的真實社區結構.而通過在社區發現中融合先驗信息，進行半監督的社區發現，可以有效地提高社交網絡中社區發現的預測精度.在本文中，基于因子圖模型，通過融入先驗信息到一個統一的概率框架中，本文提出一種半監督的社區發現模型-FGSSCD模型，研究具有用戶引導情況下的社交網絡社區發現問題.在三個真實的社交網絡數據中進行實驗，實驗表明通過融入先驗信息可以有效地提高社區發現的精度.另外，與一種最新的半監督社區方法（半監督的Spin-Glass模型）進行對比，實驗結果顯示我們的FG-SSCD模型可以實現更好的社區劃分.

圖7　不同噪聲比例下，與Spin-Glass模型相比較，FG-SSCD模型F-measure值提高的比例Fig.7　The percent improvement in F-measure of our approach against Spin-Glass model with different noise rate

References

1 Fortunato S.Community detection in graphs.Physics Reports，2010，486（3-5）:75-174

2 Eaton E，Mansbach R.A spin-glass model for semisupervised community detection.In:Proceedings of the 26th AAAI Conference on Artificial Intelligence.Toronto，Ontario，Canada:AAAI，2012:900-906

3 Newman M E J，Girvan M.Finding and evaluating community structure in networks.Physical Review E，2004，69（2）: 026113-1-026113-15

4 Good B H，De Montjoye Y A，Clauset A.Performance of modularity maximization in practical contexts.Physical Review E，2010，81（4）:046106-1-046106-19

5 Yang Z，Tang J，Li J Z，Yang W J.Social community analysis via a factor graph model.IEEE Intelligent Systems，2011，26（3）:58-65

6 Girvan M，Newman M E J.Community structure in social and biological networks.Proceedings of the National Academy of Sciences of the United States of America，2002，99（12）:7821-7826

7 Brandes U，Delling D，Gaertler M，Gorke R，Hoefer M，Nikoloski Z，Wagner D.On modularity clustering.IEEE Transactions on Knowledge and Data Engineering，2008，20（2）:172-188

8 Newman M E J.Fast algorithm for detecting community structure in networks.Physical Review E，2004，69（6）: 066133

9 Duch J，Arenas A.Community detection in complex networks using extremal optimization.Physical Review E，2005，72（2）:027104

11 White S，Smyth P.A spectral clustering approach to finding communities in graph.In:Proceedings of the 2005 International Conference on Data Mining.New York，USA:IEEE，2005，5:76-84

14 Shen H W，Cheng X Q，Fang B X.Covariance，correlation matrix，and the multiscale community structure of networks. Physical Review E，2010，82（1）:016114-1-016114-9

17 Mucha P J，Richardson T，Macon K，Porter M A，Onnela JP.Community structure in time-dependent，multiscale，and multiplex networks.Science，2010，328（5980）:876-878

18 Ma X K，Gao L，Yong X R，Fu L D.Semi-supervised clustering algorithm for community structure detection in complex networks.Physica A:Statistical Mechanics and its Applications，2010，389（1）:187-197

19 Allahverdyan A E，Ver Steeg G，Galstyan A.Community detection with and without prior information.EPL（Europhysics Letters），2010，90（1）:983-995

20 Liu D，Liu X，Wang W J，Bai H Y.Semi-supervised community detection based on discrete potential theory.Physica A:Statistical Mechanics and its Applications，2014，416: 173-182

21 Li L，Du M，Liu G F，Hu X G，Wu G Q.Extremal optimization-based semi-supervised algorithm with conflict pairwise constraints for community detection.In:Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.New York，USA:IEEE，2014.180-187

22 Yang L，Cao X C，Jin D，Wang X，Meng D.A unified semi-supervised community detection framework using latent space graph regularization.IEEE Transactions on Cybernetics，2014，45（11）:2585-2598

23 Yang L，Jin D，Wang X，Cao X C.Active link selection for efficient semi-supervised community detection.Scientific Reports，2015，5:9039-1-9039-12

24 Tang W B，Zhuang H L，Tang J.Learning to infer social ties in large networks.Machine Learning and Knowledge Discovery in Databases.Berlin Heidelberg:Springer，2011，6913: 381-397

25 Hammersley J M，Clifford P.Markov fields on finite graphs and lattices.1971.

26 Geman S，Geman D.Stochastic relaxation，Gibbs distributions，and the Bayesian restoration of images.IEEE Transactions on Pattern Analysis and Machine Intelligence，1984，6（6）:721-741

27 Basu S，Bilenko M，Mooney R J.A probabilistic framework for semi-supervised clustering.In:Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York，USA:ACM，2004.59-68

29 Murphy K P，Weiss Y，Jordan M I.Loopy belief propagation for approximate inference:an empirical study.In:Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence.San Francisco，CA，USA:Morgan Kaufmann Publishers Inc.，1999.467-475

30 Lusseau D，Schneider K，Boisseau O J，Haase P，Slooten E，Dawson S M.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations.Behavioral Ecology and Sociobiology，2003，54（4）: 396-405

31 Yang J，Leskovec J.Defining and evaluating network communities based on ground-truth.Knowledge and Information Systems，2015，42（1）:181-213

32 Basu S.Semi-supervised Clustering:Probabilistic Models，Algorithms and Experiments［Ph.D.dissertation］，University of Texas at Austin，USA，2005.

33 Rosvall M，Bergstrom C T.An information-theoretic framework for resolving community structure in complex networks.Proceedings of the National Academy of Sciences of the United States of America，2007，104（18）:7327-7331

黃立威北京市遙感信息研究所工程師. 2014年獲得解放軍理工大學指揮信息系統學院博士學位.主要研究方向為數據挖掘和機器學習.本文通信作者.

E-mail:dr_huanglw@163.com

（HUANG Li-WeiEngineer at Beijing Institute of Remote Sensing.He received his Ph.D.degree in computer science from PLA University of Science and Technology in 2014.His research interest covers data mining and machine learning.Corresponding author of this paper.）

李彩萍北京市遙感信息研究所高級工程師.2015年獲得裝備學院博士學位.主要研究方向為系統仿真.

E-mail:alninglcp@sina.com

（LI Cai-PingSenior engineer at Beijing Institute of Remote Sensing. She received her Ph.D.degree from PLA Institute of Equipment in 2015. Her main research interest is system simulation.）

張海粟中國人民解放軍國防信息學院副教授.2012年獲得解放軍理工大學博士學位.主要研究方向為數據挖掘.

E-mail:zhanghaisu@139.com

（ZHANG Hai-SuAssociate professor at the Institute of National Defense Information.He received his Ph.D. degree in computer science from PLA University of Science and Technology in 2012.His main research interest is data mining.）

劉玉超中國指揮與控制學會副秘書長. 2012年獲得清華大學計算機科學與技術系博士學位.主要研究方向為數據挖掘和機器學習.

E-mail:yuchao_liu@163.com

（LIU Yu-ChaoDeputy secretarygeneral at Chinese Institute of Command and Control.He received his Ph.D.degree from the Department of Computer Science and Technology，Tsinghua University in 2012.His research interest covers data mining and machine learning.）

李德毅中國電子系統工程研究所研究員.中國工程院院士.國際歐亞科學院院士.1983年獲得英國愛丁堡Heriot-Watt大學博士學位.主要研究方向為人工智能.E-mail:lidy@cae.cn

（LI De-YiProfessor at the Institute of Electronic System Engineering.He is currently an academician of Chinese Academy of Engineering，a member of the International Eurosian Academy of Science.He received his Ph.D.degree in computer science from Heriot-Watt University in Edinburgh，UK.His main research interest is artificial intelligence.）

劉艷博北京市遙感信息研究所工程師. 2013年獲得國防科技大學碩士學位.主要研究方向為遙感信息應用.

E-mail:liuyanbonudt@163.com

（LIU Yan-BoEngineer at Beijing Institute of Remote Sensing.She received her master degree in automation from National University of Defense Technology.Her main research interest is remote sensing information application.）

A Semi-supervised Community Detection Method Based on Factor Graph Model

HUANG Li-Wei1LI Cai-Ping1ZHANG Hai-Su2LIU Yu-Chao3LI De-Yi4LIU Yan-Bo1

Community detection is an important research direction of social network analysis.Most of the current studies focused on automated community detection.However，in networks having missing data or noise，the ability for an automated community detection algorithm to discover true community structures may degrade rapidly with the increase of noise.On the other hand，semi-supervised community detection provides a feasible way for solving the above problem by incorporating priori information into the community detection process.In this paper，based on the factor graph model，by incorporating the priori information into a unified probabilistic framework，we propose a factor graph-based semisupervised community detection method.We evaluate the method with three different genres of real datasets（Zachary，Dolphins and DBLP）.Experiments indicate that incorporating priori information into the community detection process can improve the prediction accuracy significantly.Compared with a latest semi-supervised community detection algorithm（semi-supervised spin-glass model），the F-measure of our method is on average improved by 6.34%，16.36%and 12.13% in the three datasets.

Social networks，semi-supervised community detection，factor graph，social networks analysis，probability reasoning

Manuscript May 5，2015；accepted January 19，2016

10.16383/j.aas.2016.c150261

Huang Li-Wei，Li Cai-Ping，Zhang Hai-Su，Liu Yu-Chao，Li De-Yi，Liu Yan-Bo.A semi-supervised community detection method based on factor graph model.Acta Automatica Sinica，2016，42（10）:1520-1531

2015-05-05錄用日期2016-01-19

國家重點基礎研究發展計劃（973計劃）（2014CB340401），國家自然科學基金（61035004，61273213，61305055）資助

Supported by National Basic Research Program of China（973 Program）（2014CB340401），National Natural Science Foundation of China（61035004，61273213，61305055）

本文責任編委周志華

Recommended by Associate Editor ZHOU Zhi-Hua

1.北京市遙感信息研究所北京1008542.中國人民解放軍國防信息學院武漢4300103.中國指揮與控制學會北京1000484.中國電子系統工程研究所北京100039

1.Beijing Institute of Remote Sensing，Beijing 100854 2.Institute of National Defense Information，Wuhan 430010 3.Chinese Institute of Command and Control，Beijing 100048 4.Institute of Electronic System Engineering，Beijing 100039