摘要： 挖掘網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)分析的關(guān)鍵任務(wù)，但在現(xiàn)實(shí)應(yīng)用中如何進(jìn)一步提高社團(tuán)檢測(cè)性能仍極具挑戰(zhàn)性。鑒于屬性網(wǎng)絡(luò)中的節(jié)點(diǎn)內(nèi)容和網(wǎng)絡(luò)嵌入均蘊(yùn)含有社團(tuán)結(jié)構(gòu)信息，提出一種基于非負(fù)矩陣分解融合節(jié)點(diǎn)內(nèi)容和嵌入強(qiáng)化拓?fù)涞陌氡O(jiān)督方法。首先，基于生成框架重構(gòu)拓?fù)浜蛢?nèi)容，以構(gòu)建融合拓?fù)浜蛢?nèi)容的基本模型；然后，利用拓?fù)湎嗨菩詷?gòu)造must-link先驗(yàn)信息，同時(shí)由Node2Vec計(jì)算網(wǎng)絡(luò)嵌入；最后，使用矩陣補(bǔ)全技術(shù)將先驗(yàn)信息和網(wǎng)絡(luò)嵌入引入模型，形成融合內(nèi)容、網(wǎng)絡(luò)嵌入的半監(jiān)督社團(tuán)檢測(cè)模型。在合成和真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果充分驗(yàn)證了新模型的良好競(jìng)爭(zhēng)力。

關(guān)鍵詞： 社團(tuán)檢測(cè)； 屬性網(wǎng)絡(luò)； 半監(jiān)督； 節(jié)點(diǎn)內(nèi)容； 嵌入強(qiáng)化

中圖分類號(hào)： TP391

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1671-6841（2024）06-0046-08

DOI： 10.13705/j.issn.1671-6841.2023143

Combination of the Content and Embedding-enhanced Topology for Semi-supervised Community Detection

XU Weizhong1， LU Yang1， CAO Jinxin1， JU Hengrong1， DING Weiping1， JIN Di2

（1.School of Information Science and Technology， Nantong University， Nantong 226019， China；

2.College of Intelligence and Computing， Tianjin University， Tianjin 300350， China）

Abstract： Mining the community structure in a network was a key task in complex network analysis， but how to further improve the performance of community detection in practical applications was still highly challenging. Considering that both node content and network embedding in attribute networks contain the information of community structure， a semi-supervised method based on non-negative matrix factorization that integrates node content and embed reinforcement topology was proposed. Firstly， based on the generated framework， a basic model that could integrate topology and content was reconstructed. Then， by utilizing the topological similarity between nodes， a must-link prior was constructed， and at the same time， the network embedding was conducted by Node2Vec. Finally， the inductive matrix completion technique was used to introduce prior information and network embedding， forming a semi-supervised community detection model that could integrate content and network embedding. The strong competitiveness of the new model was fully verified through experiments on synthetic and real networks.

Key words： community detection; attributed network; semi-supervised; node content; embedding reinforcement

0 引言

社交網(wǎng)絡(luò)化的數(shù)據(jù)存在于現(xiàn)實(shí)生活中的方方面面，比如，客戶關(guān)系網(wǎng)絡(luò)、在線產(chǎn)品評(píng)論網(wǎng)絡(luò)等。這些帶有節(jié)點(diǎn)內(nèi)容的屬性網(wǎng)絡(luò)可建模為復(fù)雜網(wǎng)絡(luò)。挖掘?qū)傩跃W(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)可揭示所蘊(yùn)含的結(jié)構(gòu)和主要功能，具有十分重要的現(xiàn)實(shí)意義。社團(tuán)結(jié)構(gòu)檢測(cè)有廣泛的應(yīng)用，如社交網(wǎng)絡(luò)的用戶行為和需求檢測(cè)、基因功能檢測(cè)、復(fù)雜系統(tǒng)特性分析、推薦系統(tǒng)等。

社團(tuán)一般定義為同一社團(tuán)的節(jié)點(diǎn)間鏈接稠密，而不同社團(tuán)的節(jié)點(diǎn)間鏈接稀疏。近十幾年來，已有不同類型的社團(tuán)發(fā)現(xiàn)方法提出［1-4］，并取得了不錯(cuò)的成績。傳統(tǒng)方法將具有相似鏈接模式的節(jié)點(diǎn)集識(shí)別為社團(tuán)，當(dāng)面對(duì)異配、分層等復(fù)雜結(jié)構(gòu)的網(wǎng)絡(luò)時(shí)，其性能將受到影響。一些研究人員提出了半監(jiān)督社團(tuán)檢測(cè)方法［5-6］，引入有限的先驗(yàn)信息便可明顯提升社團(tuán)檢測(cè)精度。網(wǎng)絡(luò)中也會(huì)存在鏈接缺失或噪聲，網(wǎng)絡(luò)蘊(yùn)含的內(nèi)容信息在社團(tuán)檢測(cè)任務(wù)中可補(bǔ)充網(wǎng)絡(luò)的拓?fù)?。Newman等［7］發(fā)現(xiàn)，結(jié)合內(nèi)容可識(shí)別的社團(tuán)結(jié)構(gòu)更為準(zhǔn)確。近幾年，網(wǎng)絡(luò)嵌入（network embedding）已被廣泛應(yīng)用于社團(tuán)檢測(cè)領(lǐng)域［1］。網(wǎng)絡(luò)嵌入運(yùn)用稠密的表征向量刻畫社團(tuán)結(jié)構(gòu)，Jin等［2］研究發(fā)現(xiàn)融合網(wǎng)絡(luò)嵌入能夠?qū)Y(jié)構(gòu)復(fù)雜的網(wǎng)絡(luò)進(jìn)行高效挖掘。

同時(shí)融合網(wǎng)絡(luò)拓?fù)?、?nèi)容信息和網(wǎng)絡(luò)嵌入的半監(jiān)督社團(tuán)檢測(cè)方法挖掘網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的執(zhí)行力將會(huì)得到進(jìn)一步提升。因?yàn)榫W(wǎng)絡(luò)中鄰居重合度高的節(jié)點(diǎn)往往具有相似的內(nèi)容信息，它們的網(wǎng)絡(luò)嵌入也會(huì)很相近，被劃分到同一社團(tuán)的可能性也高。本文提出了一種融合節(jié)點(diǎn)內(nèi)容和嵌入強(qiáng)化鏈接的半監(jiān)督社團(tuán)檢測(cè)模型（embedding-enhanced link based semi-supervised community detection with node content，ELSNC）。結(jié)合生成框架和歸納矩陣補(bǔ)全技術(shù)構(gòu)建新模型，將鄰接矩陣、節(jié)點(diǎn)內(nèi)容特征矩陣、拓?fù)湎嗨贫染仃嚒⒕W(wǎng)絡(luò)嵌入矩陣作為模型的四個(gè)輸入源。首先，基于非負(fù)矩陣分解（non-negative matrix factorization，NMF）生成框架構(gòu)建網(wǎng)絡(luò)拓?fù)渥幽Ｐ?，設(shè)計(jì)節(jié)點(diǎn)-社團(tuán)隸屬度矩陣以重構(gòu)鄰接矩陣。接著，基于NMF與主題模型pLSA［8］理論等價(jià)性原理構(gòu)建節(jié)點(diǎn)內(nèi)容子模型，設(shè)計(jì)節(jié)點(diǎn)內(nèi)容-主題隸屬度矩陣以重構(gòu)節(jié)點(diǎn)內(nèi)容。文檔主題即對(duì)應(yīng)網(wǎng)絡(luò)社團(tuán)。然后，運(yùn)用“如果兩個(gè)節(jié)點(diǎn)存在鏈接且具有高度相似的拓?fù)浣Y(jié)構(gòu)，它們將被劃分到同一社團(tuán)”的想法構(gòu)造社團(tuán)指示矩陣以實(shí)現(xiàn)先驗(yàn)信息（半監(jiān)督信息）的構(gòu)建。再次，將網(wǎng)絡(luò)嵌入和先驗(yàn)信息使用歸納矩陣補(bǔ)全技術(shù)引入拓?fù)渥幽Ｐ椭?。最終，使用一個(gè)平衡因子結(jié)合網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)內(nèi)容，使用一個(gè)鄰域超參刻畫先驗(yàn)信息，以實(shí)現(xiàn)融合網(wǎng)絡(luò)拓?fù)洹⒐?jié)點(diǎn)內(nèi)容和網(wǎng)絡(luò)嵌入的半監(jiān)督社團(tuán)檢測(cè)統(tǒng)一模型的構(gòu)建。

1 相關(guān)工作

鑒于新模型融合的信息來自不同類型，本文梳理了基于網(wǎng)絡(luò)拓?fù)渖鐖F(tuán)檢測(cè)、基于內(nèi)容信息社團(tuán)檢測(cè)、融合網(wǎng)絡(luò)拓?fù)渑c節(jié)點(diǎn)內(nèi)容社團(tuán)檢測(cè)以及半監(jiān)督社團(tuán)檢測(cè)等相關(guān)研究工作。

在傳統(tǒng)模型中，基于經(jīng)典的模塊度Q，Blondel等［9］提出Louvain算法，運(yùn)用分層聚類實(shí)現(xiàn)社團(tuán)發(fā)現(xiàn)。Yang等［10］運(yùn)用NMF構(gòu)建隨機(jī)塊模型，經(jīng)推導(dǎo)獲得非負(fù)社團(tuán)隸屬度以挖掘網(wǎng)絡(luò)中的社團(tuán)。Grover等［11］設(shè)計(jì)的經(jīng)典網(wǎng)絡(luò)嵌入模型Node2Vec是基于Deepwalk模型進(jìn)行的擴(kuò)展，獲取節(jié)點(diǎn)表征后進(jìn)行聚類以挖掘社團(tuán)結(jié)構(gòu)。Wang等［12］使用自動(dòng)編碼器優(yōu)化一階和二階相似度圖的圖嵌入模型SDNE，實(shí)現(xiàn)了網(wǎng)絡(luò)嵌入社團(tuán)檢測(cè)精度的提升?；趦?nèi)容信息的模型MAC［13］是運(yùn)用NMF和生成模型思想，實(shí)現(xiàn)了布爾型數(shù)據(jù)的重疊類別聚類，這表明了節(jié)點(diǎn)內(nèi)容也具有社團(tuán)結(jié)構(gòu)。

關(guān)于融合拓?fù)渑c內(nèi)容的模型，Yang等［14］基于生成框架，相互獨(dú)立地建模拓?fù)浜蛢?nèi)容信息，引入一個(gè)平衡因子構(gòu)建融合二元信息的聯(lián)合模型CESNA。Wang等［15］認(rèn)為節(jié)點(diǎn)內(nèi)容能給出社團(tuán)的描述，設(shè)計(jì)了基于NMF融合拓?fù)浜蛢?nèi)容的SCI模型，實(shí)現(xiàn)了對(duì)語義社團(tuán)的挖掘。Yang等［16］提出的TADW模型屬于融合拓?fù)浜蛢?nèi)容的網(wǎng)絡(luò)嵌入模型，其運(yùn)用矩陣分解和歸納矩陣補(bǔ)全技術(shù)實(shí)現(xiàn)二元信息的融合，獲得的網(wǎng)絡(luò)表征可用于社團(tuán)檢測(cè)。

半監(jiān)督社團(tuán)檢測(cè)兼顧了網(wǎng)絡(luò)的異配、分層等復(fù)雜結(jié)構(gòu)，通過引入網(wǎng)絡(luò)結(jié)構(gòu)的先驗(yàn)信息，實(shí)現(xiàn)社團(tuán)結(jié)構(gòu)檢測(cè)性能的提升。Yang等［17］基于子空間聚類思想，以圖正則的形式引入先驗(yàn)信息，提出了NMF_LSE、NMF_SYM模型。He等［18］運(yùn)用修正、懲罰兩種策略引入硬、軟約束形式的先驗(yàn)信息，提出了ECD模型實(shí)現(xiàn)半監(jiān)督社團(tuán)檢測(cè)。

上述模型中，融合內(nèi)容信息、引入先驗(yàn)信息均可實(shí)現(xiàn)社團(tuán)檢測(cè)性能的提升。鑒于此，若在模型中同時(shí)融合內(nèi)容、網(wǎng)絡(luò)嵌入，并引入先驗(yàn)信息，其擴(kuò)展性將會(huì)得到提升，其魯棒性、社團(tuán)結(jié)構(gòu)檢測(cè)能力也將會(huì)進(jìn)一步提升。

2 構(gòu)建ELSNC模型

2.1 構(gòu)建網(wǎng)絡(luò)拓?fù)渥幽Ｐ?/p>

用n表示網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)，m表示鏈接條數(shù)，l表示節(jié)點(diǎn)內(nèi)容特征維度。一個(gè)無向、非加權(quán)的屬性網(wǎng)絡(luò)可以形式化為G=（V， E， F），其中：V={v1，v2，…，vn}，代表節(jié)點(diǎn)集；E={e1，e2，…，em}，代表邊集；F={f1，f2，…，fn}，代表節(jié)點(diǎn)內(nèi)容特征集?；谝陨闲畔?，構(gòu)建鄰接矩陣A∈Rn×n，節(jié)點(diǎn)內(nèi)容特征矩陣為B∈Rn×l，網(wǎng)絡(luò)嵌入矩陣為U，社團(tuán)指示矩陣為C。

鄰接矩陣A的每行表示某一節(jié)點(diǎn)在網(wǎng)絡(luò)中的鏈接狀態(tài)特征。設(shè)置一組參數(shù)xit描述節(jié)點(diǎn)vi隸屬于第t個(gè)社團(tuán)的傾向，另一組參數(shù)wtj描述第t個(gè)社團(tuán)蘊(yùn)含第j個(gè)基特征的傾向。那么，xitwjt則描述社團(tuán)t中節(jié)點(diǎn)vi和vj之間存在鏈接的數(shù)量。則包含k個(gè)社團(tuán)的屬性網(wǎng)絡(luò)G中，vi和vj之間鏈接期望數(shù)可形式化為

a^ij=∑kt=1xitwjt， i=1，2，…，n，j=1，2，…，n，（1）

公式（1）的矩陣化形式為A^=XWT，擬合鄰接矩陣A。拓?fù)渥幽Ｐ偷哪繕?biāo)函數(shù)為

lossto（X，W）=‖A-A^‖2F=‖A-XWT‖2F。（2）

2.2 構(gòu)建內(nèi)容拓?fù)渥幽Ｐ图盎灸Ｐ?/p>

鑒于pLSA主題模型［8］與NMF模型的理論相似性，可將每個(gè)節(jié)點(diǎn)所包含的內(nèi)容對(duì)應(yīng)于一篇文檔，屬性對(duì)應(yīng)文檔中單詞。參數(shù)xit刻畫節(jié)點(diǎn)內(nèi)容-主題隸屬度，設(shè)置hjt描述文章第t個(gè)主題包含第j個(gè)單詞的傾向，xithjt指示節(jié)點(diǎn)vi隸屬于第t個(gè)社團(tuán)，且蘊(yùn)含第j個(gè)屬性的可能性。則節(jié)點(diǎn)vi與第j個(gè)屬性之間的關(guān)聯(lián)可表示為

bij=∑kt=1xithjt， i=1，2，…，n，j=1，2，…，l，（3）

公式（3）的矩陣化形式為B^=XHT，擬合觀測(cè)節(jié)點(diǎn)內(nèi)容特征矩陣B。內(nèi)容子模型的目標(biāo)函數(shù)可形式化為

lossco（X，H）=‖B-B^‖2F=‖B-XHT‖2F。（4）

公式（4）中，文檔集的主題對(duì)應(yīng)于網(wǎng)絡(luò)的社團(tuán)，則節(jié)點(diǎn)內(nèi)容-主題隸屬度即為節(jié)點(diǎn)-社團(tuán)隸屬度。這樣便可對(duì)公式（2）和（4）所表示的子模型進(jìn)行融合，并使用超參α控制內(nèi)容子模型的貢獻(xiàn)。至此融合了拓?fù)浜蛢?nèi)容并構(gòu)建基本模型，其目標(biāo)函數(shù)可形式化為

Oto+co（X，W，H）=

argX，W，H≥0min‖A-XWT‖2F+α·‖B-XHT‖2F。（5）

2.3 引入先驗(yàn)信息

本文基于網(wǎng)絡(luò)中節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)設(shè)置半監(jiān)督信息，即must-link先驗(yàn)信息。對(duì)于某一節(jié)點(diǎn)vi，其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以由它的鄰居節(jié)點(diǎn)來描述，即D（i）={vj∈V（vi，vj）∈E}∪{vi}。那么，網(wǎng)絡(luò)中節(jié)點(diǎn)的拓?fù)湎嗨贫染仃嘢={sij}∈Rn×n可計(jì)算為

sij=D（i）∩D（j）D（i）×D（j）。（6）

基于想法“如果兩個(gè)節(jié)點(diǎn)存在鏈接且拓?fù)浣Y(jié)構(gòu)相似度高，那么，它們之間存在must-link約束，將被分配到同一個(gè)社團(tuán)”，使用以下方式對(duì)約束矩陣Ω={ωij}∈Rn×n進(jìn)行構(gòu)造

ωij=1，aij=1，sij>ε，

0，aij=0，（7）

其中超參ε控制must-link生成的數(shù)量。很明顯，在Ω對(duì)應(yīng)無向圖中任一連通分量下所包含的節(jié)點(diǎn)間均具有must-link約束。進(jìn)一步，設(shè)置指示矩陣C∈Rn×p表示頂點(diǎn)-連通分量隸屬分布，用以刻畫先驗(yàn)信息。此處C可視為節(jié)點(diǎn)的額外特征。基于歸納矩陣補(bǔ)全思想，通過引入一個(gè)非負(fù)的輔助矩陣Y∈Rp×k，則節(jié)點(diǎn)-社團(tuán)隸屬度X可表示為

X=CY，（8）

運(yùn)用公式（8）引入先驗(yàn)信息到基本模型（5），目標(biāo)函數(shù)為

Osemi+to+co（Y，W，H）=

argY，W，H≥0min‖A-CYWT‖2F+α·‖B-CYHT‖2F。（9）

2.4 引入網(wǎng)絡(luò)嵌入信息

Node2Vec算法［10］將鄰接矩陣轉(zhuǎn)化為網(wǎng)絡(luò)嵌入矩陣U∈Rn×p。本文將鄰接矩陣A視為特征矩陣，對(duì)于鄰接矩陣的特征化描述可運(yùn)用奇異值分解等形式。這里同樣借鑒矩陣補(bǔ)全的思想將已獲取的網(wǎng)絡(luò)嵌入U(xiǎn)引入拓?fù)渥幽Ｐ椭校?5］。特征矩陣W可由網(wǎng)絡(luò)嵌入U(xiǎn)作為其額外特征進(jìn)行表示，可形式化為

W→UW，（10）

用公式（10）將網(wǎng)絡(luò)嵌入引入帶有先驗(yàn)信息的基本模型（9）中。統(tǒng)一融合模型的目標(biāo)函數(shù)為

Lfinal（Y，W，H）=Osemi+to+emb+co（Y，W，H）=

argY，W，H≥0min‖A-CYWTUT‖2F+

α·‖B-CYHT‖2F+β·‖W‖2F，（11）

其中，最后一項(xiàng)為正則項(xiàng)，防止模型過擬合。至此，完成了對(duì)ELSNC模型的構(gòu)建。該模型統(tǒng)一化融合網(wǎng)絡(luò)拓?fù)?、?jié)點(diǎn)內(nèi)容、網(wǎng)絡(luò)嵌入和先驗(yàn)信息。通過模型優(yōu)化學(xué)習(xí)參數(shù)矩陣Y后，再結(jié)合指示矩陣C可計(jì)算節(jié)點(diǎn)-社團(tuán)隸屬度。基于節(jié)點(diǎn)-社團(tuán)隸屬度矩陣進(jìn)行聚類，實(shí)現(xiàn)社團(tuán)檢測(cè)。

2.5 ELSNC模型的算法偽代碼

模型ELSNC的具體實(shí)現(xiàn)過程可由如下偽代碼呈現(xiàn)。

算法1 ELSNC的算法

輸入： 鄰接矩陣A，節(jié)點(diǎn)內(nèi)容特征矩陣B，社團(tuán)個(gè)數(shù)k，平衡因子α、β，領(lǐng)域超參ε，閾值ξ，最大迭代次數(shù)τmax。

輸出： 社團(tuán)隸屬度矩陣X。

①運(yùn)用公式（6）計(jì)算A的拓?fù)湎嗨贫染仃嘢，再使用公式（7）設(shè)計(jì)先驗(yàn)信息的指示矩陣C；

②基于A用Node2Vec算法計(jì)算網(wǎng)絡(luò)嵌入U(xiǎn)；

③隨機(jī)初始化Ynew、Wnew和Hnew；

④while （Lfinal （Y，W，H）（τ）-Lfinal（Y，W，H）（τ-1）<ξ or τ>τmax）

⑤令Yold=Ynew，Wold=Wnew，Hold=Hnew，運(yùn)用公式（13）、（14）和（15）更新Ynew、Wnew和Hnew；

⑥運(yùn)用公式（11）計(jì)算Lfinal（Y，W，H）；

⑦τ=τ+1；

⑧end while

⑨獲得最優(yōu)Y，基于公式（8）計(jì)算X；

⑩返回X。

3 ELSNC模型優(yōu)化

模型ELSNC包含了三個(gè)參數(shù)矩陣Y、W和H。秩形式中，y=f（x），則trace［y］=tr［f（x）］。為了進(jìn)行模型推導(dǎo)，現(xiàn)將新模型的目標(biāo)函數(shù)（11）轉(zhuǎn)為秩的形式L（Y，W，H），然后，運(yùn)用卡羅需-庫思-塔克（Karush-Kuhn-Tucker，KKT）條件［19］的梯度下降法進(jìn)行模型參數(shù)更新規(guī)則求解。目標(biāo)函數(shù)（11）的秩形式L（Y，W，H）為

L（Y，W，H）=trace［Lfinal（Y，W，H）］=

tr［（A-CYWTUT）（A-CYWTUT）T］+

α·tr［（B-CYHT）（B-CYHT）T］+β·tr（WWT）=

tr［（A-CYWTUT）（AT-UWYTCT）］+

α·tr［（B-CYHT）（BT-HYTCT）］+

β·tr（WWT）=tr（AAT）-2·tr（AUWYTCT）+

tr（CYWTUTUWYTCT）+

α·tr（BBT）-2α·tr（BHYTCT）+

α·tr（CYHTHYTCT）+β·tr（WWT）。（12）

式（12）關(guān)于參數(shù)矩陣Y的偏導(dǎo)為

YL（Y，W，H）=

-2·Ytr（AUWYTCT）+Ytr（CYWTUTUWYTCT）-

2α·Ytr（BHYTCT）+α·Ytr（CYHTHYTCT）=

-2CTAUW+2CTCYWTUTUW+

2α·CTBH+2α·CTCYHTH。

根據(jù)KKT條件［19］，參數(shù)矩陣Y的更新規(guī)則為

ynewij=yoldij·｛-Y｝ij｛+Y｝ij=

yoldij·（CTAUW+α·CTBH）ij（CTCYWTUTUW+α·CTCYHTH）ij。（13）

同樣，式（12）關(guān)于參數(shù)矩陣W的偏導(dǎo)為

WL（Y，W，H）=-2·Wtr（AUWYTCT）+

Wtr（CYWTUTUWYTCT）+β·tr（WWT）=

-2·UTACY+2·UTUWYTCTCY+2β·W。

而W的更新規(guī)則為

wnewij=woldij·｛-W｝ij｛+W｝ij=

woldij·（UTACY）ij（UTUWYTCTCY+β·W）ij。（14）

式（12）關(guān)于參數(shù)矩陣H的偏導(dǎo)為

HL（Y，W，H）=-2α·Htr（BHYTCT）+

α·Htr（CYHTHYTCT）=

-2α·BCY+2α·HYTCTCY。

同理可求參數(shù)矩陣H的更新規(guī)則為

hnewij=holdij·｛-H｝ij｛+H｝ij=holdij·（BCY）ij（HYTCTCY）ij。（15）

新模型更新過程為：首先，隨機(jī)初始化非負(fù)矩陣Y、W和H；然后，分別基于更新規(guī)則（14）、（16）和（18）對(duì)Y、W和H進(jìn)行迭代更新，直至損失函數(shù)（11）收斂。最后，運(yùn)用公式（8）計(jì)算出節(jié)點(diǎn)社團(tuán)隸屬度，并檢測(cè)社團(tuán)。

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

實(shí)驗(yàn)使用的數(shù)據(jù)有帶有內(nèi)容的GN、LFR人工網(wǎng)絡(luò)［22］，五個(gè)真實(shí)網(wǎng)絡(luò)［23］（詳細(xì)信息如表1所示，網(wǎng)絡(luò)中節(jié)點(diǎn)內(nèi)容的類型用type of F表示）。對(duì)比模型包含：基于拓?fù)涞哪Ｐ陀蠰ouvain［9］、NMF［10］、Node2Vec［11］和SDNE［12］；基于內(nèi)容的模型有MAC［13］；融合拓?fù)浜蛢?nèi)容的模型有CESNA［14］、SCI［15］、TADW［16］；半監(jiān)督社團(tuán)檢測(cè)模型有NMF_LSE［17］、NMF_SYM［17］、ECD［18］。

在對(duì)ELSNC性能分析前，先在帶有內(nèi)容的GN網(wǎng)絡(luò)中對(duì)超參α、β和ε進(jìn)行調(diào)節(jié)。后在帶有內(nèi)容的LFR人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上對(duì)比ELSNC模型與當(dāng)前流行的社團(tuán)檢測(cè)模型識(shí)別社團(tuán)的能力。實(shí)驗(yàn)中，使用了社團(tuán)檢測(cè)領(lǐng)域常用的評(píng)價(jià)方法標(biāo)準(zhǔn)互信息熵（normalized mutual information，NMI）［20］和調(diào)整蘭德系數(shù)（adjusted rand index，ARI）［21］。

4.1 超參數(shù)α、β和ε的調(diào)節(jié)

在帶有內(nèi)容的人工GN網(wǎng)絡(luò)上對(duì)模型超參數(shù)進(jìn)行測(cè)試，設(shè)定網(wǎng)絡(luò)生成參數(shù)Zout為8和10，社團(tuán)結(jié)構(gòu)相對(duì)模糊，便于測(cè)試模型中超參數(shù)α、β和ε的敏感性。

首先，固定超參數(shù)β，調(diào)節(jié)超參數(shù)α和ε。設(shè)定搜索區(qū)域?yàn)?.1<α<10（0.1<α<1時(shí)，α設(shè)為1/10、

1/8、1/6、1/4、1/2）、0.1<ε<1，對(duì)α和 ε執(zhí)行網(wǎng)格搜索以確定最佳超參數(shù)，Zout分別為8和10時(shí)，得到的NMI值變化趨勢(shì)如圖1所示?？梢园l(fā)現(xiàn)，當(dāng)（α， ε）=（0.5，0.8）時(shí)，ELSNC的NMI精度在兩個(gè)帶有內(nèi)容GN網(wǎng)絡(luò)上均取得峰值，因此我們將（0.5，0.8）作為 （α， ε）的推薦值。然后，固定（α， ε）=（0.5， 0.8），Zout分別為8和10時(shí)測(cè)試超參β，結(jié)果如圖2所示。同理，將超參數(shù)β的推薦值設(shè)為10-3。需要說明，首先，把搜索區(qū)域設(shè)置為0<β<10，我們發(fā)現(xiàn)峰值出現(xiàn)的區(qū)域?yàn)?<β<1；然后，為了提高超參數(shù)調(diào)節(jié)的分辨率，使β分別取10-1、10-2、10-3、10-4、10-5、10-6、10-7，觀察是否取得峰值精度。將上述推薦值作為后續(xù)實(shí)驗(yàn)中新模型ELSNC的超參數(shù)默認(rèn)設(shè)置。

4.2 在人工網(wǎng)絡(luò)上的對(duì)比實(shí)驗(yàn)

在可控的網(wǎng)絡(luò)中，檢驗(yàn)?zāi)Ｐ虴LSNC社團(tuán)結(jié)構(gòu)檢測(cè)的能力。對(duì)于網(wǎng)絡(luò)規(guī)模n=1 000，帶有內(nèi)容的LFR網(wǎng)絡(luò)，用混合參數(shù)μ控制節(jié)點(diǎn)度的比值以及此節(jié)點(diǎn)與社團(tuán)外部其他節(jié)點(diǎn)之間鏈接數(shù)量，μ值越大，網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)越模糊，則模型的NMI精度曲線下降越緩慢，其魯棒性越高、執(zhí)行力更強(qiáng)。

如圖3所示，隨著μ值增大，不同模型的NMI值均呈下降趨勢(shì)。圖3中ELSNC模型的NMI曲線下降速度均慢于其他模型，這充分表明了ELSNC在社團(tuán)結(jié)構(gòu)檢測(cè)的性能上具有強(qiáng)大競(jìng)爭(zhēng)力。實(shí)驗(yàn)中，基于內(nèi)容的社團(tuán)檢測(cè)模型MAC的NMI曲線顯示為一條水平線，這是由于不同模糊程度的網(wǎng)絡(luò)設(shè)置共享同一節(jié)點(diǎn)內(nèi)容信息。同時(shí)，還可以發(fā)現(xiàn)，融合拓?fù)渑c內(nèi)容的TADW、SCI和CESNA模型總體的社團(tuán)結(jié)構(gòu)檢測(cè)性能高于基于拓?fù)涞腘MF、Louvain模型。基于網(wǎng)絡(luò)嵌入的Node2Vec、SDNE模型表現(xiàn)不統(tǒng)一，但是，融合網(wǎng)絡(luò)嵌入和內(nèi)容信息的TDAW模型的社團(tuán)檢測(cè)能力總體上排名第二，說明網(wǎng)絡(luò)嵌入的模型對(duì)社團(tuán)檢測(cè)具有良好的輔助作用。綜合分析，同時(shí)融合內(nèi)容信息、網(wǎng)絡(luò)嵌入和先驗(yàn)信息（即半監(jiān)督信息）能夠進(jìn)一步增強(qiáng)模型ELSNC社團(tuán)檢測(cè)的性能。

4.3 在真實(shí)網(wǎng)絡(luò)上的對(duì)比實(shí)驗(yàn)

在真實(shí)網(wǎng)絡(luò)上測(cè)試ELSNC模型與不同對(duì)比模型性能的實(shí)驗(yàn)中，基準(zhǔn)模型中的參數(shù)設(shè)置均參照原作者的默認(rèn)設(shè)置。由于Yang等［17］沒有明確說明NMF_LSE、NMF_SYM模型中must-link的數(shù)量，同時(shí)考慮表1中真實(shí)網(wǎng)絡(luò)的期望鏈接比為m：［（n（n-1）/2）］=1.48%，因此，對(duì)于NMF_LSE、NMF_SYM模型，在實(shí)驗(yàn)中引入（n（n-1）/2）×2%數(shù)量的must-link，即大于且接近m。

在不同真實(shí)網(wǎng)絡(luò)上，模型ELSNC與其他對(duì)比模型基于NMI的性能對(duì)比結(jié)果如表2所示，加粗、斜體的數(shù)值分別表示最佳、第二佳結(jié)果?？梢钥闯?，模型ELSNC在Texas、Washington和Wisconsin上取得最佳結(jié)果，在Cornell、Uai2010上取得了第二佳的結(jié)果。這表明模型ELSNC在社團(tuán)檢測(cè)方面具有較強(qiáng)的性能。這也說明，同時(shí)融合拓?fù)?、?jié)點(diǎn)內(nèi)容、網(wǎng)絡(luò)嵌入和先驗(yàn)信息比融合拓?fù)渑c節(jié)點(diǎn)內(nèi)容或是融合網(wǎng)絡(luò)嵌入與網(wǎng)絡(luò)拓?fù)淠苓M(jìn)一步識(shí)別精確的網(wǎng)絡(luò)社團(tuán)。

關(guān)于模型NMF_SYM在Uai2010上取得較高精度，這是由于該模型中使用must-link的數(shù)量比ELSNC模型超過66倍，其獲得先驗(yàn)信息描述的社團(tuán)結(jié)構(gòu)也更為清晰。一般地，半監(jiān)督社團(tuán)檢測(cè)模型結(jié)合有限的先驗(yàn)信息即可實(shí)現(xiàn)社團(tuán)檢測(cè)性能的明顯提升。但是，ELSNC模型在Uai2010上還是取得了第二佳的結(jié)果。

表3展示了模型ELSNC與其他社團(tuán)檢測(cè)模型基于ARI性能對(duì)比結(jié)果，加粗、斜體的數(shù)值分別表示最佳、第二佳結(jié)果。ARI是聚類、社團(tuán)檢測(cè)領(lǐng)域中常用且與模型、算法類型無關(guān)的評(píng)價(jià)方法，因此，社團(tuán)檢測(cè)性能評(píng)價(jià)結(jié)果更為公平?？梢钥吹?，模型ELSNC在Texas、Washington和Wisconsin上社團(tuán)結(jié)構(gòu)檢測(cè)的性能獲得最佳，在Uai2010上社團(tuán)檢測(cè)的性能取得第二佳，在Cornell上的結(jié)果為第三佳。綜合上述分析，對(duì)比實(shí)驗(yàn)驗(yàn)證了融合拓?fù)?、?nèi)容、網(wǎng)絡(luò)嵌入和先驗(yàn)信息可以進(jìn)一步提高社團(tuán)檢測(cè)模型在屬性網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)檢測(cè)的性能以及魯棒性。

5 結(jié)論

本文提出了一種同時(shí)融合網(wǎng)絡(luò)拓?fù)洹⒐?jié)點(diǎn)內(nèi)容和網(wǎng)絡(luò)嵌入的半監(jiān)督社團(tuán)檢測(cè)模型ELSNC。該模型不僅能利用節(jié)點(diǎn)內(nèi)容緩解網(wǎng)絡(luò)噪聲的影響，也可借助網(wǎng)絡(luò)嵌入刻畫社團(tuán)隸屬度以減緩網(wǎng)絡(luò)拓?fù)湎∈璧呢?fù)面影響。還使用拓?fù)浣Y(jié)構(gòu)生成先驗(yàn)信息來強(qiáng)化拓?fù)涞纳鐖F(tuán)表征能力，社團(tuán)檢測(cè)能力得到進(jìn)一步提升。模型的關(guān)鍵思想在于運(yùn)用非負(fù)矩陣分解框架統(tǒng)一的融合拓?fù)?、?nèi)容、網(wǎng)絡(luò)嵌入和先驗(yàn)信息；基于KKT條件的梯度下降法推導(dǎo)新模型的參數(shù)。實(shí)驗(yàn)結(jié)果驗(yàn)證了ELSNC社團(tuán)檢測(cè)結(jié)構(gòu)的性能優(yōu)越性。

本文提出的模型主要面向靜態(tài)網(wǎng)絡(luò)的社團(tuán)檢測(cè)，還需要預(yù)先設(shè)置社團(tuán)個(gè)數(shù)k。因此，未來的工作包括兩個(gè)方面：1） 設(shè)計(jì)新模型檢測(cè)動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，可以嘗試在新模型中添加正則項(xiàng)實(shí)現(xiàn)；2） 設(shè)計(jì)新模型可以進(jìn)行模型選擇，即模型中預(yù)設(shè)的社團(tuán)個(gè)數(shù)由k自確定，可以嘗試運(yùn)用交叉驗(yàn)證等方式實(shí)現(xiàn)模型選擇以確定k值。

參考文獻(xiàn)：

［1］ YU Z， FAN X H， PIETRASIK M， et al. Fragmentation coagulation based mixed membership stochastic blockmodel［J］. Proceedings of the AAAI conference on artificial intelligence， 2020， 34（4）： 6704-6711.

［2］ JIN D， ZHANG B B， SONG Y， et al. ModMRF： a modularity-based Markov random field method for community detection［J］. Neurocomputing， 2020， 405： 218-228.

［3］ HE D X， WANG Y Y， CAO J X， et al. A network embedding-enhanced Bayesian model for generalized community detection in complex networks［J］. Information sciences， 2021， 575： 306-322.

［4］ 張中軍， 于來行， 李潤川. 基于鏈路結(jié)構(gòu)和轉(zhuǎn)發(fā)行為的微博社交網(wǎng)絡(luò)重疊社區(qū)劃分方法［J］. 鄭州大學(xué)學(xué)報(bào)（理學(xué)版）， 2021， 53（4）： 69-76.

ZHANG Z J， YU L H， LI R C. Overlapping community division method of microblog social network based on link structure and forwarding behavior［J］. Journal of Zhengzhou university （natural science edition）， 2021， 53（4）： 69-76.

［5］ LUBER M， THIELMANN A， WEISSER C， et al. Community-detection via hashtag-graphs for semi-supervised NMF topic models［EB/OL］.（2021-11-17） ［2023-03-11］. https：∥arxiv.org/abs/2111.10401.

［6］ DE SANTO A， GALLI A， MOSCATO V， et al. A deep learning approach for semi-supervised community detection in Online Social Networks［J］. Knowledge-based systems， 2021， 229： 107345.

［7］ NEWMAN M E J， CLAUSET A. Structure and inference in annotated networks［J］. Nature communications， 2016， 7： 11863.

［8］ HOFMANN T. Probabilistic latent semantic indexing［C］∥Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM Press， 1999： 50-57.

［9］ BLONDEL V D， GUILLAUME J L， LAMBIOTTE R， et al. Fast unfolding of communities in large networks［J］. Journal of statistical mechanics： theory and experiment， 2008， 2008（10）： P10008.

［10］YANG J， LESKOVEC J. Overlapping community detection at scale： a nonnegative matrix factorization approach［C］∥Proceedings of the Sixth ACM International Conference on Web Search and Data Mining. New York： ACM Press， 2013： 587-596.

［11］GROVER A， LESKOVEC J. Node2vec： scalable feature learning for networks［J］. KDD： proceedings international conference on knowledge discovery & data mining， 2016， 2016： 855-864.

［12］WANG D X， CUI P， ZHU W W. Structural deep network embedding［C］∥Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press， 2016： 1225-1234.

［13］STREICH A P， FRANK M， BASIN D， et al. Multi-assignment clustering for Boolean data［C］∥Proceedings of the 267+B/9ni7krdmIdJVEgfFEsFnycjT7AyGQlIsvFr4Js4=th Annual International Conference on Machine Learning. New York： ACM Press， 2009： 969-976.

［14］YANG J， MCAULEY J， LESKOVEC J. Community detection in networks with node attributes［C］∥2013 IEEE 13th International Conference on Data Mining. Piscataway： IEEE Press， 2014： 1151-1156.

［15］WANG X A， JIN D， CAO X C， et al. Semantic community identification in large attribute networks［C］∥Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2016： 265-271.

［16］YANG C， LIU Z Y， ZHAO D L， et al. Network representation learning with rich text information［C］∥Proceedings of the 24th International Conference on Artificial Intelligence. New York： ACM Press， 2015： 2111-2117.

［17］YANG L， CAO X C， 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.

［18］HE D X， WANG H C， JIN D， et al. A model framework for the enhancement of community detection in complex networks［J］. Physica A： statistical mechanics and its applications， 2016， 461： 602-612.

［19］QI L Q， JIANG H Y. Semismooth karush-kuhn-tucker equations and convergence analysis of Newton and quasi-newton methods for solving these equations［J］. Mathematics of operations research， 1997， 22（2）： 301-325.

［20］LIU H F， WU Z H， LI X L， et al. Constrained nonnegative matrix factorization for image representation［J］. IEEE transactions on pattern analysis and machine intelligence， 2012， 34（7）： 1299-1311.

［21］YEUNG K Y， RUZZO W L. Principal component analysis for clustering gene expression data［J］. Bioinformatics， 2001， 17（9）： 763-774.

［22］CAO J X， JIN D， DANG J W. Autoencoder based community detection with adaptive integration of network topology and node contents［M］.Cham： Springer International Publishing， 2018.

［23］SEN P， NAMATA G， BILGIC M， et al. Collective classification in network data［J］. AI magazine， 2008， 29（3）： 93-106.