基于迭代框架的主動鏈接選擇半監督社區發現算法

陳嶷瑛，柴變芳，李文斌，賀毅朝，吳聰聰

(河北地質大學 信息工程學院，石家莊 050031)

基于迭代框架的主動鏈接選擇半監督社區發現算法

陳嶷瑛*，柴變芳，李文斌，賀毅朝，吳聰聰

(河北地質大學 信息工程學院，石家莊 050031)

針對非負矩陣分解(NMF)半監督社區發現方法隨機選擇先驗約束，導致提升相同性能需要更多約束信息的問題，提出一種基于迭代框架的主動鏈接選擇半監督社區發現算法——ALS_GNMF。在迭代框架下，首先，主動選擇不確定性高且對社區劃分指導性強的鏈接對作為先驗信息；其次，為主動選擇的鏈接對增加must-link約束，增強社區間連接，生成先驗矩陣；同時，增加cannot-link約束，減弱社區間連接，修改鄰接矩陣；最后，將先驗矩陣作為正則項，加入基于NMF的最優化目標函數，并融合網絡拓撲結構信息，以期用較少的先驗信息，達到較高的社區發現準確性和魯棒性。實驗結果表明，ALS_GNMF算法在真實網絡及人工網絡上，相同的先驗比例下，性能比未采用迭代框架和主動策略的NMF半監督社區發現方法有更大的提升，且在結構不清晰的網絡中表現穩定。

半監督學習；主動鏈接選擇；社區發現；非負矩陣分解

0 引言

社區發現常見的方法有譜方法、圖分割方法、聚類方法、目標函數優化方法等[1-6]。大部分方法是基于網絡拓撲結構，通過算法自動地發現網絡中的社區，屬于無監督的方法。這類方法通常存在兩個問題：1)網絡過于復雜時，比如網絡之間存在重疊或者存在多級結構，很難準確獲得社區的邊界，無法獲得準確的劃分結果；2)在具有數據稀疏、鏈路缺失或有噪聲的網絡中，算法性能會大幅下降，難以有效揭示真實的社區結構。

為解決上述問題，半監督方法被引入社區發現算法[7-15]，利用先驗信息提高社區劃分的準確度以及噪聲環境下社區劃分的魯棒性。Eaton等[9]提出一種spin-glass模型，引入包含背景知識的節點標簽和成對約束，提升算法的性能及魯棒性。Wang等[10]提出在標簽更新時吸收其鄰近節點的標簽信息作為先驗信息的標簽傳播算法，不但繼承了速度快的特點，還提高了社區發現的質量。這種直接使用節點標簽作為監督信息的半監督社區發現方法簡單而直接，但通常情況下，節點標簽不易獲取，或代價昂貴。Zhang[11]和Zhang等[12]提出一種半監督社區發現的學習框架(及增強框架)，通過鏈接對的must-link和cannot-link約束，為社區結構矩陣降噪，同時考慮節點的拓撲結構和鏈接對信息，指導社區發現過程，得到更具解釋性的劃分結果。但這些算法多采用隨機選擇鏈接對的方法，沒有更多關注對社區劃分具指導性的鏈接對，也沒有關注先驗信息與目標函數的關系。Yang等[13]提出一種使用隱空間圖正則化方法的統一的半監督社區發現框架，并提出了基于各種非負矩陣分解(Non-negative Matrix Factorization, NMF)變形和譜聚類的半監督社區發現算法。對屬于同一社區的節點增加圖正則化項，使得越相近的節點在隱空間的向量表示盡可能相近。該方法將must-link約束對信息引入目標函數，提升算法在不同網絡，尤其結構不清晰網絡上社區發現的準確性。但是，這種方法存在以下不足：1)只是在初始化階段選擇約束對，對先驗信息不能充分利用; 2)隨機選擇約束對，目標性不強，可能需要增加約束對比例以期達到滿意的效果; 3)不能充分利用cannot-link約束信息。2015年，Yang等[14]提出一種主動選擇鏈接的半監督社區發現方法。基于NMF算法，提出鏈接策略(Connection Strategy)和斷開鏈接策略(Disconnection Strategy)，并對兩種策略的4種組合在不同的社區網絡中進行測試，實驗表明這些策略的運用，可以降低監督信息比例。但因僅利用先驗信息改變網絡的拓撲結構，沒能融入社區發現過程，不能更充分地利用先驗信息提升算法性能。

為減小鏈接選擇信息的比例，并將先驗信息引入目標函數，本文借鑒文獻[14]算法，在基于NMF的半監督社區發現算法[13]的基礎上，提出一種基于迭代框架的主動鏈接選擇半監督社區發現算法ALS_GNMF(Active Link Selection algorithm for semi-supervised community detection based on Graph regularization NMF)。該算法在迭代框架下，主動選擇對社區劃分有指導意義且屬于相同社區的鏈接對。通過增加鏈接對兩端點之間，以及它們與所在社區中心(hub)的must-link約束，增強社區內部連接的緊密性；同時，增加與相鄰社區節點的cannot-link約束，使社區邊界更清晰。然后將主動選擇的鏈接對作為先驗信息，引入目標函數，以期提升算法性能。

1 ALS_GNMF算法

1.1 圖正則非負矩陣分解算法

非負矩陣分解(NMF)算法可以發現隱含的模塊結構，因此被成功應用于無監督社區發現領域[16]。NMF算法的目的是尋找兩個非負矩陣，使得它們乘積與原始矩陣的相似度最高。NMF算法描述如下：

給定一個m×n的非負矩陣A，找到m×r的非負矩陣W和n×r的非負矩陣H，使得：

A≈WHT

(1)

圖正則非負矩陣分解(Graph regularization Non-negative Matrix Factorization, GNMF)在進行矩陣分解的同時，要求在低維空間中繼續保持樣本的幾何結構。假設兩個數據點ai和aj在原始空間是鄰近點，那么在新的基下hi和hj相應地也是鄰近點。

在社區發現中，如果預先知道節點i和j屬于相同的社區，那么矩陣H中的第i行和第j行，即hi和hj應該是相似的。因此，最小化這兩行的差異，即可把這兩個節點指派到相同的社區。

使用平方距離和K-L散度度量節點i和j的相似性

(2)

(3)

其中:hik和hjk分別表示節點i和j屬于社區k的概率,K為社區總數。

基于平方距離的先驗約束形式化為：

(4)

Tr(HTDH)-Tr(HTOH)=Tr(HTLH)

(5)

同理，基于K-L散度的約束形式化為：

(6)

RLSE(O,H)與RKL(O,H)即為圖正則項，將它們分別引入相應的目標函數，得到：

FLSE(H|A,O)=LLSE(A,H)+λRLSE(O,H)=

(7)

FKL(H|A,O)=LKL(A,H)+λRKL(O,H)=

(8)

其中λ是拓撲信息與先驗信息之間的平衡參數，為非負數。

對無向無權圖，其鄰接矩陣A是對稱的，式(7)可以改寫成：

FSNMF(H|A,O)=LSNMF(A,H)+λRSNMF(O,H)=

(9)

采用三重迭代算法[13]，獲得FLSE的更新規則：

(10)

FSNMF的更新規則：

(11)

FKL的更新規則：

(12)

(13)

1.2 ALS_GNMF算法

ALS_GNMF算法的基本思想是：1)利用NMF算法計算初始社區劃分矩陣H，主動選擇H中位于社區邊界不確定性高，并對社區劃分具有指導意義的鏈接對; 2)為主動選擇鏈接對增加must-link約束，生成先驗信息矩陣，增加cannot-link約束，修改鄰接矩陣; 3)將先驗信息矩陣作為正則項融入基于NMF的最優化目標函數，依據更新規則反復迭代，直到兩次更新的目標函數差值達到指定的閾值為止，得到最終的社區劃分矩陣H。

1)主動鏈接選擇方法。

采用計算鏈接對信息熵的方法，可以找到位于社區邊界的不確定性鏈接對。每個節點可以通過它屬于某社區的概率計算信息熵，公式為：

(14)

如果某個節點屬于k個不同社區的概率是相同的，即概率為1/k，則該節點的不確定性很大，熵值是最大的;相反，如果節點屬于某個特定社區的概率為1，屬于其他社區的概率為0，則該節點的確定性很大，熵值最小。鏈接對的熵值定義為其端點熵值的平均值。

2)生成先驗信息矩陣修改鄰接矩陣。

尋找每個社區中心(hub)節點h，即社區中熵值最小的節點。若鏈接對的兩個端點屬于同一社區，則在這兩個端點之間，以及每個端點與h之間建立must-link約束。

如圖1所示，鏈接對〈u,v〉屬于同一社區，節點h為該社區hub，則在節點u與v，u與h，v與h之間建立3個must-link約束，即令ouv=1，ouh=1，ovh=1。依次處理所有主動選擇的鏈接對，生成先驗信息矩陣O。

圖1 增加must-link約束Fig. 1 Adding must-link constraints

為使社區邊界更清晰，若鏈接對與其他社區相連，則增加鏈接對的cannot-link約束。如圖1所示，主動選擇的鏈接對〈u,v〉，其端點u與其他社區的節點b，c，d均有鏈接，此時，斷開這3組鏈接，為節點u增加3組cannot-link約束，形成如圖2所示的拓撲結構。同時修改網絡鄰接矩陣A，令aub=0，auc=0，aud=0。

圖2 增加cannot-link約束Fig. 2 Adding cannot-link constraints

3)ALS_GNMF算法。

ALS_GNMF算法步驟如下：

輸入 網絡鄰接矩陣A，各節點與社區真實隸屬關系矩陣C，先驗鏈接對比例percent。

輸出 社區劃分矩陣H。

步驟1 初始化先驗信息矩陣O為N×N的零矩陣(N為節點數)。

步驟2 利用NMF算法，計算初始社區劃分矩陣H。

步驟3 利用式(14)計算H矩陣中各節點的熵，找到各社區的hub節點及t組最不確定鏈接對(為平穩且較快達到規定先驗比例，每次選擇3組最不確定鏈接對，設置t=3)。

步驟4 對照真實隸屬關系矩陣C，為主動選擇的鏈接對增加must-link約束，修改先驗信息矩陣O，增加cannot-link約束，修改鄰接矩陣A。

步驟5 將先驗信息矩陣O融入目標函數，依據更新規則反復迭代，直到兩次目標函數差值達到指定閾值為止，得到新的社區劃分矩陣H。

步驟6 計算主動選擇鏈接對比例ratio，重復執行步驟3～5，直到ratio的值達到percent為止。

步驟7 計算并輸出社區劃分矩陣H。

2 實驗與結果分析

為比較ALS_GNMF算法與GNMF算法[13]的性能，以標準互信息(Normalized Mutual Information, NMI)和準確率作為評價指標，選取3組真實網絡和3組人工生成網絡進行測試，如表1所示。實際網絡為Football、School7和Dolphin網絡，3組人工網絡為LFR網絡，除混合參數外，其他生成參數均相同。算法用Matlab實現，在Intel Core CPU 2.60 GHz，4 GB內存的Windows7(64位)計算機上運行。

表1 真實網絡及人工網絡數據Tab. 1 Data of real-world and synthetic networks

兩種算法分別采用3種更新規則：1)基于平方距離的LSE方法(式(10))；2)基于平方距離的對稱矩陣的SNMF方法(式(11))；3)基于K-L散度KL方法(式(12))。每個網絡均使用6種方法測試，先驗比例從0增加到30%，NMI值及準確率均取10次計算的平均值，測試結果見表2、圖3及圖4所示。

表2為3組真實網絡的NMI測試數據。可以看出Football網絡中，ALS_GNMF算法的三種方法在相同先驗比例(2%～30%)下NMI值均高于GNMF算法對應方法。以ALS_GNMF算法的ALS-LSE方法為例，先驗比例為2%(NMI=0.935 7)時，效果與GNMF算法的LSE方法30%先驗比例(NMI=0.932 3)相當。同樣，ALS-KL及ALS-SNMF方法2%先驗比例的效果相當于GNMF對應方法 20%先驗比例的效果。School7網絡也具有相同的特點，ALS-KL方法4%的先驗比例可達到KL算法10%的效果，ALS-LSE方法僅2%的先驗比例就高于LSE算法30%的效果，ALS-SNMF 8%的先驗比例高于SNMF20%的效果。Dolphin網絡中，ALS_GNMF算法在2%的先驗比例下NMI值均已達到1。

圖3 ALS_GNMF與GNMF算法在LFR網絡的互信息比較Fig. 3 Normalized mutual information comparison of ALS_GNMF and GNMF on LFR networks

圖4 ALS_GNMF與GNMF算法在LFR網絡的準確率比較Fig. 4 Accuracy comparison of ALS_GNMF and GNMF on LFR networks

圖3為人工網絡的NMI測試結果，為驗證算法在LFR網絡的性能，選取不同的混合參數，生成120個節點的三組網絡。參數設置為：節點數N=120，平均度k=11，度的最大值kmax=20，社區數最小值xmin=5，社區數最大值cmax=13。圖3(a)的混合參數mu=0.7，圖3(b)的混合參數mu=0.8，圖3(c)的混合參數mu=0.9。

圖3(a)中GNNF的LSE、KL方法性能較差，SNMF方法及ALS-LSE、ALS-SNMF、ALS-KL方法均隨著先驗比例的增加性能呈上升態勢，且SNMF方法在30%的先驗比例下效果與ALS-SNMF，ALS-KL相當。圖3(b)混合參數增加到0.8，SNMF方法雖仍強于LSE和KL，但與之前相比性能急劇下降，曲線僅呈微弱抬升趨勢。

而ALS_GNMF算法的ALS-SNMF、ALS-KL及ALS-LSE性能基本穩定，隨先驗比例的增加呈明顯上升趨勢。圖3(c)混合參數增加到0.9，GNMF算法的三種方法的性能都很差，LSE方法甚至有下降趨勢。相反，ALS_GNMF算法的三種方法依然隨先驗比例的增加呈上升趨勢。ALS-KL和ALS-SNMF方法還能保持較高的穩定性。圖4的準確率測試結果亦可得出與NMI大致相同的結論。

綜上可知：1)大多數情況下，采用相同的先驗信息比例，ALS_GNMF算法比GNMF算法效果好。2)ALS_GNMF算法使用很少的先驗信息比例就可以達到GNMF算法用較高的先驗信息才能達到的效果。3)網絡結構復雜時，GNMF算法性能較差，而ALS_GNMF算法性能良好，且隨著網絡結構復雜度的增加，表現出良好的穩定性和魯棒性。

3 結語

本文提出的ALS_GNMF算法，基于迭代框架迭代地執行：1)基于當前社區發現結果，選擇不確定性大的鏈接進行標定作為先驗信息；2)增加所選鏈接對與其所在社區中心hub節點間的must-link約束，與相鄰社區節點的cannot-link約束，以增強社區內部連接的緊密性，弱化社區間的鏈接，清晰化社區邊界；3)將must-link作為正則項融入目標函數進行社區發現。通過使用實際網絡及人工網絡數據集測試， ALS_GNMF算法在相同的先驗信息比例下，效果遠好于GNMF算法，可以使用很少的先驗信息比例，達到GNMF算法用較高的先驗信息才能達到的效果。尤其在結構不清晰的網絡中，ALS_GNMF算法性能穩定，具有良好的魯棒性。

References)

[1] KAUFMANN E, BONALD T, LELARGE M. An adaptive spectral algorithm for the recovery of overlapping communities in networks [C/OL].[2016- 11- 20]. http://chercheurs.lille.inria.fr/ekaufman/KBL15.pdf.

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

[3] SHEN H, CHENG X, GUO J. Exploring the structural regularities in networks[J]. Physical Review E, 2011, 84(5):056111.

[4] JIANG Y, JIA C, YU J. An efficient community detection method based on rank centrality[J]. Physical A: Statistical Mechanics and Its Applications, 2013, 392(9):2182-2194.

[5] ALDECOA R, MARN I. Surprise maximization reveals the community structure of complex networks [J]. Scientific Reports, 2013, 3(1): 1060.

[6] JIANG Y, JIA C, YU J. An efficient community detection algorithm using greedy surprise maximization [J].Journal of Physics A: Mathematical and Theoretical, 2014, 47(16): 165101.

[7] 黃立威, 李彩萍, 張海粟, 等. 一種基于因子圖模型的半監督社區發現方法[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.)

[8] 陳俊宇, 周剛, 南煜, 等. 一種半監督的局部擴展式重疊社區發現方法[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.)

[9] EATON E, MANSBACH R. 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, 7:900-906.

[10] WANG Y, WANG W, LIU D, et al. Using prior knowledge for community detection by label propagation algorithm[EB/OL].[2017- 05- 20]. https://www.scientific.net/AMR.1049-1050.1566.

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

[12] 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.

[13] 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.

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

[15] CAI D, HE X, HAN J, et al. Graph regularized nonnegative matrix factorization for data representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1548-1560.

[16] 李亞芳, 賈彩燕, 于劍. 應用非負矩陣分解模型的社區發現方法綜述[J].計算機科學與探索, 2016, 10(1):1-13.(LI Y F, JIA C Y, YU J. Survey on community detection algorithms using nonnegative matrix factorization model[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(1):1-13.)

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

CHENYiying, born in 1971, Ph. D., professor. Her research interests include community detection, machine learning.

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

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

HEYichao, born in 1969, M. S., professor. His interests include the intelligent computing, combinatorial optimization, algorithm theory.

WUCongcong, born in 1975, M. S., lecturer. Her research interests include intelligent computing, information retrieval.

Semi-supervisedcommunitydetectionalgorithmusingactivelinkselectionbasedoniterativeframework

CHEN Yiying*, CHAI Bianfang, LI Wenbin, HE Yichao, WU Congcong

(SchoolofInformationEngineering,HebeiGEOUniversity,ShijiazhuangHebei050031,China)

In order to solve the problem that large amounts of supervised information was needed to achieve satisfactory performance, owing to the implementation of the semi-supervised community detection methods based on Non-negative Matrix Factorization (NMF) which selected prior information randomly, an Active Link Selection algorithm for semi-supervised community detection based on Graph regularization NMF (ALS_GNMF) was proposed. Firstly, in the iteration framework, the most uncertain and informative links were selected actively as prior information links. Secondly, the must-link constraints of these links, which generated the prior matrix, were added to enhance the connections in a certain community. At the same time, the cannot-link constraints were added, which modified the adjacency matrix, to weaken the connections between communities. Finally, the prior matrix was used as a graph regularization term to incorporate into the optimization objective function of NMF. And combining with network topology information, higher community discovery accuracy and robustness were achieved with less prior information. At the same prior ratio on both synthetic and real networks, experimental results demonstrate that the ALS_GNMF algorithm significantly outperformes the existing semi-supervised NMF algorithms in terms of efficiency, and it is stable especially on networks with unclear structure.

semi-supervised learning; active link selection; community detection; Non-negative Matrix Factorization (NMF)

2017- 05- 16;

2017- 06- 05。

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

陳嶷瑛(1971—)，女，湖南寧遠人，教授，博士，主要研究方向：社區發現、機器學習； 柴變芳(1979—)，女，山西運城人，副教授，博士，主要研究方向：復雜網絡分析、概率圖模型、機器學習、社區發現； 李文斌(1974—)，男，江西南昌人，教授，博士，CCF高級會員，主要研究方向：機器學習、復雜網絡分析； 賀毅朝(1969—),男，河北晉州人，教授，碩士，CCF高級會員，主要研究方向：智能計算、組合優化、算法理論；吳聰聰(1975—)，女，河北唐山人，講師，碩士，主要研究方向：智能計算、信息檢索。

1001- 9081(2017)11- 3085- 05

10.11772/j.issn.1001- 9081.2017.11.3085

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

TP181

A