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

一種基于因子圖模型的半監(jiān)督社區(qū)發(fā)現(xiàn)方法

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

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

社交網(wǎng)絡(luò)，半監(jiān)督社區(qū)發(fā)現(xiàn)，因子圖，社交網(wǎng)絡(luò)分析，概率推理

引用格式黃立威，李彩萍，張海粟，劉玉超，李德毅，劉艷博.一種基于因子圖模型的半監(jiān)督社區(qū)發(fā)現(xiàn)方法.自動(dòng)化學(xué)報(bào)，2016，42（10）:1520-1531

社交網(wǎng)絡(luò)中，用戶由于共同的興趣和特征結(jié)成群體，群體體現(xiàn)了關(guān)系的局部聚集特性.在網(wǎng)絡(luò)科學(xué)研究中，人們把用戶視為節(jié)點(diǎn)，關(guān)系視為邊，群體視為社區(qū)［1］.社區(qū)通常由功能相近或性質(zhì)相似的網(wǎng)絡(luò)節(jié)點(diǎn)組成，在一定程度上反映了用戶自發(fā)、無(wú)序行為背后的局部弱規(guī)則性和全局有序性.對(duì)社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)的深入研究不僅有助于揭示相對(duì)獨(dú)立而又相互關(guān)聯(lián)的社區(qū)如何形成錯(cuò)綜復(fù)雜的社交網(wǎng)絡(luò)，幫助人們更好地理解系統(tǒng)在不同層次上的結(jié)構(gòu)和功能特性，而且具有很多的實(shí)用價(jià)值，例如通過(guò)發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)揭示具有共同興趣或相似社會(huì)背景的社會(huì)團(tuán)體.因此，社區(qū)發(fā)現(xiàn)已成為社交網(wǎng)絡(luò)分析領(lǐng)域中一個(gè)非常重要的研究方向.

目前大部分社區(qū)發(fā)現(xiàn)的研究都是面向自動(dòng)社區(qū)發(fā)現(xiàn)問(wèn)題，即根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)，通過(guò)算法自動(dòng)地發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)，是一種無(wú)監(jiān)督的方法.但自動(dòng)的社區(qū)發(fā)現(xiàn)通常存在兩個(gè)重要的問(wèn)題：

1）在面對(duì)具有鏈路缺失或具有噪聲數(shù)據(jù)的網(wǎng)絡(luò)時(shí)，自動(dòng)社區(qū)發(fā)現(xiàn)的性能會(huì)大大下降［2］，很難有效地揭示網(wǎng)絡(luò)中的真實(shí)社區(qū)結(jié)構(gòu)；

2）類(lèi)似于流行的模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)方法［3］，通過(guò)近似優(yōu)化方法最大化模塊度來(lái)發(fā)現(xiàn)社區(qū)，通常得不到最優(yōu)的社區(qū)劃分［4］.

導(dǎo)致第一個(gè)問(wèn)題的原因通常是，社區(qū)發(fā)現(xiàn)的時(shí)候僅僅考慮了當(dāng)前的網(wǎng)絡(luò)信息，其前提是將網(wǎng)絡(luò)作為一個(gè)正確的、完全的網(wǎng)絡(luò)處理，但通常情況下，我們獲得的網(wǎng)絡(luò)包含了大量包括錯(cuò)誤連接在內(nèi)的噪聲數(shù)據(jù)，網(wǎng)絡(luò)連接通常也是不完全的.在這樣的情況下，即使最好的自動(dòng)社區(qū)發(fā)現(xiàn)方法在遇到具有噪聲的網(wǎng)絡(luò)時(shí)其性能也會(huì)急劇下降.第二個(gè)問(wèn)題是由于通過(guò)優(yōu)化方法最大化模塊度得到的是一個(gè)近似解，導(dǎo)致發(fā)現(xiàn)的社區(qū)是多種多樣的，即使模塊度的值差得很小，也可能導(dǎo)致差異非常大的社區(qū)劃分，不能得到一個(gè)最優(yōu)的劃分結(jié)果，也很難發(fā)現(xiàn)特定情境下滿足特定需求的社區(qū)結(jié)構(gòu).

在數(shù)據(jù)挖掘領(lǐng)域，針對(duì)具體的任務(wù)，往往會(huì)考慮加入用戶引導(dǎo)或約束到挖掘任務(wù)中，提高數(shù)據(jù)挖掘的性能.事實(shí)上，在社交網(wǎng)絡(luò)環(huán)境下，已知部分社區(qū)劃分信息的情況也普遍存在，例如我們可能已知部分用戶屬于某一個(gè)社區(qū)，或者已知兩個(gè)用戶屬于相同或不同的社區(qū).通過(guò)將這些信息融入到社區(qū)劃分中，進(jìn)行半監(jiān)督的社區(qū)發(fā)現(xiàn)，往往可以有效提高社區(qū)劃分的準(zhǔn)確度，提高噪聲環(huán)境下社區(qū)劃分的魯棒性，而且還能幫助發(fā)現(xiàn)滿足特定需求的社區(qū)劃分.

在本文中，我們針對(duì)兩種類(lèi)型的先驗(yàn)信息，即已知部分節(jié)點(diǎn)的社區(qū)劃分以及用戶之間存在的成對(duì)的必須連接約束（Must-link constraints）和不能連接約束（Cannot-link constraints），研究半監(jiān)督社區(qū)發(fā)現(xiàn)問(wèn)題，提出了一種基于因子圖模型的半監(jiān)督社區(qū)發(fā)現(xiàn)方法，將原始的社交網(wǎng)絡(luò)與兩種先驗(yàn)信息融合到一個(gè)統(tǒng)一的半監(jiān)督概率框架中，既可以使得發(fā)現(xiàn)的社區(qū)滿足先驗(yàn)條件，又可以符合網(wǎng)絡(luò)的整體社區(qū)結(jié)構(gòu).本文提出的模型具有高的適應(yīng)性，因?yàn)橥ㄟ^(guò)定義更高階的因子特征函數(shù)，我們可以將兩個(gè)以上節(jié)點(diǎn)之間的約束融合到社區(qū)發(fā)現(xiàn)問(wèn)題中.文獻(xiàn)［5］研究了利用因子圖模型進(jìn)行社區(qū)發(fā)現(xiàn)的問(wèn)題，但并沒(méi)有考慮先驗(yàn)信息.據(jù)我們所能得到的信息，本文是第一次從概率推理的視角研究半監(jiān)督社區(qū)發(fā)現(xiàn)問(wèn)題，或許能夠?yàn)槲覀冞M(jìn)一步探索社區(qū)發(fā)現(xiàn)的不確定性提供一些有用的啟發(fā).

1　相關(guān)工作

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

目前模塊度優(yōu)化方法已成為復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的基準(zhǔn)方法，并得到廣泛的應(yīng)用.然而，進(jìn)一步的研究發(fā)現(xiàn)模塊度優(yōu)化方法在處理各種具體網(wǎng)絡(luò)時(shí)存在一些問(wèn)題：1）文獻(xiàn)［12］發(fā)現(xiàn)由于隨機(jī)波動(dòng)模塊度方法中所采用的參照網(wǎng)絡(luò)也會(huì)呈現(xiàn)出偽社區(qū)結(jié)構(gòu)，從而對(duì)模塊度方法中采用參照網(wǎng)絡(luò)提出了質(zhì)疑，并基于統(tǒng)計(jì)顯著性給出了相應(yīng)的改進(jìn)辦法；2）文獻(xiàn)［13］指出對(duì)于給定的網(wǎng)絡(luò)，模塊度優(yōu)化方法存在一個(gè)固有的分辨率，使得模塊度優(yōu)化方法不能識(shí)別出該分辨率以下的社區(qū)，這就是所謂的“分辨率限制”問(wèn)題.因此，小社區(qū)往往會(huì)被大的社區(qū)吸納，從而淹沒(méi)在大的網(wǎng)絡(luò)社區(qū)中而無(wú)法被識(shí)別出來(lái)；3）文獻(xiàn)［14］發(fā)現(xiàn)模塊度優(yōu)化方法不能很好地處理節(jié)點(diǎn)度分布高度差異的網(wǎng)絡(luò)，而真實(shí)網(wǎng)絡(luò)中的節(jié)點(diǎn)度分布往往服從冪率分布，研究通過(guò)引入尺度（Rescaling）變換解決了該問(wèn)題.

進(jìn)一步的研究表現(xiàn)，真實(shí)世界中的網(wǎng)絡(luò)社區(qū)之間普遍存在重疊節(jié)點(diǎn)，這些節(jié)點(diǎn)在不同社區(qū)間起著橋梁作用，在社區(qū)中發(fā)揮著重要影響，是社區(qū)間信息擴(kuò)散的媒介和社區(qū)演化的推手.鑒于這個(gè)問(wèn)題，人們開(kāi)始著眼于重疊社區(qū)結(jié)構(gòu)的研究.最初，Palla等在Nature上發(fā)表論文［15］，指出了社區(qū)重疊這一重要現(xiàn)象，并提出了一種基于完全子圖滲流（Clique percolation）的重疊社區(qū)發(fā)現(xiàn)方法.隨后，該算法被擴(kuò)展應(yīng)用到有向網(wǎng)絡(luò)、有權(quán)網(wǎng)絡(luò)和二部網(wǎng)絡(luò)等.直到現(xiàn)在，完全子圖滲流算法依然是重疊社區(qū)發(fā)現(xiàn)研究中應(yīng)用最為廣泛的方法之一.

社區(qū)演化是社區(qū)發(fā)現(xiàn)研究中的另一個(gè)重要問(wèn)題.演化是真實(shí)網(wǎng)絡(luò)所具有的基本特性，社區(qū)演化是網(wǎng)絡(luò)自身結(jié)構(gòu)和在其上頻繁發(fā)生的交互過(guò)程相互作用的結(jié)果.社區(qū)演化分析主要研究社區(qū)隨時(shí)間變化的情況，并分析導(dǎo)致社區(qū)演化的原因以及內(nèi)在的機(jī)制.文獻(xiàn)［16］基于他們提出的完全子圖滲流社區(qū)發(fā)現(xiàn)方法研究社區(qū)演化，得到一個(gè)有趣的結(jié)論：小社區(qū)的穩(wěn)定性是保證其存在的前提，而大社區(qū)的動(dòng)態(tài)性是其存在的基礎(chǔ).文獻(xiàn)［17］通過(guò)擴(kuò)展模塊度研究異構(gòu)關(guān)系網(wǎng)絡(luò)中隨時(shí)間演化的、多尺度社區(qū)結(jié)構(gòu).更多社區(qū)發(fā)現(xiàn)的研究可以參考文獻(xiàn)［1］.

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

2　問(wèn)題定義

為了融合先驗(yàn)信息到社區(qū)發(fā)現(xiàn)中，我們基于因子圖模型，對(duì)社交網(wǎng)絡(luò)中的半監(jiān)督社區(qū)發(fā)現(xiàn)問(wèn)題進(jìn)行建模，提出一種基于因子圖的半監(jiān)督社區(qū)發(fā)現(xiàn)方法（Factor graph-based semi-supervised community detection，F(xiàn)G-SSCD）.為了更清晰地對(duì)問(wèn)題進(jìn)行描述，首先我們給出社區(qū)發(fā)現(xiàn)的定義：

定義1（社區(qū)發(fā)現(xiàn)）.給定社交網(wǎng)絡(luò)G=（V，E，A，Y）以及期望的社區(qū)集合L=｛l1，l2，···，lK｝，其中V是所有用戶的集合，|V|=N，E?V×V是所有用戶關(guān)系的集合，A是網(wǎng)絡(luò)對(duì)應(yīng)的鄰接矩陣，Y是所有用戶的社區(qū)標(biāo)簽，在一般的社區(qū)劃分問(wèn)題中，它在初始階段是未知的，L表示所有社區(qū)標(biāo)簽集合.社區(qū)發(fā)現(xiàn)的目標(biāo)是為每個(gè)用戶vi確定其社區(qū)標(biāo)簽yi，yi∈｛l1，l2，···，lK｝，表示vi屬于的社區(qū).

在半監(jiān)督社區(qū)發(fā)現(xiàn)問(wèn)題中，通?？紤]兩種形式的先驗(yàn)知識(shí)：1）已知部分節(jié)點(diǎn)的社區(qū)標(biāo)簽；2）成對(duì)節(jié)點(diǎn)之間的必須連接和不能連接約束.在兩種先驗(yàn)信息之間不存在沖突的前提下，本文研究的問(wèn)題是如何同時(shí)考慮這兩種信息，將其融入到一個(gè)統(tǒng)一的概率模型中，引導(dǎo)我們進(jìn)行半監(jiān)督社區(qū)劃分.因此可以給出本文研究的半監(jiān)督社區(qū)發(fā)現(xiàn)問(wèn)題的定義.

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

此外，針對(duì)每個(gè)社區(qū)lk存在一個(gè)變量集合Xk，用于表示社區(qū)lk中的用戶集合.

3　基于因子圖模型的半監(jiān)督社區(qū)發(fā)現(xiàn)方法

3.1模型建立

在本節(jié)中，考慮融合先驗(yàn)信息到社區(qū)劃分問(wèn)題中，借鑒Tang等［24］提出的部分因子圖模型的思想，建立一個(gè)基于因子圖的半監(jiān)督社區(qū)發(fā)現(xiàn)模型FGSSCD，將半監(jiān)督的社區(qū)發(fā)現(xiàn)問(wèn)題建模到一個(gè)統(tǒng)一的框架中.

本文接下來(lái)給出FG-SSCD模型的一個(gè)簡(jiǎn)單例子.如圖1所示，左側(cè)的圖展示了一個(gè)網(wǎng)絡(luò)示例，包含了5個(gè)用戶｛v1，v2，···，v5｝以及相應(yīng)的社會(huì)關(guān)系.右側(cè)的圖是由左側(cè)的網(wǎng)絡(luò)作為輸入所建立的FG-SSCD模型，圖中觀測(cè)變量是網(wǎng)絡(luò)中給定的用戶｛v1，v2，···，v5｝，模型的隱變量即每個(gè)用戶的社區(qū)標(biāo)簽｛y1，y2，···，y5｝，假設(shè)整個(gè)網(wǎng)絡(luò)中的用戶劃分為兩個(gè)社區(qū)，即社區(qū)標(biāo)簽為｛1，2｝，網(wǎng)絡(luò)中已知用戶v1，v2，v5的社區(qū)標(biāo)簽，分別為1，1，2，需要預(yù)測(cè)用戶v3，v4的社區(qū)劃分.為了對(duì)模型進(jìn)行更加清晰的描述，下面對(duì)模型的基本要素分別進(jìn)行詳細(xì)介紹：

圖1　FG-SSCD模型的圖結(jié)構(gòu)Fig.1　Graphical structure of FG-SSCD

1）變量節(jié)點(diǎn)

模型中包含了兩類(lèi)變量節(jié)點(diǎn)，分別為：隱變量和觀測(cè)變量.

隱變量節(jié)點(diǎn)：模型中包含一個(gè)隱變量的集合｛y1，y2，···，yn｝，是不能直接觀測(cè)到的，在圖中用白色的圓圈表示，代表每個(gè)用戶vi的社區(qū)標(biāo)簽，是問(wèn)題需要預(yù)測(cè)的值.

觀測(cè)變量節(jié)點(diǎn)：模型中包含一個(gè)觀測(cè)變量的集合｛v1，v2，···，vn｝，在圖中用灰色的圓圈表示，每一個(gè)觀測(cè)變量由條件概率分布P（vi|yi）所產(chǎn)生，在模型中，當(dāng)給定社區(qū)劃分的情況下，隨機(jī)變量V的產(chǎn)生是條件獨(dú)立的，即

2）因子節(jié)點(diǎn)

根據(jù)用戶自身的特征，用戶之間存在的社會(huì)關(guān)系以及在社區(qū)發(fā)現(xiàn)中的約束，可以在模型中定義相關(guān)的因子函數(shù)：

節(jié)點(diǎn)特征因子：f（yi）是定義在單個(gè)隱變量上的節(jié)點(diǎn)特征因子，其表示在給定節(jié)點(diǎn)社區(qū)標(biāo)簽yi產(chǎn)生觀測(cè)數(shù)據(jù)vi的概率P（vi|yi）.

關(guān)聯(lián)特征因子：g（yi，yj）是定義在節(jié)點(diǎn)對(duì)之間的關(guān)聯(lián)特征因子，反映了隱變量之間存在的關(guān)聯(lián)，在本文模型中，僅僅考慮了成對(duì)的關(guān)聯(lián)，根據(jù)不同類(lèi)型的關(guān)聯(lián)，定義了三類(lèi)關(guān)聯(lián)特征因子gR（yi，yj）、gM（yi，yj）和gC（yi，yj）·gR（yi，yj）表示用戶之間由于存在的社會(huì)關(guān)系所定義的關(guān)聯(lián)特征函數(shù)，gM（yi，yj）是根據(jù)用戶之間存在的必須連接約束所定義的關(guān)聯(lián)特征函數(shù)，gC（yi，yj）是根據(jù)用戶之間存在的不能連接約束所定義的關(guān)聯(lián)特征函數(shù)，我們將gM（yi，yj）和gC（yi，yj）也稱為約束勢(shì)函數(shù).

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

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

同樣，λ表示特征函數(shù)f的權(quán)重，Z2是歸一化因子，其形式為：

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

結(jié)合式（1）和（3），可以進(jìn)一步得到：

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

3.2因子函數(shù)定義

在給出模型的通用框架之后，我們進(jìn)一步對(duì)模型中的因子函數(shù)進(jìn)行定義.

我們針對(duì)網(wǎng)絡(luò)中的每條邊（yi，yj）定義一個(gè)邊特征函數(shù)gR（yi，yj），用于表示邊上的（即有關(guān)聯(lián)的）兩個(gè)節(jié)點(diǎn)選擇同一個(gè)社區(qū)的可能性.其取值不僅僅與用戶之間的關(guān)系權(quán)重有關(guān)，而且與每個(gè)用戶的鄰居個(gè)數(shù)有關(guān)，借鑒文獻(xiàn)［5］中對(duì)邊特征函數(shù)的定義，我們將其定義為：

其中1（·）是指示函數(shù)，即如果對(duì)應(yīng)的條件滿足則函數(shù)取值為1，否則取0.其中ki是節(jié)點(diǎn)vi與所有鄰居的邊的總權(quán)重，即是節(jié)點(diǎn)vi的鄰居集合，m是網(wǎng)絡(luò)的總權(quán)重，即從定義可以看出，邊特征函數(shù)gR（yi，yj）具有如下直觀的含義：如果兩個(gè)節(jié)點(diǎn)之間的權(quán)值越大，且兩節(jié)點(diǎn)與它們各自鄰居的權(quán)重相對(duì)網(wǎng)絡(luò)的總權(quán)重越小，則兩節(jié)點(diǎn)屬于同一社區(qū)的概率越大.不難發(fā)現(xiàn)，gR（yi，yj）的定義事實(shí)上是借鑒了模塊度的定義.

對(duì)于先驗(yàn)信息中的約束條件，我們定義了兩種關(guān)聯(lián)特征函數(shù)gM（yi，yj）和gC（yi，yj），借鑒Basu等［27］在使用隱馬爾科夫隨機(jī)場(chǎng)（Hidden Markov random field，HMRF）進(jìn)行半監(jiān)督聚類(lèi)時(shí)選擇Potts勢(shì)［28］定義約束勢(shì)函數(shù)的方式，將gM（yi，yj）和gC（yi，yj）分別定義為：

其中?ij為用戶vi，vj在網(wǎng)絡(luò)中的距離，通?？梢允亲疃搪窂?，本文使用隨機(jī)游走路徑，?max為網(wǎng)絡(luò)中的節(jié)點(diǎn)最大距離.本文在約束關(guān)聯(lián)特征函數(shù)中考慮了用戶之間的距離，因?yàn)槿绻麅蓚€(gè)用戶距離很近，他們更可能屬于同一個(gè)社區(qū)，應(yīng)該以更大的概率滿足必須連接約束條件，以及更小的概率滿足不能連接約束條件；反之亦然.因此對(duì)二者的定義正好可以確保社區(qū)劃分以更大的概率滿足約束條件.

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

從定義可以看出，節(jié)點(diǎn)具有更大的概率與其更親密的鄰居具有相同的社區(qū)標(biāo)簽.我們注意到節(jié)點(diǎn)特征函數(shù)中的變量yi和|Xyi|的值應(yīng)該直到整個(gè)網(wǎng)絡(luò)的社區(qū)劃分確定后才能被獲得，因此我們簡(jiǎn)單地使用｛yi｝的中間結(jié)果計(jì)算節(jié)點(diǎn)特征函數(shù).因此一旦yi和|Xyi|的值確定之后，節(jié)點(diǎn)特征函數(shù)都是常量.

3.3參數(shù)估計(jì)

接下來(lái)我們需要對(duì)模型中的參數(shù)θ=｛α，β，γ，λ｝進(jìn)行評(píng)價(jià).在我們的問(wèn)題中，已知部分用戶的社區(qū)劃分，需要預(yù)測(cè)剩余用戶的社區(qū)劃分.我們需要通過(guò)整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)，融合成對(duì)用戶之間的約束，部分用戶的社區(qū)標(biāo)簽，來(lái)決定整個(gè)網(wǎng)絡(luò)的社區(qū)劃分.這里，我們使用Y|YL表示由部分用戶標(biāo)簽推導(dǎo)而來(lái)的一個(gè)社區(qū)劃分，通過(guò)采用log最大似然估計(jì)方法，得到log似然目標(biāo)函數(shù)l（θ），如式（12）所示.

最大化目標(biāo)函數(shù)，便可以獲得估計(jì)的參數(shù)配

置θ?，即：

在本文中，我們采用梯度下降方法，對(duì)參數(shù)進(jìn)行優(yōu)化，參數(shù)的更新過(guò)程為：

其中，η為所有參數(shù)θ的迭代步長(zhǎng)，以λ為例，針對(duì)目標(biāo)函數(shù)求λ的偏導(dǎo)數(shù)，如式（15）所示.

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

算法1.FG-SSCD模型的參數(shù)學(xué)習(xí)算法

輸入.社交網(wǎng)絡(luò)G=（V，E，A，Y），期望的社區(qū)集合L=｛l1，l2，···，lK｝，已知的用戶社區(qū)標(biāo)簽YL，必須連接約束的集合M=｛（xi，xj）｝和不能連接約束的集合侵犯約束代價(jià)W 和以及學(xué)習(xí)速率η；

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

算法步驟:

對(duì)于每個(gè)未知社區(qū)標(biāo)簽的用戶，用K最近鄰居方法初始化社區(qū)標(biāo)簽YU，計(jì)算f（yi）初始化θ

重復(fù)

1）使用LBP計(jì)算各個(gè)期望值

3）按照下式，使用學(xué)習(xí)效率η更新參數(shù)θ:

4）使用LBP計(jì)算未知社區(qū)劃分用戶的社區(qū)標(biāo)簽YU，重新計(jì)算f（yi）

直至參數(shù)θ 取值收斂

3.4模型推理

接下來(lái)，根據(jù)學(xué)習(xí)所得到的參數(shù)θ，我們需要推斷每個(gè)未知社區(qū)標(biāo)簽用戶的社區(qū)標(biāo)簽，所采用的方法就是尋找使目標(biāo)函數(shù)最大化的一個(gè)標(biāo)簽配置，即：

這里我們需要再一次使用LBP算法，通過(guò)此算法計(jì)算出未知社區(qū)標(biāo)簽用戶的社區(qū)標(biāo)簽.通過(guò)計(jì)算邊緣分布函數(shù)P（yi|YL，V），然后取此邊緣分布函數(shù)取得最大值的變量值，作為未知社區(qū)標(biāo)簽用戶的社區(qū)標(biāo)簽，從而獲得社交網(wǎng)絡(luò)的最終社區(qū)劃分.

值得注意的是，雖然文章研究的問(wèn)題的前提是兩種先驗(yàn)信息之間不存在沖突，但是我們同時(shí)也考慮了更多的情況.對(duì)于兩種先驗(yàn)信息，如果從一種直接可以推出另一種，或者說(shuō)兩種數(shù)據(jù)提供的信息是等價(jià)的，表明此時(shí)存在信息冗余，我們僅僅利用類(lèi)標(biāo)簽信息；若二者存在沖突，表明此時(shí)存在噪聲數(shù)據(jù)，我們忽略所有相沖突的先驗(yàn)信息.此外，分析我們的概率模型中加入的兩類(lèi)先驗(yàn)信息，對(duì)于已知的用戶社區(qū)標(biāo)簽，因?yàn)槭亲鳛橛?xùn)練的標(biāo)記數(shù)據(jù)，最終得到的社區(qū)劃分一定符合這些信息；但對(duì)于必須連接和不能連接約束，通過(guò)定義約束勢(shì)函數(shù)，因?yàn)槭潜M量從概率的角度滿足約束，因此不能確保最終得到的社區(qū)劃分一定滿足這兩類(lèi)約束條件.通過(guò)以上兩種方式，確保在我們的方法中，不會(huì)出現(xiàn)兩種先驗(yàn)信息相互沖突的情況.

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

本文從兩個(gè)方面對(duì)提出的半監(jiān)督社區(qū)發(fā)現(xiàn)方法進(jìn)行評(píng)價(jià)，一個(gè)是考慮在具有噪聲的網(wǎng)絡(luò)中，評(píng)價(jià)本文提出的社區(qū)發(fā)現(xiàn)方法的魯棒性，另一個(gè)是與其他社區(qū)發(fā)現(xiàn)方法進(jìn)行比較，展現(xiàn)本文提出方法的有效性.

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

本文選擇了3個(gè)真實(shí)的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其中包括兩個(gè)較小的數(shù)據(jù)集-Zachary社會(huì)關(guān)系網(wǎng)絡(luò)和海豚關(guān)系網(wǎng)，以及一個(gè)大的數(shù)據(jù)集-DBLP協(xié)作網(wǎng).這3個(gè)數(shù)據(jù)集都擁有清晰的社區(qū)結(jié)構(gòu)，能夠方便對(duì)試驗(yàn)結(jié)果進(jìn)行驗(yàn)證.

Zachary社會(huì)關(guān)系網(wǎng)是社交網(wǎng)絡(luò)分析領(lǐng)域中經(jīng)常被用到的一個(gè)小型測(cè)試網(wǎng)絡(luò).20世紀(jì)70年代，Wayne Zachary花了三年時(shí)間（1970～1972年）觀察美國(guó)一所大學(xué)空手道俱樂(lè)部成員間的社會(huì)關(guān)系，然后構(gòu)造了一個(gè)俱樂(lè)部成員社會(huì)關(guān)系網(wǎng)（Zachary′s karate club network）.網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)代表一個(gè)俱樂(lè)部成員，如果兩個(gè)成員經(jīng)常一起出現(xiàn)在俱樂(lè)部活動(dòng)（如空手道訓(xùn)練、俱樂(lè)部聚會(huì)等）之外的其他場(chǎng)合，代表在俱樂(lè)部之外他們可以被稱為朋友，則兩個(gè)成員之間存在連邊，整個(gè)網(wǎng)絡(luò)包含34個(gè)節(jié)點(diǎn)，78條邊.在調(diào)查過(guò)程中發(fā)現(xiàn)，因?yàn)榫銟?lè)部教練Mr.Hi（v1）與主管John A.（v34）之間的爭(zhēng)執(zhí)，該俱樂(lè)部被分裂為了2個(gè)各自以他們?yōu)楹诵牡男〖瘓F(tuán).Zachary社會(huì)關(guān)系網(wǎng)是常用于檢驗(yàn)社團(tuán)發(fā)現(xiàn)算法有效性的網(wǎng)絡(luò)［1，3，9］，該網(wǎng)絡(luò)真實(shí)社團(tuán)結(jié)構(gòu)如圖2所示，圖中不同顏色的節(jié)點(diǎn)代表分裂后的不同集團(tuán)的成員.

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

圖2　Zachary網(wǎng)絡(luò)的真實(shí)社團(tuán)結(jié)構(gòu)Fig.2　Community structure of Zachary′s karate club network

圖3　海豚關(guān)系網(wǎng)的真實(shí)社團(tuán)結(jié)構(gòu)Fig.3　Community structure of dolphin social network

第三個(gè)是DBLP數(shù)據(jù)集，我們使用Yang等［31］提取的DBLP共同作者關(guān)系網(wǎng)絡(luò)，網(wǎng)絡(luò)中的兩個(gè)作者至少合作過(guò)一篇文章，則他們之間具有一條連邊.整個(gè)網(wǎng)絡(luò)包括317080個(gè)節(jié)點(diǎn)，1049866條邊，平均聚類(lèi)系數(shù)為0.6324.數(shù)據(jù)集中包含了Ground-truth社區(qū)，節(jié)點(diǎn)被劃為13477個(gè)社區(qū).數(shù)據(jù)能夠在斯坦福網(wǎng)絡(luò)分析平臺(tái)1被下載.

注意，在3個(gè)數(shù)據(jù)集中，根據(jù)已知的社區(qū)劃分設(shè)置我們的模型中期望的社區(qū)集合，即將社區(qū)個(gè)數(shù)設(shè)置為已知的社區(qū)標(biāo)簽的數(shù)據(jù).

4.2度量指標(biāo)

為了度量社區(qū)發(fā)現(xiàn)的質(zhì)量，我們選擇成對(duì)F-measure（Pairwise F-measure）［32］作為度量指標(biāo)，Basu通過(guò)將信息領(lǐng)域中的F-measure引入到半監(jiān)督聚類(lèi)中，提出成對(duì)F-measure的定義，用來(lái)度量半監(jiān)督聚類(lèi)算法的質(zhì)量.本文選擇成對(duì)F-measure來(lái)測(cè)試社區(qū)發(fā)現(xiàn)算法的質(zhì)量.我們首先給出社區(qū)發(fā)現(xiàn)中的準(zhǔn)確率和召回率的定義：

其中，Epred是預(yù)測(cè)到的社區(qū)內(nèi)的節(jié)點(diǎn)對(duì)的集合，Esame是真實(shí)情況下社區(qū)內(nèi)的節(jié)點(diǎn)對(duì)的集合，Ecorrect=Epred∩Esame是正確預(yù)測(cè)的在社區(qū)內(nèi)的節(jié)點(diǎn)對(duì)的集合，因此我們可以得到成對(duì)F-measure的定義：

顯然F-measure越大，表示社區(qū)發(fā)現(xiàn)的預(yù)測(cè)結(jié)果越好.

4.3抗噪聲能力評(píng)價(jià)

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

在實(shí)驗(yàn)中，首先通過(guò)在真實(shí)的社交網(wǎng)絡(luò)中隨機(jī)地加入和刪除用戶關(guān)系，來(lái)增加噪聲，然后在各種噪聲比例下，通過(guò)加入不同程度的用戶引導(dǎo)信息，進(jìn)行半監(jiān)督的社區(qū)發(fā)現(xiàn)，進(jìn)而比較不同情形下社區(qū)發(fā)現(xiàn)的F-measure值.對(duì)于先驗(yàn)信息的融入，我們區(qū)分兩種情況，分別為僅僅考慮已知部分用戶社區(qū)標(biāo)簽的情況，以及同時(shí)考慮已知部分用戶社區(qū)標(biāo)簽和增加用戶約束的情況.下面我們首先在兩個(gè)網(wǎng)絡(luò)中，分別給出在幾種情況下進(jìn)行半監(jiān)督社區(qū)劃分的例子.

圖4（a）中給出了沒(méi)有噪聲的情況下，Zachary社會(huì)關(guān)系網(wǎng)絡(luò)中通過(guò)融合5個(gè)已知用戶（7、13、15、27和28）的社區(qū)標(biāo)簽，使用我們的半監(jiān)督社區(qū)發(fā)現(xiàn)方法FG-SSCD預(yù)測(cè)得到的社區(qū)劃分，得到的F-measure結(jié)果為0.9462，有1個(gè)節(jié)點(diǎn)（10號(hào)）產(chǎn)生了誤分.圖4（b）中是沒(méi)有噪聲的情況下，海豚社會(huì)網(wǎng)中通過(guò)融合5個(gè)已知用戶（14、22、31、37和50）的社區(qū)標(biāo)簽，我們的半監(jiān)督社區(qū)發(fā)現(xiàn)方法預(yù)測(cè)得到的社區(qū)劃分，F(xiàn)-measure得到的結(jié)果為0.9723，有2個(gè)節(jié)點(diǎn)（29號(hào)和40號(hào)）產(chǎn)生了誤分.

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

圖4　FG-SSCD模型發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)（無(wú)噪聲）Fig.4　Community structure from FG-SSCD（without noise）

以上幾種情況下，不管有無(wú)噪聲數(shù)據(jù)，在兩個(gè)網(wǎng)絡(luò)中進(jìn)行的半監(jiān)督社區(qū)發(fā)現(xiàn)，都取得了較高的F-measure值，獲得了較好的社區(qū)發(fā)現(xiàn)結(jié)果.為了進(jìn)一步驗(yàn)證我們的半監(jiān)督社區(qū)發(fā)現(xiàn)方法在噪聲環(huán)境下的有效性，我們選擇了兩種著名的無(wú)監(jiān)督的社區(qū)發(fā)現(xiàn)算法進(jìn)行對(duì)比，以驗(yàn)證融入先驗(yàn)信息對(duì)于社區(qū)發(fā)現(xiàn)的影響.

圖5　FG-SSCD模型發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)（有噪聲）Fig.5　Community structure from FG-SSCD（with noise）

1）快速Newman算法（Fast-Newman，F(xiàn)N）［8］，F(xiàn)N算法是Newman等提出的一種基于模塊度優(yōu)化的貪婪算法.該算法是在使得模塊度不斷增加的基礎(chǔ)上進(jìn)行，即每次合并沿著使模塊度增多最大和減小最少的方向進(jìn)行.在Zachary和海豚社會(huì)網(wǎng)的實(shí)驗(yàn)中，根據(jù)實(shí)際存在的社區(qū)個(gè)數(shù)，我們將FN算法的社區(qū)個(gè)數(shù)指定為2，而在DBLP中，最終社區(qū)個(gè)數(shù)根據(jù)模塊度最大值設(shè)置.

2）基于信息論的算法（Information-theoretic approach，IT）［33］，這種方法將社區(qū)發(fā)現(xiàn)過(guò)程轉(zhuǎn)化為一個(gè)信號(hào)通信過(guò)程.通過(guò)在信息過(guò)程中對(duì)網(wǎng)絡(luò)結(jié)構(gòu)信息進(jìn)行信號(hào)編碼和解碼，信息丟失最少時(shí)，編碼后得到的社區(qū)結(jié)構(gòu)為最優(yōu)的社區(qū)劃分.這種方法并沒(méi)有設(shè)定發(fā)現(xiàn)社區(qū)的個(gè)數(shù).

我們將網(wǎng)絡(luò)中的噪聲比例分別設(shè)置為2%、4%、6%、8%、10%，由于我們的方法是隨機(jī)產(chǎn)生噪聲和先驗(yàn)信息，因此我們?cè)诓煌壤脑肼暛h(huán)境下，選擇50次的平均結(jié)果作為實(shí)驗(yàn)的最終結(jié)果進(jìn)行比較.圖6中給出了不同噪聲比例下，分別執(zhí)行FN和IT算法，以及融入不同比例的先驗(yàn)信息的情況下通過(guò)FG-SSCD模型，得到的社區(qū)劃分實(shí)驗(yàn)對(duì)比結(jié)果.從圖中可以看出，在Zachary和海豚社會(huì)網(wǎng)中，IT算法的性能顯著低于其他算法，這是因?yàn)镮T并沒(méi)有預(yù)先設(shè)定社區(qū)個(gè)數(shù).事實(shí)上，社區(qū)個(gè)數(shù)也是一種先驗(yàn)信息，這從另一個(gè)側(cè)面也反映出先驗(yàn)信息有利于提高社區(qū)發(fā)現(xiàn)的魯棒性.三個(gè)不同的網(wǎng)絡(luò)中，在無(wú)噪聲環(huán)境下，我們的方法通過(guò)融合先驗(yàn)信息未必能獲得比FN算法更好的社區(qū)劃分.可是在添加噪聲數(shù)據(jù)之后，在不同的噪聲比例下，通過(guò)我們的方法，融合不同比例的先驗(yàn)信息，都能顯著地提高社區(qū)發(fā)現(xiàn)的精度，而且先驗(yàn)信息越多，得到的預(yù)測(cè)精度越高.因?yàn)楝F(xiàn)實(shí)世界的網(wǎng)絡(luò)中，通常都包含了大量的噪聲，因此通過(guò)融入先驗(yàn)信息到社區(qū)發(fā)現(xiàn)中，能夠提高社區(qū)發(fā)現(xiàn)算法的魯棒性，發(fā)現(xiàn)的社區(qū)更能夠有效地揭示現(xiàn)實(shí)世界的網(wǎng)絡(luò)中的真實(shí)社區(qū)結(jié)構(gòu).

圖6　不同噪聲比例下的社區(qū)發(fā)現(xiàn)預(yù)測(cè)精度對(duì)比Fig.6　The prediction accuracy with different noise rate

4.4有效性評(píng)價(jià)

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

我們分別在三個(gè)網(wǎng)絡(luò)中，在設(shè)置不同的噪聲比例的情況下，對(duì)每一項(xiàng)實(shí)驗(yàn)獨(dú)立重復(fù)50次，然后取F-measure的平均值，圖7給出了我們提出的半監(jiān)督社區(qū)發(fā)現(xiàn)算法與半監(jiān)督的Spin-Glass模型的比較結(jié)果.從圖中可以看出，在網(wǎng)絡(luò)中有噪聲的情況下，不管是Zachary網(wǎng)絡(luò)還是海豚社會(huì)網(wǎng)中，本文的結(jié)果一致優(yōu)于Spin-Glass模型的社區(qū)發(fā)現(xiàn)結(jié)果.三個(gè)網(wǎng)絡(luò)中，本文算法得到的平均F-measure比Spin-Glass模型分別提高了6.34%、16.36%和12.13%.因?yàn)閮煞N半監(jiān)督社區(qū)發(fā)現(xiàn)方法都融入了相同的先驗(yàn)信息，相比Spin-Glass模型通過(guò)用戶的經(jīng)驗(yàn)知識(shí)設(shè)置參數(shù)以確定各類(lèi)信息的權(quán)重，本文方法通過(guò)自動(dòng)優(yōu)化特征因子函數(shù)的權(quán)重，可以自動(dòng)確定各種信息對(duì)于社區(qū)劃分的貢獻(xiàn)程度，有助于提高社區(qū)劃分的精度.

5　結(jié)論

本文研究了社區(qū)發(fā)現(xiàn)這一社交網(wǎng)絡(luò)分析中長(zhǎng)期關(guān)注的問(wèn)題，但當(dāng)前大部分的研究都聚焦在如何在網(wǎng)絡(luò)中自動(dòng)發(fā)現(xiàn)社區(qū)的問(wèn)題，在大量具有數(shù)據(jù)缺失或噪聲的網(wǎng)絡(luò)中，自動(dòng)社區(qū)發(fā)現(xiàn)方法往往難以發(fā)現(xiàn)網(wǎng)絡(luò)中的真實(shí)社區(qū)結(jié)構(gòu).而通過(guò)在社區(qū)發(fā)現(xiàn)中融合先驗(yàn)信息，進(jìn)行半監(jiān)督的社區(qū)發(fā)現(xiàn)，可以有效地提高社交網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的預(yù)測(cè)精度.在本文中，基于因子圖模型，通過(guò)融入先驗(yàn)信息到一個(gè)統(tǒng)一的概率框架中，本文提出一種半監(jiān)督的社區(qū)發(fā)現(xiàn)模型-FGSSCD模型，研究具有用戶引導(dǎo)情況下的社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問(wèn)題.在三個(gè)真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)中進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)表明通過(guò)融入先驗(yàn)信息可以有效地提高社區(qū)發(fā)現(xiàn)的精度.另外，與一種最新的半監(jiān)督社區(qū)方法（半監(jiān)督的Spin-Glass模型）進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果顯示我們的FG-SSCD模型可以實(shí)現(xiàn)更好的社區(qū)劃分.

圖7　不同噪聲比例下，與Spin-Glass模型相比較，F(xiàn)G-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，F(xiàn)ang 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，F(xiàn)u 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年獲得解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院博士學(xué)位.主要研究方向?yàn)閿?shù)據(jù)挖掘和機(jī)器學(xué)習(xí).本文通信作者.

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.）

李彩萍北京市遙感信息研究所高級(jí)工程師.2015年獲得裝備學(xué)院博士學(xué)位.主要研究方向?yàn)橄到y(tǒng)仿真.

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.）

張海粟中國(guó)人民解放軍國(guó)防信息學(xué)院副教授.2012年獲得解放軍理工大學(xué)博士學(xué)位.主要研究方向?yàn)閿?shù)據(jù)挖掘.

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.）

劉玉超中國(guó)指揮與控制學(xué)會(huì)副秘書(shū)長(zhǎng). 2012年獲得清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系博士學(xué)位.主要研究方向?yàn)閿?shù)據(jù)挖掘和機(jī)器學(xué)習(xí).

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.）

李德毅中國(guó)電子系統(tǒng)工程研究所研究員.中國(guó)工程院院士.國(guó)際歐亞科學(xué)院院士.1983年獲得英國(guó)愛(ài)丁堡Heriot-Watt大學(xué)博士學(xué)位.主要研究方向?yàn)槿斯ぶ悄?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年獲得國(guó)防科技大學(xué)碩士學(xué)位.主要研究方向?yàn)檫b感信息應(yīng)用.

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

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（973計(jì)劃）（2014CB340401），國(guó)家自然科學(xué)基金（61035004，61273213，61305055）資助

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

本文責(zé)任編委周志華

Recommended by Associate Editor ZHOU Zhi-Hua

1.北京市遙感信息研究所北京1008542.中國(guó)人民解放軍國(guó)防信息學(xué)院武漢4300103.中國(guó)指揮與控制學(xué)會(huì)北京1000484.中國(guó)電子系統(tǒng)工程研究所北京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