徐新黎,尹 晶,肖云月,龍海霞

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

1 引 言

隨著信息技術(shù)的不斷發(fā)展與普及,出現(xiàn)了越來越多節(jié)點(diǎn)有屬性的網(wǎng)絡(luò),例如社交網(wǎng)絡(luò)Facebook、引文網(wǎng)絡(luò)Wiki、在線商品評(píng)論網(wǎng)站Epinions、醫(yī)學(xué)研究蛋白質(zhì)網(wǎng)絡(luò)等.社區(qū)發(fā)現(xiàn)是網(wǎng)絡(luò)分析中的一個(gè)基本問題,對(duì)于屬性網(wǎng)絡(luò)來說,除了使社區(qū)內(nèi)節(jié)點(diǎn)的連接緊密外,同一社區(qū)內(nèi)節(jié)點(diǎn)的屬性也應(yīng)該是同質(zhì)的,即同一社區(qū)內(nèi)節(jié)點(diǎn)的特征信息相似.經(jīng)典的社區(qū)發(fā)現(xiàn)方法主要分為兩類:一類是僅處理網(wǎng)絡(luò)的結(jié)構(gòu)(即節(jié)點(diǎn)之間的聯(lián)系),而忽略節(jié)點(diǎn)的特征;另一類是使用節(jié)點(diǎn)屬性來發(fā)現(xiàn)社區(qū),完全忽略節(jié)點(diǎn)之間的聯(lián)系,代表方法有k-means聚類算法.近年來,國內(nèi)外學(xué)者對(duì)屬性網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的研究不斷深入,注意到只處理結(jié)構(gòu)或只處理屬性的方法不能夠完全利用網(wǎng)絡(luò)中所有的可用信息,研究能同時(shí)利用結(jié)構(gòu)和屬性的社區(qū)發(fā)現(xiàn)方法已成為網(wǎng)絡(luò)分析的一個(gè)新領(lǐng)域[1].

屬性網(wǎng)絡(luò)的節(jié)點(diǎn)規(guī)模一般比傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)大,而且每個(gè)節(jié)點(diǎn)帶有高維的屬性信息.如何有效地處理大量的屬性信息是一個(gè)難題,而特征選擇是一個(gè)常用且可以較好地用于節(jié)點(diǎn)重要屬性(特征)篩選的方法.通過特征選擇可以剔除不相關(guān)的特征,降低節(jié)點(diǎn)屬性的維度,但又不影響屬性中有效信息的利用,可以協(xié)助分類、聚類、社區(qū)發(fā)現(xiàn)等下游任務(wù)的開展.常用的特征選擇方法為無監(jiān)督方法,例如拉普拉斯得分法LapScore,通過給屬性網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)屬性進(jìn)行打分,篩選出分?jǐn)?shù)最高的前t個(gè)節(jié)點(diǎn)屬性[2].Li Z.等提出一種非負(fù)判別特征選擇NDFS,利用判別信息和特征相關(guān)性來選擇更好的特征子集,提出了一種簡(jiǎn)單有效的迭代算法來優(yōu)化目標(biāo)函數(shù)[3].對(duì)于鏈接社交媒體網(wǎng)絡(luò),Tang J.等提出一種特征選擇框架LUFS,用偽標(biāo)簽作為無監(jiān)督的替代約束,使用最大化模塊度,并提出損失函數(shù),用優(yōu)化算法求解[4].為了利用節(jié)點(diǎn)屬性有效減少噪聲的鏈接對(duì)潛在表征的負(fù)面影響,Li J.等提出一種無監(jiān)督的特征選擇方法(NetFS),將潛在表征向量嵌入到特征選擇階段中,用優(yōu)化算法求解后得到每個(gè)節(jié)點(diǎn)屬性的重要性系數(shù),從而篩選得到重要的節(jié)點(diǎn)屬性[5].基于譜圖理論,Zhao Z.等提出一種譜特征選擇框架(SPEC),首先計(jì)算原始數(shù)據(jù)的相似性矩陣,然后計(jì)算每個(gè)特征的權(quán)重分?jǐn)?shù),利用權(quán)重分?jǐn)?shù)判斷特征的好壞[6].此外,考慮到特征矩陣和標(biāo)簽矩陣之間的共享公共模式,Hu L.等提出多標(biāo)簽特征選擇方法(SCMFS),利用耦合矩陣分解(CMF)提取特征和標(biāo)簽之間的共享公共模式,并采用非負(fù)矩陣分解(NMF)來增強(qiáng)特征選擇的可解釋性[7].上述方法中,除了LUFS[4]和NetFS[5]結(jié)合網(wǎng)絡(luò)鏈接信息進(jìn)行特征選擇外,其他方法都沒有利用網(wǎng)絡(luò)鏈接信息.

為了更好地在屬性網(wǎng)絡(luò)中實(shí)現(xiàn)社區(qū)發(fā)現(xiàn),除了采用特征選擇,還可以采用屬性網(wǎng)絡(luò)表征學(xué)習(xí),來降低節(jié)點(diǎn)屬性維度.和僅利用網(wǎng)絡(luò)結(jié)構(gòu)信息來獲得低維度潛在特征的網(wǎng)絡(luò)表示方法(DeepWalk[8]、LINE[9]等)不同,屬性網(wǎng)絡(luò)表征學(xué)習(xí)方法不但可以降低節(jié)點(diǎn)屬性的維度,而且能夠有效融合網(wǎng)絡(luò)拓?fù)浜蛯傩孕畔?例如,Huang X.等提出一種通用的嵌入框架 (HILL),同時(shí)融合異構(gòu)信息和拓?fù)湫畔?并且提出一種分布式算法(ADMM算法)完成優(yōu)化求解[10].對(duì)于多視圖網(wǎng)絡(luò),Wang H.等在2019年提出一種基于圖的多視圖聚類(GMC)方法,可以自動(dòng)生成不同視圖的權(quán)重,同時(shí)學(xué)習(xí)每個(gè)不同視圖的圖,并通過拉普拉斯矩陣對(duì)融合后的低維向量施加秩約束,可以自動(dòng)生成聚類結(jié)果[11].Sun F.等提出了一個(gè)概率生成模型(vGraph)來協(xié)作學(xué)習(xí)社區(qū)成員和節(jié)點(diǎn)的低維表示,可以同時(shí)捕獲圖的全局結(jié)構(gòu)和局部結(jié)構(gòu)[12].Zhao Z.等在2021年提出了一種基于深度模型的屬性網(wǎng)絡(luò)嵌入學(xué)習(xí)方法(DeepEmLAN),通過深度注意力模型將不同類型的屬性信息平穩(wěn)地投影到相同的語義空間中,同時(shí)可以保持拓?fù)浣Y(jié)構(gòu),使得有更多鄰居的節(jié)點(diǎn)、有相似文本或者屬性的節(jié)點(diǎn)在表示空間中更加接近[13].上述屬性網(wǎng)絡(luò)表征學(xué)習(xí)方法中,HILL算法沒有深入融合網(wǎng)絡(luò)拓?fù)涞纳顚哟涡畔?GMC方法對(duì)單視圖網(wǎng)絡(luò)的嵌入表示后的聚類效果明顯比不上多視圖的聚類結(jié)果,而vGraph和DeepEmLAN方法都需要標(biāo)簽信息進(jìn)行訓(xùn)練學(xué)習(xí).

為了以無監(jiān)督的方式融合結(jié)構(gòu)和屬性進(jìn)行社區(qū)發(fā)現(xiàn),Zhang B.等在自動(dòng)編碼器框架中,提出了一種新的無監(jiān)督社區(qū)檢測(cè)圖卷積神經(jīng)網(wǎng)絡(luò)方法(GUCD),引入了一個(gè)以社區(qū)為中心的雙解碼器,以無監(jiān)督的方式分別重構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性,還設(shè)計(jì)了一個(gè)局部增強(qiáng)的方案,以適應(yīng)節(jié)點(diǎn)有更多的共同鄰居和相似的屬性與相似的社區(qū)成員[14].GUCD方法是在社區(qū)發(fā)現(xiàn)的同時(shí)融合結(jié)構(gòu)和屬性的,本文主要針對(duì)融合結(jié)構(gòu)和屬性之后進(jìn)行社區(qū)發(fā)現(xiàn).為了更好地處理節(jié)點(diǎn)屬性的高維數(shù)據(jù)以及深入融合網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)重要屬性,本文根據(jù)基于矩陣分解的特征選擇和屬性網(wǎng)絡(luò)表示學(xué)習(xí)提出了一種社區(qū)發(fā)現(xiàn)方法,首先結(jié)合節(jié)點(diǎn)相似性提出聯(lián)合相似度,用改進(jìn)后的特征選擇算法將網(wǎng)絡(luò)中重要的屬性篩選出來,然后將融合鄰居信息的拓?fù)浣Y(jié)構(gòu)和重要屬性聯(lián)合建模,利用基于矩陣分解的屬性網(wǎng)絡(luò)表征方法求解得到節(jié)點(diǎn)嵌入向量,最后用聚類算法實(shí)現(xiàn)社區(qū)發(fā)現(xiàn).實(shí)驗(yàn)結(jié)果表明所提算法具有較好的特征選擇和劃分社區(qū)的效果.

2 問題描述

一個(gè)既有鏈接信息又有節(jié)點(diǎn)屬性信息的復(fù)雜網(wǎng)絡(luò)可以表示為G=(V,E,X),其中V為含有n個(gè)節(jié)點(diǎn)的集合,E為鏈接邊的集合,所有節(jié)點(diǎn)的屬性可以用一個(gè)屬性信息矩陣X∈Rn×m表示,m是屬性類別個(gè)數(shù).對(duì)于屬性網(wǎng)絡(luò),一般圖G為一個(gè)無向無權(quán)圖,可以用eij∈E表示節(jié)點(diǎn)i∈V和節(jié)點(diǎn)j∈V之間的鏈接關(guān)系,如果兩者之間有連邊,則eij=1,否則eij=0.所有節(jié)點(diǎn)的連邊關(guān)系就構(gòu)成一個(gè)鄰接矩陣A.

屬性網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)是為了劃分社區(qū),即使同一社區(qū)內(nèi)的節(jié)點(diǎn)連接緊密,且節(jié)點(diǎn)間的特征信息相似.為了更好地在屬性網(wǎng)絡(luò)中實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)的任務(wù),可以將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)信息以及重要屬性信息,以高效的方式映射到低維的表示空間中,得到節(jié)點(diǎn)的嵌入向量后進(jìn)行社團(tuán)劃分.所以本文問題可以描述為:給定一個(gè)屬性網(wǎng)絡(luò)G=(V,E,X)及其鄰接矩陣A,篩選出t個(gè)重要屬性,與原拓?fù)浣Y(jié)構(gòu)組成一個(gè)新網(wǎng)絡(luò)G′=(V,E,F),其中F∈Rn×t為重要屬性信息矩陣,將網(wǎng)絡(luò)G′的節(jié)點(diǎn)映射成低維向量后進(jìn)行社區(qū)劃分.

3 算法描述

3.1 算法框架

屬性網(wǎng)絡(luò)與傳統(tǒng)網(wǎng)絡(luò)相比,往往節(jié)點(diǎn)本身富含更多的信息.為了有效降低屬性網(wǎng)絡(luò)節(jié)點(diǎn)的維度,同時(shí)深入挖掘網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),將網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)重要屬性進(jìn)行有效融合,達(dá)到良好的社區(qū)發(fā)現(xiàn)性能,本文提出了聯(lián)合重要特征選擇和局部網(wǎng)絡(luò)拓?fù)淝度氲纳鐓^(qū)發(fā)現(xiàn)算法(A Community Detection Method Combining Important Feature Selection and Local Network Topology Embedding,簡(jiǎn)稱FSNE),算法整體框架如圖1所示.

圖1 FSNE算法框架圖Fig.1 FSNE algorithm framework diagram

FSNE算法的第1步是基于節(jié)點(diǎn)聯(lián)合相似度潛在表征的特征選擇,首先計(jì)算節(jié)點(diǎn)的聯(lián)合相似度,將基于聯(lián)合相似度的節(jié)點(diǎn)潛在表征嵌入到特征選擇過程中,篩選得到重要系數(shù)靠前的t個(gè)節(jié)點(diǎn)屬性,與原網(wǎng)絡(luò)拓?fù)浣M成新網(wǎng)絡(luò);第2步是用基于矩陣分解的網(wǎng)絡(luò)嵌入框架將新網(wǎng)絡(luò)映射成低維空間中的向量,首先計(jì)算融合鄰居信息的拓?fù)湎嗨贫群椭匾卣鞯膶傩越咏?基于矩陣分解將拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性聯(lián)合建模求解,得到融合了重要屬性和網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)嵌入向量,最后使用k-means聚類算法進(jìn)行社區(qū)劃分.

3.2 基于節(jié)點(diǎn)聯(lián)合相似度潛在表征的特征選擇

特征選擇可以將屬性網(wǎng)絡(luò)中節(jié)點(diǎn)的有效信息篩選出來,這里屬性也稱之為特征,通過去除不重要的特征,留下的節(jié)點(diǎn)特征集合就可以用來進(jìn)行社區(qū)發(fā)現(xiàn).基于網(wǎng)絡(luò)拓?fù)浣５奶卣鬟x擇方法,一般只是單純利用鄰接矩陣進(jìn)行建模得到潛在表征,但這樣往往會(huì)造成網(wǎng)絡(luò)結(jié)構(gòu)深層次信息的缺失.因此,本文采用節(jié)點(diǎn)相似度以有效地融合網(wǎng)絡(luò)結(jié)構(gòu)的深層次信息,從而更好地輔助特征選擇.

節(jié)點(diǎn)相似性指標(biāo)可以用來作為社區(qū)劃分的依據(jù),不同的指標(biāo)通常從不同的角度描述兩個(gè)節(jié)點(diǎn)之間的相似程度,例如考慮共同鄰居數(shù)的CN指標(biāo)[15]、在CN指標(biāo)上發(fā)展而來的Jaccard指標(biāo)[16]和Sφrenson指標(biāo)[17]、基于節(jié)點(diǎn)間局部點(diǎn)不重復(fù)路徑的SLP指標(biāo)[18]等.在復(fù)雜網(wǎng)絡(luò)中,Jaccard相似性的計(jì)算如式(1)所示:

(1)

其中Γ(i)、Γ(j)分別表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的鄰居,|Γ(i)∩Γ(j)|表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的共同鄰居的數(shù)量,|Γ(i)∪Γ(j)|表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的聯(lián)合鄰居的數(shù)量.當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的Jaccard值越大,表明這兩個(gè)節(jié)點(diǎn)之間的相似度越大.該相似度不僅考慮了兩節(jié)點(diǎn)之間的共同鄰居,而且還納入了兩節(jié)點(diǎn)各自的鄰居信息.

為了更好地利用拓?fù)渖顚哟涡畔⒑凸?jié)點(diǎn)屬性信息,基于Jaccard相似度[16]和Sφrenson相似度[17],本文提出聯(lián)合相似度進(jìn)行建模使?jié)撛诒碚鞲玫剌o助特征選擇.聯(lián)合相似度S不僅考慮了節(jié)點(diǎn)的鄰居信息,而且還考慮了節(jié)點(diǎn)的度信息,可以更深入地表達(dá)拓?fù)湫畔?節(jié)點(diǎn)i和j之間的聯(lián)合相似度Sij如下:

(2)

其中d(i)、d(j)分別表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的度.如果節(jié)點(diǎn)i和j之間沒有共同鄰居,則聯(lián)合相似度Sij為0,否則兩節(jié)點(diǎn)的共同鄰居數(shù)越多,且聯(lián)合鄰居數(shù)和平均度越少,則相似度Sij越大.和Jaccard相似性相比,Sij提升了有共同鄰居的節(jié)點(diǎn)間的相似度,可以更好地挖掘網(wǎng)絡(luò)拓?fù)涞纳顚哟涡畔?

聯(lián)合相似度S比鄰接矩陣A更能挖掘出拓?fù)浣Y(jié)構(gòu)信息.以節(jié)點(diǎn)數(shù)為6的網(wǎng)絡(luò)為例,對(duì)應(yīng)的鄰接矩陣A和聯(lián)合相似度S如圖2所示.例如,節(jié)點(diǎn)3和其鄰居(節(jié)點(diǎn)1、節(jié)點(diǎn)2、節(jié)點(diǎn)4)之間的聯(lián)合相似度S分別為:1.17、0.53、0.45,顯然節(jié)點(diǎn)3和

圖2 鄰接矩陣和聯(lián)合相似度矩陣示例圖Fig.2 Sample diagram of adjacent matrix and joint similarity matrix

節(jié)點(diǎn)1的相似度最高,從圖2的6個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中也可以看到節(jié)點(diǎn)3與節(jié)點(diǎn)1的拓?fù)浣Y(jié)構(gòu)更為相似.而在鄰接矩陣中,節(jié)點(diǎn)3和其鄰居(節(jié)點(diǎn)1、節(jié)點(diǎn)2、節(jié)點(diǎn)4)的相似性并沒有區(qū)別.此外,節(jié)點(diǎn)2與節(jié)點(diǎn)5并沒有共同鄰居,從S矩陣中可以看到節(jié)點(diǎn)2與其鄰居(節(jié)點(diǎn)1、節(jié)點(diǎn)5、節(jié)點(diǎn)3)之間的相似度分別為0.53、0、0.53,因此節(jié)點(diǎn)2跟節(jié)點(diǎn)1、節(jié)點(diǎn)3會(huì)更加相似,而不是和節(jié)點(diǎn)5相似.

為了使?jié)撛谇度氡硎鞠蛄扛玫乇３滞負(fù)涞男再|(zhì),對(duì)網(wǎng)絡(luò)拓?fù)浣?將聯(lián)合相似度矩陣S分解為矩陣因式,得到拓?fù)淝度氲哪繕?biāo)函數(shù)如下:

(3)

為了使?jié)撛诒碚鱈更好地輔助特征選擇,再以L為約束,通過多元線性回歸模型對(duì)節(jié)點(diǎn)屬性信息X進(jìn)行建模,得到特征選擇的目標(biāo)函數(shù)如下:

(4)

最小化式(4)可以使屬性信息矩陣X與轉(zhuǎn)換參數(shù)矩陣Z的積逼近潛在表征L,從而可以幫助特征信息學(xué)習(xí)到更合適的潛在表征,使?jié)撛诒碚骺梢愿玫刂笇?dǎo)特征選擇.

結(jié)合公式(3)和公式(4),得到最終的目標(biāo)函數(shù)如下:

(5)

其中,β是平衡聯(lián)合相似度拓?fù)浣：吞卣鬟x擇的參數(shù).

可以采用交替優(yōu)化算法[5]來求解以公式(5)為目標(biāo)的優(yōu)化問題.當(dāng)L固定時(shí),式(5)是一個(gè)凸函數(shù),因此對(duì)J(Z,L)求導(dǎo),當(dāng)Z趨近于0時(shí),可以得到:

XT(XZ-L)+αDZ=0

(6)

其中,D∈Rm×m是對(duì)角矩陣,它的第i個(gè)對(duì)角元素為:

(7)

其中ε為一個(gè)非常小的常數(shù).由此可以得到:

Z=(XTX+αD)-1XTL

(8)

將式(8)代入式(5),可以得到:

(9)

其中M=XTX+αD.式(9)是一個(gè)標(biāo)準(zhǔn)的約束優(yōu)化問題,可以使用投影梯度法進(jìn)行優(yōu)化:

(10)

令Ll是L的第l次迭代更新,Ll+1的更新如下:

Ll+1=P[Ll-sl▽J(Ll)]

(11)

其中P[Ll-sl▽J(Ll)]是框投影運(yùn)算符,用于將點(diǎn)投影到有界區(qū)域.

當(dāng)L固定時(shí),根據(jù)公式(8)更新Z,而Z固定時(shí),根據(jù)公式(11)更新L,交替進(jìn)行直到目標(biāo)函數(shù)式(5)收斂,由此得到節(jié)點(diǎn)屬性的重要性系數(shù),再利用重要性系數(shù)對(duì)節(jié)點(diǎn)屬性矩陣X進(jìn)行篩選就可以得到節(jié)點(diǎn)重要屬性矩陣F.

3.3 融合共同鄰居信息和重要屬性信息的表示學(xué)習(xí)

為了使聯(lián)合表征向量同時(shí)保持網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)屬性的相似性,文獻(xiàn)[10]對(duì)節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)和屬性信息進(jìn)行聯(lián)合建模,得到拓?fù)浣５哪繕?biāo)函數(shù)為:

(12)

其中,hi∈Rd、hj∈Rd分別代表節(jié)點(diǎn)i和節(jié)點(diǎn)j的節(jié)點(diǎn)嵌入向量,d為節(jié)點(diǎn)嵌入向量的維數(shù).如果節(jié)點(diǎn)i和節(jié)點(diǎn)j存在連接,則Aij=1,否則Aij=0.

文獻(xiàn)[10]只是進(jìn)行簡(jiǎn)單利用鄰接矩陣,并沒有挖掘和融合更深的拓?fù)湫畔?考慮到合適的節(jié)點(diǎn)相似性指標(biāo)可以更好地描繪網(wǎng)絡(luò)拓?fù)涞奶匦?一般認(rèn)為兩個(gè)擁有更多共同鄰居的節(jié)點(diǎn)比兩個(gè)共同鄰居較少的節(jié)點(diǎn)更為相似.因此本文提出融合共同鄰居信息的節(jié)點(diǎn)相似性指標(biāo)如下:

(13)

節(jié)點(diǎn)相似度SAij為節(jié)點(diǎn)i和節(jié)點(diǎn)j的相似性.如果節(jié)點(diǎn)i與j相連,由式(13)可知,SAij為節(jié)點(diǎn)i和節(jié)點(diǎn)j的共同鄰居數(shù)|Γ(i)∩Γ(j)|在總節(jié)點(diǎn)數(shù)n中的占比.如果節(jié)點(diǎn)i和節(jié)點(diǎn)j不相連,則SAij為0.

將篩選得到的節(jié)點(diǎn)重要屬性矩陣F和原拓?fù)浣Y(jié)構(gòu)組成一個(gè)新網(wǎng)絡(luò)后,可以基于節(jié)點(diǎn)相似性對(duì)其拓?fù)湫畔⒔?使節(jié)點(diǎn)嵌入向量更好地表征拓?fù)湫畔?拓?fù)浣５哪繕?biāo)為最小化式(14):

(14)

重要屬性建模是基于屬性接近度來構(gòu)建的,屬性接近度可以用來描述兩節(jié)點(diǎn)之間重要屬性的相似程度[19],采用余弦相似度,公式如下:

(15)

進(jìn)而對(duì)節(jié)點(diǎn)重要屬性信息進(jìn)行建模,其目標(biāo)為最小化式(16):

(16)

通過最小化式(16)可以使節(jié)點(diǎn)嵌入矩陣H∈Rn×d和HT∈Rd×n的積近似逼近屬性接近度矩陣SF∈Rn×n,使得到的節(jié)點(diǎn)嵌入向量很好地保持屬性接近度.

因此,對(duì)融合共同鄰居信息的節(jié)點(diǎn)相似度矩陣SA∈Rn×n和重要屬性接近度矩陣SF聯(lián)合建模,得到最終的目標(biāo)函數(shù)如下:

(17)

其中λ是拓?fù)浣Ｅc屬性建模所占比例的權(quán)衡系數(shù),λ越大表示拓?fù)浣Y(jié)構(gòu)信息考慮得越多.

上述以式(17)為目標(biāo)函數(shù)的優(yōu)化問題可以重新表述為一個(gè)雙凸優(yōu)化問題[10].令Y=H,可以將公式(17)重新表述為一個(gè)線性約束問題:

(18)

得到該雙凸優(yōu)化問題的增廣拉格朗日函數(shù)如下:

(19)

其中增廣拉格朗日參數(shù)ρ>0,ui為對(duì)偶變量,i=1,2,3,…,n.用ADMM算法[10]求解該函數(shù),迭代方法如下:

(20)

(21)

Ul+1=Ul+(Hl+1-Yl+1)

(22)

其中,l為迭代次數(shù).

對(duì)式(20)和式(21)求導(dǎo)得到hi和yi的更新公式如下:

(23)

(24)

其中I為單位矩陣.

綜上所述,對(duì)融合共同鄰居信息的節(jié)點(diǎn)相似度矩陣SA和重要屬性接近度矩陣SF聯(lián)合建模后,采用ADMM算法[10],根據(jù)式(23)和式(24) 分別迭代更新hi和yi,直到目標(biāo)函數(shù)式(17)收斂,就可以得到節(jié)點(diǎn)嵌入向量.

3.4 算法步驟和復(fù)雜度分析

本文算法分為兩個(gè)階段:第1階段為基于節(jié)點(diǎn)聯(lián)合相似度潛在表征的特征選擇,第2階段為融合鄰居信息和重要屬性表征學(xué)習(xí)的社區(qū)發(fā)現(xiàn),算法的主要步驟如下:

步驟1.針對(duì)屬性網(wǎng)絡(luò)G=(V,E,X)及其鄰接矩陣A,設(shè)置待選擇的重要屬性個(gè)數(shù)t、節(jié)點(diǎn)嵌入向量的維數(shù)d和參數(shù)α、β、λ,并根據(jù)式(2)計(jì)算節(jié)點(diǎn)聯(lián)合相似度矩陣S;

步驟2.根據(jù)式(3)和式(4)分別對(duì)基于節(jié)點(diǎn)聯(lián)合相似度S的拓?fù)浣Y(jié)構(gòu)信息和節(jié)點(diǎn)屬性信息X進(jìn)行建模;

步驟3.以公式(5)為目標(biāo)函數(shù),采用交替優(yōu)化算法,根據(jù)公式(11)和公式(8)交替更新潛在表征L和轉(zhuǎn)換參數(shù)矩陣Z;

步驟4.重復(fù)步驟3直到目標(biāo)函數(shù)式(5)收斂,得到節(jié)點(diǎn)屬性的重要程度系數(shù),篩選出前t個(gè)重要的節(jié)點(diǎn)特征,得到重要屬性信息矩陣F;

步驟5.構(gòu)建新網(wǎng)絡(luò)G′=(V,E,F),根據(jù)式(13)計(jì)算融合共同鄰居信息的節(jié)點(diǎn)相似度,得到節(jié)點(diǎn)相似度矩陣SA;

步驟6.根據(jù)式(15) 計(jì)算重要屬性接近度,得到重要屬性接近度矩陣SF;

步驟7.對(duì)SA和SF聯(lián)合建模,以式(17)為目標(biāo)函數(shù),采用ADMM算法,根據(jù)式(23)和式(24)分別更新hi和yi;

步驟8.重復(fù)步驟7,直到目標(biāo)函數(shù)式(17)收斂,得到節(jié)點(diǎn)嵌入向量;

步驟9.運(yùn)行k-means算法對(duì)節(jié)點(diǎn)嵌入向量聚類,得到節(jié)點(diǎn)類別標(biāo)簽,實(shí)現(xiàn)社區(qū)劃分.

上述步驟1計(jì)算聯(lián)合相似度S的復(fù)雜度為O(|E|),|E|為邊的數(shù)量;步驟2～步驟4,使用交替優(yōu)化算法更新Z和L,時(shí)間復(fù)雜度為O(nm2+m3+m2c+ncm),n為總的節(jié)點(diǎn)數(shù)量,其中節(jié)點(diǎn)的屬性類別個(gè)數(shù)m和節(jié)點(diǎn)潛在表征向量的維數(shù)c都是常數(shù),因此時(shí)間復(fù)雜度為O(n);步驟5中計(jì)算相似度SA的復(fù)雜度為O(|E|);步驟6～步驟8的優(yōu)化求解計(jì)算的復(fù)雜度為O(nNF+n2/k),NF為F中非零的個(gè)數(shù),k為ADMM[10]算法中并行處理器的個(gè)數(shù);步驟9中k-means的時(shí)間復(fù)雜度為O(n).一般情況下,n<|E|

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

本節(jié)使用多個(gè)特征選擇算法(LapScore[2]、NDFS[3]、LUFS[4]、NetFS[5]和SPEC[6])、網(wǎng)絡(luò)表示學(xué)習(xí)算法(LINE算法[9]、HILL算法[10]、GMC[11]、vGraph[12]和GUCD[14])與本文算法在3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行對(duì)比分析,所有仿真實(shí)驗(yàn)均在裝有i9 9900kf CPU和64G運(yùn)行內(nèi)存的計(jì)算機(jī)上完成.

4.1 數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

使用3個(gè)經(jīng)典的屬性網(wǎng)絡(luò)真實(shí)數(shù)據(jù)集(社交博客網(wǎng)絡(luò)BlogCatalog[10]、文獻(xiàn)引文網(wǎng)絡(luò)Citeseer[20]和機(jī)器學(xué)習(xí)論文網(wǎng)絡(luò)Cora[21])來測(cè)試算法的性能,如表1所示,Labels表示屬性網(wǎng)絡(luò)的原始的標(biāo)簽數(shù)以及劃分的社區(qū)數(shù).

使用3個(gè)評(píng)價(jià)指標(biāo)分析算法的社團(tuán)劃分性能,分別為ACC、F1-Score和NMI.ACC是用來度量社區(qū)劃分的正確率[22],公式如下:

(25)

表1 3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的基本信息Table 1 Basic information for 3 real networks

其中,gi表示節(jié)點(diǎn)i的真實(shí)標(biāo)簽,ri表示算法求得的節(jié)點(diǎn)i的類別標(biāo)簽,map(ri)為ri在真實(shí)標(biāo)簽集合中找到的一個(gè)最佳匹配的標(biāo)簽.f(a,b)表示符號(hào)函數(shù),若a=b,則f(a,b)=1;否則為0.

F1-Score用于衡量真實(shí)社團(tuán)和算法劃分的社團(tuán)之間的一致程度[13],公式如下:

(26)

其中,precision為查準(zhǔn)率,recall為召回率,定義如下:

(27)

(28)

其中,TP是把兩個(gè)相似節(jié)點(diǎn)歸為同一個(gè)社區(qū)或簇的個(gè)數(shù),FP是把兩個(gè)不相似的節(jié)點(diǎn)歸為同一個(gè)社區(qū)或簇的個(gè)數(shù),FN是把兩個(gè)相似的節(jié)點(diǎn)歸為不同的社區(qū)或者簇的個(gè)數(shù)[23].

歸一化互信息NMI∈[0,1]用于衡量預(yù)測(cè)結(jié)果和真實(shí)結(jié)果的差異[24],其值越接近1表示預(yù)測(cè)結(jié)果越好,公式如下:

(29)

(30)

其中,I(X,Y)表示真實(shí)標(biāo)簽集合Y和預(yù)測(cè)標(biāo)簽集合X之間的互信息度量,H(·)表示熵,p(x,y)是x和y的聯(lián)合概率分布函數(shù),p(x)、p(y)分別是x和y的邊緣概率分布函數(shù).

4.2 結(jié)果對(duì)比分析

4.2.1 特征選擇性能分析

首先,以BlogCatalog數(shù)據(jù)集為例,驗(yàn)證FSNE中特征選擇性能,其中FSNE-J和FSNE-S分別為基于Jaccard相似性的特征選擇和基于聯(lián)合相似度S的特征選擇,通過特征選擇篩選得到重要屬性后用k-means算法聚類.將FSNE-J、FSNE-S和其他5種特征選擇算法,包括LapScore[2]、NDFS[3]、LUFS[4]、NetFS[5]和SPEC[6],在特征的不同維度進(jìn)行比較,聚類后得到的2個(gè)指標(biāo)(ACC和NMI)的對(duì)比如圖3所示.算法參數(shù)設(shè)置如下:NetFS[5]、FSNE-J和FSNE-S的α=10,β=1;LapScore[2]和NDFS[3]的鄰居數(shù)為5,SPEC[6]和LUFS[4]的參數(shù)和原論文相同.

圖3顯示的是FSNE算法的特征選擇部分(FSNE-J、FSNE-S)與其他特征選擇算法在各個(gè)維度上的對(duì)比.圖3中,FSNE-J、FSNE-S算法在維度>600的社團(tuán)劃分性能(ACC和NMI值)均高于其他特征選擇算法,只有在維度為400時(shí)和NetFS算法的性能接近,但還是比其他特征選擇算法性能好.而基于聯(lián)合相似度的特征選擇FSNE-S在維度為600～1600時(shí)取得的ACC值都超越了基于Jaccard相似性的特征選擇FSNE-J的ACC值,而NMI值也僅在1000維時(shí)低于FSNE-J.由此可得,FSNE-S取得了比FSNE-J與其他算法更好的性能,在特征選擇上有良好的效果.

圖3 FSNE-J、FSNE-S與其他特征選擇算法在BlogCatalog上的ACC和NMI值比較Fig.3 ACC and NMI value comparison of FSNE-J,FSNE-S and other feature selection algorithms on BlogCatalog

為了進(jìn)一步驗(yàn)證FSNE中特征選擇部分對(duì)其他數(shù)據(jù)集的特征選擇性能,在3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集Citeseer、BlogCatalog和Cora上對(duì)3個(gè)指標(biāo)(NMI、ACC和F1-Score)進(jìn)行比較,結(jié)果分別如表2～表4所示.

表2～表4顯示的是FSNE-S、FSNE-J和NetFS在3個(gè)數(shù)據(jù)集上各維度的比較.在BlogCatalog和Citeseer數(shù)據(jù)集上,設(shè)定維度為[400,600,800,1000,1200,1400,1600,1800,2000].由于Cora數(shù)據(jù)集上的節(jié)點(diǎn)維度最高為1433維,因此設(shè)定維度為[400,600,800,1000,1200,1400].表中加粗部分為在各指標(biāo)中取得的最高值.

在Blogcatalog數(shù)據(jù)集(見表3)上,FSNE-J取得的NMI值比NetFS高出大約30%.NetFS取得的最高F1-Score值為50.27,此時(shí)FSNE-J為52.07,NetFS的ACC值最高為47.4,而FSNE-J可以達(dá)到51.67,超過NetFS將近10%.在Cora數(shù)據(jù)集上,雖然NetFS的NMI值在1000維時(shí)取到了最好值,但其他維度均低于FSNE-J,對(duì)于F1-Score和ACC值,FSNE-J都取得比NetFS好的效果,分別為39.24和41.21.這是由于,FSNE-J結(jié)合節(jié)點(diǎn)相似度(Jaccard相似性)來輔助特征選擇階段,而NetFS只是利用簡(jiǎn)單的網(wǎng)絡(luò)拓?fù)?挖掘到的信息不多,綜上所述,FSNE-J算法的效果在3個(gè)數(shù)據(jù)集上比NetFS算法都要好.同時(shí)從表中可見,FSNE-J取得的NMI值均低于FSNE-S,可以表明基于聯(lián)合相似度的特征選擇FSNE-S取得了良好的效果.

表2 Citeseer上FSNE-J、FSNE-S和NetFS的3個(gè)指標(biāo)對(duì)比Table 2 Comparison of FSNE-J、FSNE-S and NetFS in three indicators on the Citeseer

表3 BlogCatalog上FSNE-J、FSNE-S和NetFS的3個(gè)指標(biāo)對(duì)比Table 3 Comparison of FSNE-J、FSNE-S and NetFS in three indicators on the BlogCatalog

表4 Cora上FSNE-J、FSNE-S和NetFS的3個(gè)指標(biāo)對(duì)比Table 4 Comparison of FSNE-J、FSNE-S and NetFS in three indicators on the Cora

4.2.2 社區(qū)劃分性能分析

為了驗(yàn)證FSNE算法在社區(qū)發(fā)現(xiàn)任務(wù)上的性能,首先與LINE算法[9]、HILL算法[10]、GMC[11]和NetFS[5]等進(jìn)行對(duì)比,其中FSNE-A是聯(lián)合節(jié)點(diǎn)重要屬性F和鏈接矩陣A嵌入的社區(qū)發(fā)現(xiàn)方法,它和FSNE算法的特征選擇部分相同,但篩選出重要特征后用一般鏈接矩陣的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)嵌入(見公式(12))進(jìn)行社區(qū)劃分.算法參數(shù)設(shè)置如下:LINE[9]的最小批量大小為128,學(xué)習(xí)率為0.025,負(fù)采樣的數(shù)量為5;HILL[10]算法中,Blogcatalog數(shù)據(jù)集的λ=10-0.6,Citeseer數(shù)據(jù)集和Cora數(shù)據(jù)集的λ=0.86;FSNE-A和FSNE中,Blogcatalog數(shù)據(jù)集的λ=1,Citeseer數(shù)據(jù)集和Cora數(shù)據(jù)集的λ=0.001;GMC[11]的參數(shù)和原論文一樣.LINE[9]、HILL[10]、FSNE-A和FSNE的節(jié)點(diǎn)嵌入向量維數(shù)d=100;NetFS[5]、FSNE-J、FSNE-S、FSNE-A和FSNE中,Blogcatalog數(shù)據(jù)集的節(jié)點(diǎn)特征維數(shù)為1600,Citeseer數(shù)據(jù)集和Cora數(shù)據(jù)集的節(jié)點(diǎn)特征維數(shù)為600.

圖4 FSNE和其他算法的社團(tuán)劃分性能對(duì)比Fig.4 Community partitioning performance comparison of FSNE and other algorithms

圖4(a)～圖4(c)分別為FSNE算法與其他算法在3個(gè)數(shù)據(jù)集上的ACC、NMI、F1-Score的對(duì)比.可以看到,FSNE在3個(gè)數(shù)據(jù)集上的ACC、NMI、F1-Score值高出LINE、GMC、HILL和NetFS算法,這是由于FSNE中的節(jié)點(diǎn)聯(lián)合相似度潛在表征以及融合共同鄰居的結(jié)構(gòu)嵌入能更好地深入挖掘網(wǎng)絡(luò)拓?fù)浞矫娴男畔?但LINE沒有考慮節(jié)點(diǎn)屬性,NetFS沒有深入挖掘拓?fù)浣Y(jié)構(gòu)信息,而GMC、HILL也未較好融合拓?fù)浜蛯傩孕畔?此外,FSNE-A在3個(gè)數(shù)據(jù)集上的ACC、NMI、F1-Score值都高于HILL算法,因?yàn)镕SNE-A在HILL算法的基礎(chǔ)上融合了節(jié)點(diǎn)重要屬性信息,而不是節(jié)點(diǎn)的所有屬性,由此驗(yàn)證了基于節(jié)點(diǎn)聯(lián)合相似度的特征選擇是可以進(jìn)一步提高屬性網(wǎng)絡(luò)表示學(xué)習(xí)性能的.在3個(gè)數(shù)據(jù)集上的ACC、NMI、F1-Score值,基于節(jié)點(diǎn)聯(lián)合相似度潛在表征的FSNE-S高于基于Jaccard相似性表征的FSNE-J,而FSNE-J又高于NetFS,說明網(wǎng)絡(luò)拓?fù)涞纳顚哟涡畔⒖梢愿行У刂笇?dǎo)特征選擇,從而提高社團(tuán)發(fā)現(xiàn)的性能;同時(shí),FSNE高于FSNE-A,而FSNE-A又高于FSNE-S,說明得到節(jié)點(diǎn)的重要屬性后,把節(jié)點(diǎn)重要屬性進(jìn)一步和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)聯(lián)合嵌入得到節(jié)點(diǎn)向量表示,特別是深入挖潛網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),把局部鏈接(即共同鄰居)信息和節(jié)點(diǎn)重要屬性信息聯(lián)合嵌入得到節(jié)點(diǎn)向量表示可以更好地實(shí)現(xiàn)社區(qū)劃分,圖4表明了FSNE在社區(qū)劃分上的性能優(yōu)勢(shì).

表5 FSNE和HILL、vGraph、GUCD的對(duì)比Table 5 FSNE compared with HILL,vGraph and GUCD

為了進(jìn)一步分析所提FSNE算法的社團(tuán)劃分性能,FSNE算法和HILL、vGraph[12]、GUCD[14]在Cora和Citeseer數(shù)據(jù)集上進(jìn)行了比對(duì).vGraph[12]的節(jié)點(diǎn)嵌入維數(shù)d設(shè)置為100,其它參數(shù)設(shè)置和原文一樣.由表5可知,在Citeseer數(shù)據(jù)集上,FSNE的 ACC值和NMI值是最高的;而Cora數(shù)據(jù)集上,其ACC值和NMI值位居第2,僅次于GUCD[14],但仍然高于HILL和vGraph[12].因?yàn)镕SNE算法深入挖掘網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)(共同鄰居信息)來提高社區(qū)檢測(cè)的性能.由于Cora和Citeseer在構(gòu)建鄰接矩陣時(shí)存在邊數(shù)少于實(shí)際邊數(shù)的情況,其中缺失邊率分別為2.8%和1.5%.FSNE算法對(duì)Citeseer的求解性能優(yōu)于Cora,同時(shí)也體現(xiàn)了挖掘共同鄰居信息的效果.

圖5 FSNE在不同參數(shù)下的NMI、F1-score和ACC值Fig.5 NMI,F1-score and ACC values of JSNE with different parameters

4.2.3 參數(shù)分析

對(duì)FSNE算法的參數(shù)α、β設(shè)置同NetFS,有關(guān)α、β的分析見文獻(xiàn)[5],這里對(duì)FSNE算法的另一個(gè)參數(shù)λ進(jìn)行了仿真實(shí)驗(yàn)以及分析.圖5分別展示了FSNE算法在3個(gè)數(shù)據(jù)集上不同參數(shù)λ下的NMI、F1-socre和ACC值,λ分別設(shè)置為0.001,0.01,0.1,1,10,100和1000.在BlogCatalog數(shù)據(jù)集中,FSNE取得的NMI、F1-socre和ACC值曲線的趨勢(shì)隨著參數(shù)λ的上升到達(dá)最高點(diǎn)后,然后不斷下降.在Citeseer數(shù)據(jù)集中,可以看到最高點(diǎn)在0.001處,而且在Cora數(shù)據(jù)集中,曲線的變化不大,是由于節(jié)點(diǎn)的屬性維度本身就較小,因此參數(shù)的變化對(duì)效果影響不大.因此這3個(gè)數(shù)據(jù)集中λ參數(shù)設(shè)定如下:BlogCatalog的λ=1,而Citeseer和Cora中λ=0.001.

5 結(jié) 論

從屬性網(wǎng)絡(luò)表征學(xué)習(xí)的角度出發(fā),結(jié)合特征選擇,本文提出了基于節(jié)點(diǎn)聯(lián)合相似度潛在表征的特征選擇,將篩選后得到前t個(gè)重要屬性,與原拓?fù)浣M成新網(wǎng)絡(luò),通過基于矩陣分解的屬性網(wǎng)絡(luò)表征學(xué)習(xí)框架將局部鏈接拓?fù)浜凸?jié)點(diǎn)重要屬性聯(lián)合建模得到節(jié)點(diǎn)嵌入向量,然后用k-means算法聚類實(shí)現(xiàn)社區(qū)劃分.3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的仿真實(shí)驗(yàn)驗(yàn)證了本文算法不僅具有良好的特征選擇性能,而且具有優(yōu)良的社區(qū)劃分算法性能.未來,準(zhǔn)備研究動(dòng)態(tài)屬性網(wǎng)絡(luò)嵌入及其與多元信息融合,同時(shí)解決特征選擇維度的自動(dòng)確定問題,以便更好地應(yīng)用于電商網(wǎng)絡(luò)流量聚合、社交平臺(tái)興趣發(fā)現(xiàn)和金融領(lǐng)域反詐騙等實(shí)際場(chǎng)景.