基于鏈接模型的主動半監(jiān)督社區(qū)發(fā)現(xiàn)方法

柴變芳，王建嶺，許冀偉，李文斌

(1.河北地質(zhì)大學(xué) 信息工程學(xué)院，石家莊050031； 2.河北中醫(yī)學(xué)院 公共課教學(xué)部，石家莊 050200)

基于鏈接模型的主動半監(jiān)督社區(qū)發(fā)現(xiàn)方法

柴變芳1，王建嶺2*，許冀偉1，李文斌1

(1.河北地質(zhì)大學(xué) 信息工程學(xué)院，石家莊050031； 2.河北中醫(yī)學(xué)院 公共課教學(xué)部，石家莊 050200)

鏈接模型可對網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題建模，相比具有相同目標(biāo)的對稱模型和條件模型，PPL模型處理網(wǎng)絡(luò)類型更多、社區(qū)發(fā)現(xiàn)準(zhǔn)確率更高。但PPL模型是一個無監(jiān)督模型，在網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)不清晰時效果不佳，且不能利用易獲取的先驗信息。為使用盡可能少的先驗，獲得社區(qū)發(fā)現(xiàn)鏈接模型性能較大的提升， 提出了一個主動節(jié)點先驗學(xué)習(xí)(ANPL)算法，該算法主動選擇效用高、易標(biāo)記的成對約束進行標(biāo)記，基于標(biāo)記的約束對自動生成信息量更大的標(biāo)記節(jié)點集合。基于PPL模型設(shè)計了一個融合網(wǎng)絡(luò)拓撲結(jié)構(gòu)和標(biāo)記節(jié)點先驗的半監(jiān)督社區(qū)發(fā)現(xiàn)(SPPL)模型，并給出模型用于半監(jiān)督社區(qū)發(fā)現(xiàn)的參數(shù)估計算法。人工網(wǎng)絡(luò)和實際網(wǎng)絡(luò)上的實驗結(jié)果表明，利用ANPL獲得的標(biāo)記節(jié)點先驗和網(wǎng)絡(luò)拓撲結(jié)構(gòu)， SPPL模型的社區(qū)發(fā)現(xiàn)準(zhǔn)確率高于無監(jiān)督PPL模型及當(dāng)前流行的基于非負矩陣分解(NMF)的半監(jiān)督社區(qū)發(fā)現(xiàn)模型。

半監(jiān)督社區(qū)發(fā)現(xiàn)；主動學(xué)習(xí)；鏈接模型；最大期望算法；約束先驗

0 引言

社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)分析的一個關(guān)鍵方法，其可識別網(wǎng)絡(luò)中緊密鏈接子圖，子圖內(nèi)節(jié)點鏈接緊密，子圖間節(jié)點鏈接稀疏。研究者提出了大量社區(qū)發(fā)現(xiàn)方法[1-2]，基于概率模型的社區(qū)發(fā)現(xiàn)方法因其具有解釋性強的數(shù)學(xué)模型、嚴(yán)密的推理算法及有意義的準(zhǔn)確結(jié)果，在各種社區(qū)發(fā)現(xiàn)方法中脫穎而出。大多流行的概率模型對網(wǎng)絡(luò)的鏈接生成過程建模，根據(jù)模型的功能不同將其分為3類[3-4]：1)對稱的模型，假設(shè)鏈接的兩個端點角色相同，對無向網(wǎng)絡(luò)的鏈接的聯(lián)合概率建模；2)條件模型，對有向網(wǎng)絡(luò)的接收鏈接的端點產(chǎn)生鏈接的條件概率建模；3)非對稱模型，對有向網(wǎng)絡(luò)的有向鏈接的聯(lián)合概率建模。前兩類是第3類的特例，PPL(Popularity and Productivity Link)模型屬于非對稱模型， 模型性能優(yōu)于前兩種，但其屬于無監(jiān)督聚類，僅能利用網(wǎng)絡(luò)拓撲信息，導(dǎo)致模型性能在網(wǎng)絡(luò)結(jié)構(gòu)不清晰時不夠魯棒、準(zhǔn)確。

近來研究者提出了一些半監(jiān)督社區(qū)發(fā)現(xiàn)方法，先驗信息被引入到社區(qū)發(fā)現(xiàn)中，利用先驗信息提高社區(qū)劃分的性能。已有的半監(jiān)督社區(qū)發(fā)現(xiàn)方法分為兩類：一類直接利用節(jié)點類標(biāo)作為監(jiān)督信息[5-7]，該方法屬于使用監(jiān)督信息的最直接方法，但通常不易獲取節(jié)點屬于某類的先驗信息，因此不是最有效的方法。另一類利用約束鏈接對must-link和cannot-link作為監(jiān)督信息[8-13]，歸為3類：1)隨機選擇鏈接，標(biāo)定約束類型，假設(shè)同類節(jié)點鏈接、異類節(jié)點不鏈接，利用約束改變鄰接矩陣，基于傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法挖掘網(wǎng)絡(luò)潛在聚類結(jié)構(gòu)[8-10]。2)隨機選擇鏈接信息，將鏈接信息作為罰項與無監(jiān)督社區(qū)發(fā)現(xiàn)目標(biāo)函數(shù)融合。Yang等[11]提出一個基于潛在空間圖正則化的半監(jiān)督社區(qū)發(fā)現(xiàn)框架，將先驗信息作為正則化項與社區(qū)發(fā)現(xiàn)模型整合。3)基于主動學(xué)習(xí)策略選擇鏈接進行人工標(biāo)記，為半監(jiān)督社區(qū)發(fā)現(xiàn)提供效用高的約束。將這些先驗依據(jù)同類節(jié)點鏈接、異類節(jié)點不鏈接的假設(shè)轉(zhuǎn)化為網(wǎng)絡(luò)拓撲結(jié)構(gòu)，然后基于融入先驗的拓撲實現(xiàn)傳統(tǒng)無監(jiān)督社區(qū)發(fā)現(xiàn)。Cheng等[12]提出了一個主動半監(jiān)督方法，基于啟發(fā)性策略選擇節(jié)點及其相關(guān)約束進行標(biāo)定，對約束進行擴展，最后利用傳統(tǒng)社區(qū)發(fā)現(xiàn)方法識別網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。Yang等[13]設(shè)計了一個迭代的主動半監(jiān)督聚類方法，每次迭代基于網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)結(jié)果，利用最大熵原則選擇最不確定的鏈接進行標(biāo)記，基于鏈接策略和去鏈接策略，清晰化網(wǎng)絡(luò)結(jié)構(gòu)，基于此網(wǎng)絡(luò)拓撲實現(xiàn)非負矩陣分解進行社區(qū)發(fā)現(xiàn)。

研究表明，半監(jiān)督信息可以提高無監(jiān)督社區(qū)發(fā)現(xiàn)的性能，尤其是主動選擇的先驗。因此，設(shè)計主動學(xué)習(xí)算法獲取先驗，利用先驗提高PPL模型的社區(qū)發(fā)現(xiàn)性能。先驗主要有兩類，標(biāo)記節(jié)點和約束標(biāo)記，前者簡單但不易獲取，后者不易融入基于概率模型的社區(qū)發(fā)現(xiàn)節(jié)點隸屬度變量中。Basu等[14]提出了一個主動半監(jiān)督聚類算法，其主動學(xué)習(xí)算法可以通過標(biāo)記約束獲得每個類的標(biāo)記節(jié)點集合，但其不能直接應(yīng)用到網(wǎng)絡(luò)數(shù)據(jù)上。

借鑒已有半監(jiān)督社區(qū)發(fā)現(xiàn)方法和主動學(xué)習(xí)方法的思想，將無監(jiān)督社區(qū)發(fā)現(xiàn)模型PPL改進為半監(jiān)督模型，可利用高質(zhì)量的先驗信息提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確性。為設(shè)計一個以較少先驗獲得社區(qū)發(fā)現(xiàn)準(zhǔn)確率較大提升的算法，首先提出一個主動節(jié)點先驗學(xué)習(xí)(Active Node Prior Learning, ANPL)算法，主動選擇約束對進行標(biāo)記，基于標(biāo)記約束生成不相交的多個節(jié)點子集組成的標(biāo)記節(jié)點集合，每個子集對應(yīng)一個社區(qū)。然后，提出一個基于PPL模型的半監(jiān)督社區(qū)發(fā)現(xiàn)(Semi-supervised PPL, SPPL)模型，將ANPL學(xué)到的標(biāo)記節(jié)點集合與網(wǎng)絡(luò)拓撲信息融合，以獲得更高的社區(qū)發(fā)現(xiàn)準(zhǔn)確率。最后，在人工網(wǎng)絡(luò)和實際網(wǎng)絡(luò)數(shù)據(jù)上驗證設(shè)計的ANPL和SPPL模型的有效性。

1 主動節(jié)點先驗學(xué)習(xí)算法ANPL

半監(jiān)督先驗的常見形式有約束對標(biāo)記和節(jié)點標(biāo)記，約束對形式的標(biāo)記容易獲得。例如，在文檔聚類中，很容易根據(jù)兩個文檔特征的相似度判斷其是否屬于一類；在微信用戶網(wǎng)絡(luò)社區(qū)劃分時，很容易根據(jù)兩個微信用戶關(guān)注主題判斷其是否屬于一個社區(qū)。但節(jié)點標(biāo)記先驗容易初始化節(jié)點的隸屬度信息，進而初始化PPL模型參數(shù)。因此，設(shè)計主動節(jié)點先驗學(xué)習(xí)ANPL算法，主動選擇約束對進行標(biāo)記，基于約束對生成標(biāo)記節(jié)點集合。

初始類骨架構(gòu)造階段 基于最遠優(yōu)先遍歷模式，選擇與已標(biāo)記節(jié)點集合最不相似的節(jié)點，標(biāo)記其與已標(biāo)記節(jié)點的約束關(guān)系，進而確定其屬于某個標(biāo)記節(jié)點集合。針對某個網(wǎng)絡(luò)A，首先選擇度最大的節(jié)點作為初始類節(jié)點，記作N1的元素。

然后依次選擇與已有標(biāo)記節(jié)點集合相似度最小的節(jié)點，節(jié)點與已有Nk的相似度值計算如式(1)所示。根據(jù)與已有Nk的關(guān)系，如果與已有Nk存在must-link約束關(guān)系則添加到該集合，如果與所有{Nk}都為cannot-link關(guān)系，則新構(gòu)造一個集合，將該節(jié)點加入。

(1)

初始類骨架構(gòu)造階段結(jié)束條件是{Nk}集合元素個數(shù)達到K，或標(biāo)記成對約束超過給定數(shù)目。如果初始骨架構(gòu)造階段在約束超限結(jié)束時，{Nk}個數(shù)未達到K，則從未選擇節(jié)點中選擇熵大節(jié)點加入{Nk}，直到{Nk}個數(shù)達到K。

節(jié)點i熵計算公式為：

(2)

ANPL算法詳細描述如算法1。

算法1 主動節(jié)點先驗學(xué)習(xí)算法。

輸入 網(wǎng)絡(luò)節(jié)點劃分類個數(shù)K，鄰接矩陣A={Aij}，節(jié)點的相似度矩陣，所有節(jié)點的熵，可使用約束對數(shù)目m；

網(wǎng)絡(luò)骨架構(gòu)造階段：

1)

N1={度最大的節(jié)點},當(dāng)前類個數(shù)curk=1。

2)

while (curk

如果與某個Nk中節(jié)點存在must-link,則加入Nk，

curk=curk+1，加入Ncurk,根據(jù)使用約束數(shù)量修改m

end

類集合擴展階段：

3)

while (使用約束

選擇熵最大的節(jié)點i

將i加入與其具有must-link的Nk集合

end

ANPL算法可主動選擇約束對進行標(biāo)記，自動生成標(biāo)記節(jié)點集合先驗，作為半監(jiān)督社區(qū)發(fā)現(xiàn)的先驗。下面設(shè)計一個半監(jiān)督社區(qū)發(fā)現(xiàn)SPPL模型。

2 半監(jiān)督社區(qū)發(fā)現(xiàn)SPPL模型

PPL屬于無監(jiān)督社區(qū)發(fā)現(xiàn)模型，為獨立生成網(wǎng)絡(luò)邊集合E的每條邊〈i,j〉建模。相關(guān)變量定義如下：γik表示節(jié)點i屬于社區(qū)k的概率；ai表示節(jié)點i產(chǎn)生鏈接的概率；bj表示節(jié)點j接收鏈接的概率；ci表示節(jié)點i在確定社區(qū)先驗時的權(quán)重；〈i,j〉表示i指向j的鏈接。

PPL假設(shè)網(wǎng)絡(luò)每條鏈接〈i,j〉生成過程如下：

PPL模型生成所有鏈接的似然如下：

(3)

SL=

(4)

基于最大期望(Expectation Maximization, EM)框架求解SPPL模型參數(shù)。

E步按照式(5)求解網(wǎng)絡(luò)任意鏈接〈i,j〉的隸屬度qijk：

(5)

M步求解模型參數(shù):

ai、bj、ci與PPL模型參數(shù)更新一致。

SPPL參數(shù)估計算法詳細描述如算法2。

算法2 SPPL參數(shù)估計算法。

輸出γ，a,b,c。

1)

2)

while(閾值未達到)

根據(jù)式(5)計算所有鏈接的{qijk}；

計算所有節(jié)點的{ai}，{bj}，{ci}；

計算似然閾值。

end

3 實驗與結(jié)果分析

為驗證基于ANPL的半監(jiān)督SPPL模型的參數(shù)估計算法的有效性，與最近流行的基于非負矩陣分解(Non-negative Matrix Factorization, NMF)的半監(jiān)督社區(qū)發(fā)現(xiàn)算法：基于KL散度(Kullback-Leibleer divergence)的非負矩陣分解方法NMF_KL和基于對稱NMF的非負矩陣分解方法SNMF(Symmetric NMF)進行比較[11]，這兩種算法被驗證具有較好的性能。選取4個真實無向網(wǎng)絡(luò)數(shù)據(jù)(http://www-personal.umich.edu/～mejn/)、4個WebKB的子有向網(wǎng)絡(luò)(http://www.cs.cmu.edu/～WebKB/)(表1)和3個人工LFR無向網(wǎng)絡(luò)[15]進行測試(表2)，表2的混合系數(shù)表示類間鏈接概率。

表1 真實網(wǎng)絡(luò)數(shù)據(jù)集Tab. 1 Real network datasets

算法在Intel Core i5-6200U CPU，8 GB內(nèi)存的Windows10(64位)計算機上運行，用Matlab2012實現(xiàn)。主動節(jié)點先驗學(xué)習(xí)算法ANPL抽取先驗比例為網(wǎng)絡(luò)節(jié)點對的一定百分比，網(wǎng)絡(luò)節(jié)點對為N(N-1)/2，N為網(wǎng)絡(luò)節(jié)點個數(shù)。先驗比例分別設(shè)置為0.05、0.1、0.15、0.2、0.25、0.3、0.35、0.4。

表2 LFR人工網(wǎng)絡(luò)數(shù)據(jù)集Tab. 2 LFR synthetic network datasets

在無向真實網(wǎng)絡(luò)和人工網(wǎng)絡(luò)上，對基于ANPL的SPPL社區(qū)發(fā)現(xiàn)模型性能進行測試，每個比例下的實驗結(jié)果為算法運行10次的平均值和方差。為驗證ANPL算法能得到比標(biāo)記約束對更多的先驗信息，以karate網(wǎng)絡(luò)為例，提供0.05、0.1、0.15比例約束對先驗，ANPL獲得的先驗信息統(tǒng)計結(jié)果如表3所示。

表3 karate網(wǎng)絡(luò)上ANPL算法所獲先驗數(shù)量分析Tab. 3 Quantum analysis captained by ANPL algorithm on the karate network

表3中，“主動標(biāo)記約束對數(shù)量”表示ANPL算法主動選擇的需要人工標(biāo)記的約束對數(shù)量，“獲取標(biāo)記節(jié)點數(shù)量”表示ANPL算法輸出的標(biāo)記節(jié)點集合元素個數(shù)，“轉(zhuǎn)換的約束數(shù)量”表示輸出的標(biāo)記節(jié)點集合轉(zhuǎn)換為must-link和cannot-link約束數(shù)量。由表3可看出，算法輸出的節(jié)點標(biāo)記集合轉(zhuǎn)換為約束對的數(shù)量大于標(biāo)記的約束對數(shù)量,因此在karate上，ANPL算法可利用主動標(biāo)記的約束對獲得更大信息量的先驗信息。其余網(wǎng)絡(luò)類似，不再贅述。為驗證其性能，將ANPL算法獲得的標(biāo)記節(jié)點集合作為SPPL模型的先驗，通過基于SPPL模型的社區(qū)發(fā)現(xiàn)準(zhǔn)確率來驗證獲取先驗是否有效。

SPPL與NMF_KL、SNMF結(jié)果的標(biāo)準(zhǔn)互信息(Normalized Mutual Information, NMI)值比較如圖1～2所示(圖1(a)中，因為SNMF和SPPL模型在不同比例下的準(zhǔn)確率都為1，因此兩者的NMI曲線重合)。由于基于NMF的半監(jiān)督社區(qū)發(fā)現(xiàn)方法針對無向網(wǎng)絡(luò)，會將有向網(wǎng)絡(luò)轉(zhuǎn)換為無向網(wǎng)絡(luò)進行處理，丟失網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息。

圖1 真實網(wǎng)絡(luò)上算法結(jié)果比較Fig. 1 Comparisons of algorithms results on real networks

基于NMF的半監(jiān)督社區(qū)發(fā)現(xiàn)方法只能處理無向網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題，基于SPPL的半監(jiān)督社區(qū)發(fā)現(xiàn)可同時處理有向網(wǎng)絡(luò)和無向網(wǎng)絡(luò)。表3給出了有向網(wǎng)絡(luò)上基于ANPL的SPPL在不同比例先驗0、0.01、0.05、0.1下社區(qū)發(fā)現(xiàn)結(jié)果的NMI值。

基于ANPL的SPPL社區(qū)發(fā)現(xiàn)的實驗結(jié)果分析如下：

1)基于SPPL模型的半監(jiān)督社區(qū)發(fā)現(xiàn)方法，可處理有向網(wǎng)絡(luò)和無向網(wǎng)絡(luò)。圖1、圖2、表4的基于SPPL模型的實驗結(jié)果表明，半監(jiān)督SPPL模型的性能優(yōu)于無監(jiān)督PPL模型的算法性能。

2)最近提出的性能較優(yōu)的NMF_KL和SNMF半監(jiān)督社區(qū)發(fā)現(xiàn)方法只能處理無向網(wǎng)絡(luò)。圖1～2給出了無向網(wǎng)絡(luò)上，NMF_KL和SNMF與基于半監(jiān)督SPPL模型性能比較結(jié)果。SNMF和NMF_KL在沒有引入先驗時大多數(shù)效果要比SPPL模型好，但隨著先驗的增加，SPPL模型的性能都超過基于NMF的半監(jiān)督方法，并且隨著先驗信息的增加，半監(jiān)督SPPL模型性能也隨之提高，尤其類個數(shù)較多、結(jié)構(gòu)不清晰條件下，SPPL性能提升更多，如在football、karate網(wǎng)絡(luò)上。分析結(jié)果表明，在無向網(wǎng)絡(luò)上，主動半監(jiān)督社區(qū)發(fā)現(xiàn)模型SPPL性能優(yōu)于基于NMF的半監(jiān)督社區(qū)發(fā)現(xiàn)方法，主要原因是ANPL獲得的先驗信息量更大、SPPL模型能更好地對網(wǎng)絡(luò)潛在社區(qū)結(jié)構(gòu)建模。

3)根據(jù)圖2中的NMI結(jié)果可看出：在類個數(shù)較多、混合系數(shù)較大時，即使先驗增加很多， NMF_KL和SNMF不能很好地識別網(wǎng)絡(luò)結(jié)構(gòu)；主要原因是這兩種算法選擇隨機抽取約束對進行標(biāo)記。SPPL模型則能夠更好地利用同等先驗約束對提高算法的性能；主要原因是采用了主動選擇約束及半監(jiān)督技術(shù)。

因此，主動節(jié)點先驗選擇算法ANPL有效地為基于半監(jiān)督SPPL模型選擇了信息量大的先驗，使得在相同先驗下基于SPPL模型的社區(qū)發(fā)現(xiàn)方法可獲得更好的性能。

圖2 人工網(wǎng)絡(luò)上算法結(jié)果比較Fig. 2 Comparisons of algorithms results on synthetic networks表4 有向網(wǎng)絡(luò)上基于ANPL的SPPL算法實驗結(jié)果(NMI)Tab. 4 NMI results of SPPL based on ANPL on directed networks

網(wǎng)絡(luò)比例00.010.050.1cornell0.03510.03770.04120.1210texas0.05730.06880.07090.0882washing-ton0.05190.05770.07870.1320wisconsin0.06690.07700.08900.1120

4 結(jié)語

鏈接模型PPL是一個性能較優(yōu)的社區(qū)發(fā)現(xiàn)模型，但其在網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜時效果不佳，且不能利用先驗信息提高性能。為利用更少的先驗更高效地提高模型的社區(qū)發(fā)現(xiàn)能力，提出了一個主動節(jié)點先驗學(xué)習(xí)算法ANPL和一個半監(jiān)督社區(qū)發(fā)現(xiàn)模型SPPL。ANPL主動選擇較少的、信息量較高的成對約束對進行標(biāo)記，基于標(biāo)記的約束對自動生成信息量更大的標(biāo)記節(jié)點集合。SPPL模型融合節(jié)點標(biāo)記先驗和網(wǎng)絡(luò)拓撲結(jié)構(gòu)對社區(qū)發(fā)現(xiàn)任務(wù)建模，基于EM算法估計模型參數(shù)。與近來流行的半監(jiān)督社區(qū)發(fā)現(xiàn)方法相比，基于ANPL的SPPL模型具有更好的社區(qū)發(fā)現(xiàn)能力。目前的算法不能處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)，未來將將現(xiàn)有算法遷移到Hadoop平臺或Spark平臺上，以高效、準(zhǔn)確地處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)。

References)

[1] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3/4/5):75-174.

[2] 黃泳航, 湯庸, 李春英, 等. 基于社區(qū)劃分的學(xué)術(shù)論文推薦模型[J]. 計算機應(yīng)用, 2016,36(5):1279-1283,1289.(HUANG Y H, TANG Y, LI C Y, et al. Academic paper recommendation model based on community detection[J]. Journal of Computer Applications, 2016, 36(5): 1279-1283,1289.)

[3] YANG T, JIN R, CHI Y, et al. Combining Link and Content for Community Detection[M]. New York: Springer, 2014:927-936.

[4] YANG T, CHI Y, ZHU S, et al. Directed network community detection: a popularity and productivity link model[C]// SIAM International Conference on Data Mining. Philadelphia: SIAM, 2010: 742-753.

[5] 黃立威, 李彩萍, 張海粟, 等. 一種基于因子圖模型的半監(jiān)督社區(qū)發(fā)現(xiàn)方法[J]. 自動化學(xué)報, 2016, 42(10): 1520-1531.(HUANG L W, LI C P, ZHANG H S, et al. A semi-supervised community detection method based on factor graph model[J]. Acta Automatica Sinica, 2016, 42(10): 1520-1531.)

[6] ERIC E, RACHAEL M. A spin-glass model for semi-supervised community detection[C]// Proceedings of the 26th AAAI Conference on Artificial Intelligence. Menlo Park, CA: AAAI Press, 2012: 900-906.

[7] 陳俊宇, 周剛, 南煜, 等. 一種半監(jiān)督的局部擴展式重疊社區(qū)發(fā)現(xiàn)方法[J]. 計算機研究與發(fā)展, 2016, 53(6): 1376-1388.(CHEN J Y, ZHOU G, NAN Y, et al. Semi-supervised local expansion method for overlapping community detection[J]. Journal of Computer Research and Development, 2016, 53(6): 1376-1388.)

[8] MA X, GAO L, YONG X, et al. Semi-supervised clustering algorithm for community structure detection in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2010, 389(1):187-197.

[9] ZHANG Z Y. Community structure detection in complex networks with partial background information[J]. Europhysics Letters, 2013, 101(4): 48005.

[10] ZHANG Z Y, SUN K D, WANG S Q. Enhanced community structure detection in complex networks with partial background information[J]. Scientific Reports, 2013, 3: 3241.

[11] YANG L,CAO X,JIN D, et al. A unified semi-supervised community detection framework using latent space graph regularization[J]. IEEE Transactions on Cybernetics,2015,45(11):2585-2598.

[12] CHENG J, LENG M, LI L, et al. Active semi-supervised community detection based on must-link and cannot-link constraints[J]. PLoS One, 2014, 9(10): e110088.

[13] YANG L, JIN D, WANG X, et al. Active link selection for efficient semi-supervised community detection[J]. Scientific Reports, 2015, 5: 9039.

[14] BASU S, BANERJEE A, MOONEY R J. Active semi-supervision for pairwise constrained clustering[EB/OL].[2016- 11- 20]. http://www.cs.utexas.edu/users/ml/papers/semi-sdm-04.pdf.

[15] LANCICHINETTI A, FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E: Statistical Nonlinear and Soft Matter Physics, 2009, 80(2):016118.

This work is partially supported by the National Natural Science Foundation of China (61503260).

CHAIBianfang, born in 1979, Ph. D., associate professor. Her research interests include complex network analysis, probabilistic graphical model, machine learning, community detection.

WANGJianling, born in 1973, M. S., associate professor. His research interests include data mining.

XUJiwei, born in 1979, M. S., lecturer. His research interests include clustering, complex network analysis, deep learning.

LIWenbin, born in 1974, Ph. D., professor. His research interests include machine learning, complex network.

Activesemi-supervisedcommunitydetectionmethodbasedonlinkmodel

CHAI Bianfang1, WANG Jianling2*, XU Jiwei1, LI Wenbin1

(1.SchoolofInformationEngineering,HebeiGeoUniversity,ShijiazhuangHebei050031,China;2.DepartmentofPublicCourses,HebeiUniversityofChineseMedicine,ShijiazhuangHebei050200,China)

Link model is able to model community detection problem on networks. Compared with other similar models including symmetric models and conditional models, PPL (Popularity and Productivity Link) deals more types of networks, and detects communities more accurately. But PPL is an unsupervised model, and works badly when the network structure is unclear. In addition, PPL is not able to utilize priors that are easily captained. In order to improve its performance by using as less as possible, an Active Node Prior Learning (ANPL) algorithm was provided. ANPL selected the highest utility and easily labeled pairwise constraints, and generated automatically more informative labeled nodes based on the labeled pairwise constraints. Based on the PPL model，a Semi-supervised PPL (SPPL) model was proposed for community detection, which combined the topology of network and node labels learned from the ANPL algorithm. Experiments on synthetic and real networks demonstrate that using node priors from the ANPL algorithm and the topology of a network, SPPL model excels to unsupervised PPL model and popular semi-supervised community detection models based on Non-negative Matrix Factorization (NMF).

semi-supervised community detection; active learning; link model; Expectation Maximization (EM) algorithm; constrained prior

2017- 05- 16;

2017- 06- 01。

國家自然科學(xué)基金資助項目(61503260)。

柴變芳(1979—)，女，山西運城人，副教授，博士，主要研究方向：復(fù)雜網(wǎng)絡(luò)分析、概率圖模型、機器學(xué)習(xí)、社區(qū)發(fā)現(xiàn)； 王建嶺(1973—)，男，河北巨鹿人，副教授，碩士，主要研究方向：數(shù)據(jù)挖掘； 許冀偉(1979—)，男，河北秦皇島人，講師，碩士，主要研究方向：聚類、復(fù)雜網(wǎng)絡(luò)分析、深度學(xué)習(xí)； 李文斌(1974—)，男，江西南昌人，教授，博士，CCF高級會員，主要研究方向：機器學(xué)習(xí)、復(fù)雜網(wǎng)絡(luò)。

1001- 9081(2017)11- 3090- 05

10.11772/j.issn.1001- 9081.2017.11.3090

(*通信作者電子郵箱w3365@163.com)

TP181

A