基于迭代框架的主動鏈接選擇半監(jiān)督社區(qū)發(fā)現(xiàn)算法

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

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

基于迭代框架的主動鏈接選擇半監(jiān)督社區(qū)發(fā)現(xiàn)算法

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

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

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

半監(jiān)督學(xué)習(xí)；主動鏈接選擇；社區(qū)發(fā)現(xiàn)；非負(fù)矩陣分解

0 引言

社區(qū)發(fā)現(xiàn)常見的方法有譜方法、圖分割方法、聚類方法、目標(biāo)函數(shù)優(yōu)化方法等[1-6]。大部分方法是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，通過算法自動地發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)，屬于無監(jiān)督的方法。這類方法通常存在兩個(gè)問題：1)網(wǎng)絡(luò)過于復(fù)雜時(shí)，比如網(wǎng)絡(luò)之間存在重疊或者存在多級結(jié)構(gòu)，很難準(zhǔn)確獲得社區(qū)的邊界，無法獲得準(zhǔn)確的劃分結(jié)果；2)在具有數(shù)據(jù)稀疏、鏈路缺失或有噪聲的網(wǎng)絡(luò)中，算法性能會大幅下降，難以有效揭示真實(shí)的社區(qū)結(jié)構(gòu)。

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

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

1 ALS_GNMF算法

1.1 圖正則非負(fù)矩陣分解算法

非負(fù)矩陣分解(NMF)算法可以發(fā)現(xiàn)隱含的模塊結(jié)構(gòu)，因此被成功應(yīng)用于無監(jiān)督社區(qū)發(fā)現(xiàn)領(lǐng)域[16]。NMF算法的目的是尋找兩個(gè)非負(fù)矩陣，使得它們乘積與原始矩陣的相似度最高。NMF算法描述如下：

給定一個(gè)m×n的非負(fù)矩陣A，找到m×r的非負(fù)矩陣W和n×r的非負(fù)矩陣H，使得：

A≈WHT

(1)

圖正則非負(fù)矩陣分解(Graph regularization Non-negative Matrix Factorization, GNMF)在進(jìn)行矩陣分解的同時(shí)，要求在低維空間中繼續(xù)保持樣本的幾何結(jié)構(gòu)。假設(shè)兩個(gè)數(shù)據(jù)點(diǎn)ai和aj在原始空間是鄰近點(diǎn)，那么在新的基下hi和hj相應(yīng)地也是鄰近點(diǎn)。

在社區(qū)發(fā)現(xiàn)中，如果預(yù)先知道節(jié)點(diǎn)i和j屬于相同的社區(qū)，那么矩陣H中的第i行和第j行，即hi和hj應(yīng)該是相似的。因此，最小化這兩行的差異，即可把這兩個(gè)節(jié)點(diǎn)指派到相同的社區(qū)。

使用平方距離和K-L散度度量節(jié)點(diǎn)i和j的相似性

(2)

(3)

其中:hik和hjk分別表示節(jié)點(diǎn)i和j屬于社區(qū)k的概率,K為社區(qū)總數(shù)。

基于平方距離的先驗(yàn)約束形式化為：

(4)

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

(5)

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

(6)

RLSE(O,H)與RKL(O,H)即為圖正則項(xiàng)，將它們分別引入相應(yīng)的目標(biāo)函數(shù)，得到：

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

(7)

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

(8)

其中λ是拓?fù)湫畔⑴c先驗(yàn)信息之間的平衡參數(shù)，為非負(fù)數(shù)。

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

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

(9)

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

(10)

FSNMF的更新規(guī)則：

(11)

FKL的更新規(guī)則：

(12)

(13)

1.2 ALS_GNMF算法

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

1)主動鏈接選擇方法。

采用計(jì)算鏈接對信息熵的方法，可以找到位于社區(qū)邊界的不確定性鏈接對。每個(gè)節(jié)點(diǎn)可以通過它屬于某社區(qū)的概率計(jì)算信息熵，公式為：

(14)

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

2)生成先驗(yàn)信息矩陣修改鄰接矩陣。

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

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

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

為使社區(qū)邊界更清晰，若鏈接對與其他社區(qū)相連，則增加鏈接對的cannot-link約束。如圖1所示，主動選擇的鏈接對〈u,v〉，其端點(diǎn)u與其他社區(qū)的節(jié)點(diǎn)b，c，d均有鏈接，此時(shí)，斷開這3組鏈接，為節(jié)點(diǎn)u增加3組cannot-link約束，形成如圖2所示的拓?fù)浣Y(jié)構(gòu)。同時(shí)修改網(wǎng)絡(luò)鄰接矩陣A，令aub=0，auc=0，aud=0。

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

3)ALS_GNMF算法。

ALS_GNMF算法步驟如下：

輸入 網(wǎng)絡(luò)鄰接矩陣A，各節(jié)點(diǎn)與社區(qū)真實(shí)隸屬關(guān)系矩陣C，先驗(yàn)鏈接對比例percent。

輸出 社區(qū)劃分矩陣H。

步驟1 初始化先驗(yàn)信息矩陣O為N×N的零矩陣(N為節(jié)點(diǎn)數(shù))。

步驟2 利用NMF算法，計(jì)算初始社區(qū)劃分矩陣H。

步驟3 利用式(14)計(jì)算H矩陣中各節(jié)點(diǎn)的熵，找到各社區(qū)的hub節(jié)點(diǎn)及t組最不確定鏈接對(為平穩(wěn)且較快達(dá)到規(guī)定先驗(yàn)比例，每次選擇3組最不確定鏈接對，設(shè)置t=3)。

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

步驟5 將先驗(yàn)信息矩陣O融入目標(biāo)函數(shù)，依據(jù)更新規(guī)則反復(fù)迭代，直到兩次目標(biāo)函數(shù)差值達(dá)到指定閾值為止，得到新的社區(qū)劃分矩陣H。

步驟6 計(jì)算主動選擇鏈接對比例ratio，重復(fù)執(zhí)行步驟3～5，直到ratio的值達(dá)到percent為止。

步驟7 計(jì)算并輸出社區(qū)劃分矩陣H。

2 實(shí)驗(yàn)與結(jié)果分析

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

表1 真實(shí)網(wǎng)絡(luò)及人工網(wǎng)絡(luò)數(shù)據(jù)Tab. 1 Data of real-world and synthetic networks

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

表2為3組真實(shí)網(wǎng)絡(luò)的NMI測試數(shù)據(jù)?？梢钥闯鯢ootball網(wǎng)絡(luò)中，ALS_GNMF算法的三種方法在相同先驗(yàn)比例(2%～30%)下NMI值均高于GNMF算法對應(yīng)方法。以ALS_GNMF算法的ALS-LSE方法為例，先驗(yàn)比例為2%(NMI=0.935 7)時(shí)，效果與GNMF算法的LSE方法30%先驗(yàn)比例(NMI=0.932 3)相當(dāng)。同樣，ALS-KL及ALS-SNMF方法2%先驗(yàn)比例的效果相當(dāng)于GNMF對應(yīng)方法 20%先驗(yàn)比例的效果。School7網(wǎng)絡(luò)也具有相同的特點(diǎn)，ALS-KL方法4%的先驗(yàn)比例可達(dá)到KL算法10%的效果，ALS-LSE方法僅2%的先驗(yàn)比例就高于LSE算法30%的效果，ALS-SNMF 8%的先驗(yàn)比例高于SNMF20%的效果。Dolphin網(wǎng)絡(luò)中，ALS_GNMF算法在2%的先驗(yàn)比例下NMI值均已達(dá)到1。

圖3 ALS_GNMF與GNMF算法在LFR網(wǎng)絡(luò)的互信息比較Fig. 3 Normalized mutual information comparison of ALS_GNMF and GNMF on LFR networks

圖4 ALS_GNMF與GNMF算法在LFR網(wǎng)絡(luò)的準(zhǔn)確率比較Fig. 4 Accuracy comparison of ALS_GNMF and GNMF on LFR networks

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

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

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

綜上可知：1)大多數(shù)情況下，采用相同的先驗(yàn)信息比例，ALS_GNMF算法比GNMF算法效果好。2)ALS_GNMF算法使用很少的先驗(yàn)信息比例就可以達(dá)到GNMF算法用較高的先驗(yàn)信息才能達(dá)到的效果。3)網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜時(shí)，GNMF算法性能較差，而ALS_GNMF算法性能良好，且隨著網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜度的增加，表現(xiàn)出良好的穩(wěn)定性和魯棒性。

3 結(jié)語

本文提出的ALS_GNMF算法，基于迭代框架迭代地執(zhí)行：1)基于當(dāng)前社區(qū)發(fā)現(xiàn)結(jié)果，選擇不確定性大的鏈接進(jìn)行標(biāo)定作為先驗(yàn)信息；2)增加所選鏈接對與其所在社區(qū)中心hub節(jié)點(diǎn)間的must-link約束，與相鄰社區(qū)節(jié)點(diǎn)的cannot-link約束，以增強(qiáng)社區(qū)內(nèi)部連接的緊密性，弱化社區(qū)間的鏈接，清晰化社區(qū)邊界；3)將must-link作為正則項(xiàng)融入目標(biāo)函數(shù)進(jìn)行社區(qū)發(fā)現(xiàn)。通過使用實(shí)際網(wǎng)絡(luò)及人工網(wǎng)絡(luò)數(shù)據(jù)集測試， ALS_GNMF算法在相同的先驗(yàn)信息比例下，效果遠(yuǎn)好于GNMF算法，可以使用很少的先驗(yàn)信息比例，達(dá)到GNMF算法用較高的先驗(yàn)信息才能達(dá)到的效果。尤其在結(jié)構(gòu)不清晰的網(wǎng)絡(luò)中，ALS_GNMF算法性能穩(wěn)定，具有良好的魯棒性。

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] 黃立威, 李彩萍, 張海粟, 等. 一種基于因子圖模型的半監(jiān)督社區(qū)發(fā)現(xiàn)方法[J]. 自動化學(xué)報(bào), 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] 陳俊宇, 周剛, 南煜, 等. 一種半監(jiān)督的局部擴(kuò)展式重疊社區(qū)發(fā)現(xiàn)方法[J]. 計(jì)算機(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.)

[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] 李亞芳, 賈彩燕, 于劍. 應(yīng)用非負(fù)矩陣分解模型的社區(qū)發(fā)現(xiàn)方法綜述[J].計(jì)算機(jī)科學(xué)與探索, 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。

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

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

1001- 9081(2017)11- 3085- 05

10.11772/j.issn.1001- 9081.2017.11.3085

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

TP181

A