基于鏈接模型的主動半監督社區發現方法

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

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

基于鏈接模型的主動半監督社區發現方法

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

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

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

半監督社區發現；主動學習；鏈接模型；最大期望算法；約束先驗

0 引言

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

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

研究表明，半監督信息可以提高無監督社區發現的性能，尤其是主動選擇的先驗。因此，設計主動學習算法獲取先驗，利用先驗提高PPL模型的社區發現性能。先驗主要有兩類，標記節點和約束標記，前者簡單但不易獲取，后者不易融入基于概率模型的社區發現節點隸屬度變量中。Basu等[14]提出了一個主動半監督聚類算法，其主動學習算法可以通過標記約束獲得每個類的標記節點集合，但其不能直接應用到網絡數據上。

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

1 主動節點先驗學習算法ANPL

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

初始類骨架構造階段 基于最遠優先遍歷模式，選擇與已標記節點集合最不相似的節點，標記其與已標記節點的約束關系，進而確定其屬于某個標記節點集合。針對某個網絡A，首先選擇度最大的節點作為初始類節點，記作N1的元素。

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

(1)

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

節點i熵計算公式為：

(2)

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

算法1 主動節點先驗學習算法。

輸入 網絡節點劃分類個數K，鄰接矩陣A={Aij}，節點的相似度矩陣，所有節點的熵，可使用約束對數目m；

網絡骨架構造階段：

1)

N1={度最大的節點},當前類個數curk=1。

2)

while (curk

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

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

end

類集合擴展階段：

3)

while (使用約束

選擇熵最大的節點i

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

end

ANPL算法可主動選擇約束對進行標記，自動生成標記節點集合先驗，作為半監督社區發現的先驗。下面設計一個半監督社區發現SPPL模型。

2 半監督社區發現SPPL模型

PPL屬于無監督社區發現模型，為獨立生成網絡邊集合E的每條邊〈i,j〉建模。相關變量定義如下：γik表示節點i屬于社區k的概率；ai表示節點i產生鏈接的概率；bj表示節點j接收鏈接的概率；ci表示節點i在確定社區先驗時的權重；〈i,j〉表示i指向j的鏈接。

PPL假設網絡每條鏈接〈i,j〉生成過程如下：

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

(3)

SL=

(4)

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

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

(5)

M步求解模型參數:

ai、bj、ci與PPL模型參數更新一致。

SPPL參數估計算法詳細描述如算法2。

算法2 SPPL參數估計算法。

輸出γ，a,b,c。

1)

2)

while(閾值未達到)

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

計算所有節點的{ai}，{bj}，{ci}；

計算似然閾值。

end

3 實驗與結果分析

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

表1 真實網絡數據集Tab. 1 Real network datasets

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

表2 LFR人工網絡數據集Tab. 2 LFR synthetic network datasets

在無向真實網絡和人工網絡上，對基于ANPL的SPPL社區發現模型性能進行測試，每個比例下的實驗結果為算法運行10次的平均值和方差。為驗證ANPL算法能得到比標記約束對更多的先驗信息，以karate網絡為例，提供0.05、0.1、0.15比例約束對先驗，ANPL獲得的先驗信息統計結果如表3所示。

表3 karate網絡上ANPL算法所獲先驗數量分析Tab. 3 Quantum analysis captained by ANPL algorithm on the karate network

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

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

圖1 真實網絡上算法結果比較Fig. 1 Comparisons of algorithms results on real networks

基于NMF的半監督社區發現方法只能處理無向網絡的社區發現問題，基于SPPL的半監督社區發現可同時處理有向網絡和無向網絡。表3給出了有向網絡上基于ANPL的SPPL在不同比例先驗0、0.01、0.05、0.1下社區發現結果的NMI值。

基于ANPL的SPPL社區發現的實驗結果分析如下：

1)基于SPPL模型的半監督社區發現方法，可處理有向網絡和無向網絡。圖1、圖2、表4的基于SPPL模型的實驗結果表明，半監督SPPL模型的性能優于無監督PPL模型的算法性能。

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

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

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

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

網絡比例00.010.050.1cornell0.03510.03770.04120.1210texas0.05730.06880.07090.0882washing-ton0.05190.05770.07870.1320wisconsin0.06690.07700.08900.1120

4 結語

鏈接模型PPL是一個性能較優的社區發現模型，但其在網絡結構復雜時效果不佳，且不能利用先驗信息提高性能。為利用更少的先驗更高效地提高模型的社區發現能力，提出了一個主動節點先驗學習算法ANPL和一個半監督社區發現模型SPPL。ANPL主動選擇較少的、信息量較高的成對約束對進行標記，基于標記的約束對自動生成信息量更大的標記節點集合。SPPL模型融合節點標記先驗和網絡拓撲結構對社區發現任務建模，基于EM算法估計模型參數。與近來流行的半監督社區發現方法相比，基于ANPL的SPPL模型具有更好的社區發現能力。目前的算法不能處理大規模網絡數據，未來將將現有算法遷移到Hadoop平臺或Spark平臺上，以高效、準確地處理大規模網絡數據。

References)

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

[2] 黃泳航, 湯庸, 李春英, 等. 基于社區劃分的學術論文推薦模型[J]. 計算機應用, 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] 黃立威, 李彩萍, 張海粟, 等. 一種基于因子圖模型的半監督社區發現方法[J]. 自動化學報, 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] 陳俊宇, 周剛, 南煜, 等. 一種半監督的局部擴展式重疊社區發現方法[J]. 計算機研究與發展, 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。

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

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

1001- 9081(2017)11- 3090- 05

10.11772/j.issn.1001- 9081.2017.11.3090

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

TP181

A