馬曉峰 耿君鋒 范 超

1(中國(guó)人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 河南 鄭州 450000) 2(國(guó)防科技大學(xué)信息通信學(xué)院 湖南 長(zhǎng)沙 410073)

0 引 言

在社交網(wǎng)絡(luò)中，用戶真實(shí)社區(qū)歸屬是客觀存在的[1]，社區(qū)檢測(cè)方法能否獲得與客觀相符的用戶社區(qū)歸屬劃分結(jié)果既取決于方法的可靠性，又取決于數(shù)據(jù)的真實(shí)性。然而，由于網(wǎng)絡(luò)用戶行為的復(fù)雜性，非常可靠并且真實(shí)的數(shù)據(jù)通常是難以獲取的，這主要表現(xiàn)在干擾數(shù)據(jù)、無(wú)用數(shù)據(jù)、矛盾數(shù)據(jù)等的廣泛存在，并且很多情況下還存在用戶數(shù)據(jù)缺失的現(xiàn)象。例如，在Tweets用戶交流中，兩個(gè)用戶間存在相互關(guān)注關(guān)系，但是可能一個(gè)用戶只聽(tīng)不說(shuō)，那么該用戶的內(nèi)容特征就為空；同樣的，一些用戶可能經(jīng)常發(fā)表一些內(nèi)容來(lái)表達(dá)自己的觀點(diǎn)，但是并不關(guān)注其他人或者不添加粉絲等，那么他們就沒(méi)有鏈接關(guān)系數(shù)據(jù)。在社交網(wǎng)絡(luò)中，某些內(nèi)容屬性數(shù)據(jù)缺失或者鏈接關(guān)系數(shù)據(jù)缺失的用戶廣泛存在，這些用戶稱為孤立節(jié)點(diǎn)。孤立節(jié)點(diǎn)存在有多種原因，如網(wǎng)絡(luò)中的“僵尸賬號(hào)”的存在造成用戶鏈接關(guān)系網(wǎng)絡(luò)十分稀疏，或者用戶與其他用戶交流數(shù)據(jù)很少造成節(jié)點(diǎn)數(shù)據(jù)很少等。在數(shù)據(jù)提取時(shí)，由于存在部分孤立節(jié)點(diǎn)，因此會(huì)形成大量的部分?jǐn)?shù)據(jù)集。對(duì)于社區(qū)檢測(cè)來(lái)講，如何針對(duì)這些缺失數(shù)據(jù)，實(shí)現(xiàn)有效的信息互補(bǔ)，進(jìn)而獲得更好的社區(qū)檢測(cè)結(jié)果，是十分有必要的。

與一般數(shù)據(jù)不全現(xiàn)象相比，這里部分?jǐn)?shù)據(jù)集表現(xiàn)在用戶某一視角信息全部丟失，而不是丟失某一視角信息中的部分特征數(shù)據(jù)。目前，許多研究集中于處理數(shù)據(jù)不全等問(wèn)題[2-3]，但是對(duì)于部分?jǐn)?shù)據(jù)集的社區(qū)檢測(cè)研究不多。多視角聚類[4]依靠不同視角之間的信息補(bǔ)充提高聚類的性能，由于用戶存在多個(gè)視角，不同視角之間可以相互補(bǔ)充，這為部分?jǐn)?shù)據(jù)集的融合聚類提供了有效的方法。但是，如何有效處理孤立節(jié)點(diǎn)，使得算法更加魯棒，避免因?yàn)楣铝⒐?jié)點(diǎn)而造成性能的急劇下降，是一個(gè)重要的研究?jī)?nèi)容，特別是在不同視角之間數(shù)據(jù)質(zhì)量差異較大的情況下，顯得尤為重要。

文獻(xiàn)[2]首先研究了包含兩個(gè)視角的部分?jǐn)?shù)據(jù)集聚類問(wèn)題。在該方法中，數(shù)據(jù)節(jié)點(diǎn)被分為包含每個(gè)視角數(shù)據(jù)的正常數(shù)據(jù)和只包含一個(gè)視角信息的部分?jǐn)?shù)據(jù)節(jié)點(diǎn)，對(duì)于正常數(shù)據(jù)，仍舊采用NMF(Nonnegative Matrix Factorization)的融合策略進(jìn)行多視角融合，而對(duì)于部分?jǐn)?shù)據(jù)節(jié)點(diǎn)，則不進(jìn)行多視角融合，只在單視角內(nèi)進(jìn)行數(shù)據(jù)聚類。其目標(biāo)函數(shù)描述如下：

(1)

s.t.U1≥0U2≥0

在此基礎(chǔ)上，文獻(xiàn)[5-6]在聚類過(guò)程中，對(duì)每個(gè)視角引入了圖正則信息以強(qiáng)化節(jié)點(diǎn)的局部結(jié)構(gòu)保持特性。同樣的，基于該思想，文獻(xiàn)[7]則研究了如何實(shí)現(xiàn)算法的“online”處理。文獻(xiàn)[8]則建立了針對(duì)部分?jǐn)?shù)據(jù)集的監(jiān)督特征提取方法。

在網(wǎng)絡(luò)社區(qū)檢測(cè)中，可以借鑒多視角聚類的方法研究部分?jǐn)?shù)據(jù)集的社區(qū)檢測(cè)問(wèn)題。一種思想如文獻(xiàn)[2]所述，對(duì)孤立節(jié)點(diǎn)不進(jìn)行處理；另一種思想是對(duì)于孤立節(jié)點(diǎn)，通過(guò)沒(méi)有缺失數(shù)據(jù)的視角，找到該節(jié)點(diǎn)的最近鄰，利用最近鄰節(jié)點(diǎn)的特征信息作為該孤立節(jié)點(diǎn)的特征，參與到多視角融合當(dāng)中，從而實(shí)現(xiàn)部分?jǐn)?shù)據(jù)集的多視角聚類。

1 多視角數(shù)據(jù)融合社區(qū)檢測(cè)算法

1.1 正則約束項(xiàng)構(gòu)造

文獻(xiàn)[2]利用兩個(gè)視角的統(tǒng)一低維表示矩陣來(lái)構(gòu)建融合策略，這里仍采用視角之間的差來(lái)描述視角之間的融合：

(2)

為了在部分?jǐn)?shù)據(jù)集的情況下建立融合正則項(xiàng)，需要引入指示矩陣來(lái)加以區(qū)分?？紤]兩種正則約束項(xiàng)。第一種：對(duì)于內(nèi)容屬性數(shù)據(jù)Xn×m，若Xn×m是部分?jǐn)?shù)據(jù)集，則可以構(gòu)造缺失用戶指示矩陣MM_C∈n×n，公式如下：

(3)

第二種：考慮多視角數(shù)據(jù)集，不同視角所描述的社區(qū)結(jié)構(gòu)是一致的，可以利用其他視角中該用戶的最近鄰信息作為該用戶的約束信息構(gòu)造約束項(xiàng)。設(shè)Xn×m中用戶i沒(méi)有數(shù)據(jù)信息，而鏈接關(guān)系矩陣Gn×n中用戶i存在鏈接關(guān)系信息，利用CAN(Clustering with Adaptive Neighbors)算法[9]可以找到用戶i的最近鄰用戶j。這里認(rèn)為用戶i與其最近鄰j具有最高的相似性，兩者的社區(qū)信息是一致，故可以構(gòu)造缺失用戶指示矩陣MC∈n×n，公式如下：

(4)

同理，對(duì)于鏈接關(guān)系矩陣Gn×n，也可以構(gòu)造兩種缺失用戶指示矩陣：MM_L∈n×n和ML∈n×n，公式如下：

(5)

(6)

據(jù)此，可以構(gòu)造兩種融合約束正則項(xiàng)如下：

(7)

(8)

對(duì)于第一種，其表示：對(duì)于缺失的用戶數(shù)據(jù)，在融合約束中將其剔除掉，即只考慮對(duì)于兩種視角的數(shù)據(jù)都有的用戶進(jìn)行融合，而對(duì)于某種視角數(shù)據(jù)缺失的用戶不進(jìn)行約束；對(duì)于第二種，在融合約束時(shí)，利用沒(méi)有缺失數(shù)據(jù)的最近鄰關(guān)系來(lái)彌補(bǔ)缺失的視角數(shù)據(jù)信息，即對(duì)于內(nèi)容數(shù)據(jù)缺失的用戶，在進(jìn)行視角逼近時(shí)，利用鏈接關(guān)系數(shù)據(jù)的最近鄰用戶的數(shù)據(jù)代替該用戶缺失的數(shù)據(jù)。

由此構(gòu)建兩種優(yōu)化目標(biāo)如下：

(9)

s.t.V≥0,H≥0,SX≥0,SG≥0

(10)

s.t.V≥0,H≥0,SX≥0,SG≥0

1.2 優(yōu)化目標(biāo)的求解

優(yōu)化目標(biāo)J2可以重新描述為：

αtr(MCHHTMCT-MCHVTMLT-MLVHTMCT+MLVVTMLT)

(11)

引入拉格朗日算子ω1、ω2、ω3、ω4分別約束H≥0,V≥0,SX≥0,SG≥0，則拉格朗日函數(shù)L描述為：

L=J2+ω1tr(HT)+ω2tr(VT)+ω3tr(SXT)+ω4tr(SGT)

(12)

L對(duì)H、V、SX,SG的一階導(dǎo)數(shù)分別為：

(13)

(14)

(15)

(16)

據(jù)KKT條件[10], 令ω1(ij)H(ij)=0,ω2(ij)V(ij)=0,ω3(ij)SX(ij)=0,ω4(ij)SG(ij)=0,則：

同理可求得針對(duì)V的KKT條件，整理可得迭代公式：

(17)

(18)

(19)

(20)

綜上，經(jīng)過(guò)迭代計(jì)算可以獲得每個(gè)視角的社區(qū)指示矩陣H和V，再利用K-近鄰分類法的方法將節(jié)點(diǎn)歸屬到相應(yīng)的社區(qū)中去。

算法：基于多視角數(shù)據(jù)融合和NMF的社區(qū)檢測(cè)算法 輸入：鏈接關(guān)系矩陣Gn×n, 屬性矩陣Xm×n，參數(shù){θ,α}, 聚類個(gè)數(shù)K;

輸出：聚類指示矩陣H、V；

1 初始化H、V、SX、SG

2 While 迭代次數(shù)和優(yōu)化誤差< 閾值do

3 正則化SX、H

4 正則化SG、V

5 更新Hby 式(17)

6 更新SXby 式(18)

7 更新Vby 式(19)

8 更新SGby 式(20)

9 End

10 返回H、V

1.3 算法復(fù)雜性分析

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

2.1 數(shù)據(jù)集與實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中用到如下三個(gè)數(shù)據(jù)集：

CiteSeer[11]：該數(shù)據(jù)集包含3 312個(gè)節(jié)點(diǎn)和4 732條邊，每一個(gè)節(jié)點(diǎn)代表一篇科技文獻(xiàn)，每一條邊代表科技文獻(xiàn)之間的引用關(guān)系，此外每一個(gè)節(jié)點(diǎn)都關(guān)聯(lián)一個(gè)類別屬性，社區(qū)數(shù)為6。

Cora[12]：該數(shù)據(jù)集也是科技文獻(xiàn)引文網(wǎng)絡(luò)數(shù)據(jù)集，包含2 708個(gè)節(jié)點(diǎn)和5 429條邊，每一個(gè)節(jié)點(diǎn)都關(guān)聯(lián)一個(gè)類別屬性，社區(qū)數(shù)為7。

WebKB[13]：該數(shù)據(jù)集由 Cornell、Texas、Washington、Wisconsin等4所大學(xué)的網(wǎng)頁(yè)及網(wǎng)頁(yè)之間的鏈接關(guān)聯(lián)關(guān)系構(gòu)成，共分為5個(gè)社區(qū)。

實(shí)驗(yàn)設(shè)置如下：

(2) 缺失數(shù)據(jù)選擇：針對(duì)內(nèi)容屬性數(shù)據(jù)X，按照[0, 0.05,0.1, 0.2, 0.3, 0.4, 0.5,]的比例，在所用節(jié)點(diǎn)中隨機(jī)選取若干設(shè)置X的行向量為0，分別根據(jù)兩種不同的約束正則項(xiàng)與鏈接關(guān)系網(wǎng)絡(luò)進(jìn)行融合社區(qū)檢測(cè)，統(tǒng)計(jì)結(jié)果的AC(Accuracy)和NMI(Normalized mutual information)[14]；針對(duì)鏈接關(guān)系網(wǎng)絡(luò)cites、inbound和outbound，分別按照上述比例隨機(jī)選取若干節(jié)點(diǎn)，并在這三個(gè)網(wǎng)絡(luò)中隨機(jī)設(shè)置節(jié)點(diǎn)的所有鏈接關(guān)系為0。

(3) 正則約束項(xiàng)設(shè)置：根據(jù)算法的兩種正則項(xiàng)生成方法，分別進(jìn)行實(shí)驗(yàn)，最近鄰產(chǎn)生方法按照文獻(xiàn)[9]的方法進(jìn)行。

(4) 參數(shù)設(shè)置：重復(fù)10次，取10次的平均值作為最終結(jié)果輸出。

2.2 結(jié)果分析與討論

如圖1所示是當(dāng)鏈接關(guān)系數(shù)據(jù)缺失時(shí)的融合算法結(jié)果。圖中，上半部分表示AC值的大小，下半部分表示NMI值的大小。其中“*”表示沒(méi)有數(shù)據(jù)缺失時(shí)的結(jié)果，“Δ”表示沒(méi)有數(shù)據(jù)缺失時(shí)采用NMF[15]、CAN[9]、譜聚類[16]等方法獲得的單視角最好的結(jié)果，“?”表示采用約束2(即最近鄰的信息代替缺失數(shù)據(jù)參加融合約束)時(shí)內(nèi)容數(shù)據(jù)和鏈接關(guān)系數(shù)據(jù)融合的結(jié)果，“+”表示采用約束1(即缺失數(shù)據(jù)不參加融合約束)時(shí)內(nèi)容數(shù)據(jù)和鏈接關(guān)系數(shù)據(jù)融合的結(jié)果。

(a) Wisconsin數(shù)據(jù)集

(b) Washington數(shù)據(jù)集

(c) Texas數(shù)據(jù)集

(d) Cornell數(shù)據(jù)集

(e) Cora數(shù)據(jù)集

(f) CiteSeer數(shù)據(jù)集 圖1 鏈接關(guān)系數(shù)據(jù)缺失時(shí)不同社區(qū)檢測(cè)算法性能比較

從圖1中可以看出：第一，雖然有鏈接關(guān)系數(shù)據(jù)缺失，但是在Wisconsin、Washington、Cornell和CiteSeer數(shù)據(jù)集上，融合算法的性能與沒(méi)有缺失數(shù)據(jù)時(shí)的性能大致相等甚至于略好于它們，這說(shuō)明：① 社區(qū)檢測(cè)算法中，三個(gè)鏈接關(guān)系的融合，可以有效彌補(bǔ)數(shù)據(jù)缺失帶來(lái)的信息丟失，保證了社區(qū)檢測(cè)的穩(wěn)定；② 由于內(nèi)容屬性數(shù)據(jù)的質(zhì)量好于鏈接關(guān)系數(shù)據(jù)，因此減小了鏈接關(guān)系數(shù)據(jù)的缺失對(duì)社區(qū)檢測(cè)結(jié)果的影響；③ 部分鏈接關(guān)系數(shù)據(jù)的缺失客觀上也減少了部分錯(cuò)誤信息的影響和干擾，因此提高了社區(qū)檢測(cè)結(jié)果的精度；④ 兩種融合約束項(xiàng)都可以發(fā)揮較好的互補(bǔ)效果，在Wisconsin數(shù)據(jù)集上，約束2要好于約束1，而在Cornell數(shù)據(jù)集上，約束1要好于約束2。

第二，由于鏈接關(guān)系網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的重要性、作用等不盡相同，即節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位是不相等的，因此，隨著丟失鏈接關(guān)系數(shù)據(jù)的用戶增加，社區(qū)檢測(cè)的結(jié)果并沒(méi)有隨之簡(jiǎn)單的增加或者減少，如在Wisconsin數(shù)據(jù)集中，當(dāng)隨機(jī)丟失5%、10%的數(shù)據(jù)時(shí)，算法性能略有下降，而當(dāng)隨機(jī)丟失30%、40%的數(shù)據(jù)時(shí)，算法的性能略有增加。

第三，在Texas數(shù)據(jù)集上，雖然融合后的結(jié)果在AC值上沒(méi)有超過(guò)譜聚類算法，但是在NMI性能上，算法的結(jié)果要好于單視角，并且隨著隨機(jī)數(shù)據(jù)缺失的 增加，NMI的變化規(guī)律也存在上下波動(dòng)的現(xiàn)象。而在Cora數(shù)據(jù)集上，在AC和NMI上，融合后的結(jié)果沒(méi)有譜聚類好，但是性能的變化規(guī)律與其他數(shù)據(jù)集相同。

圖2所示是當(dāng)內(nèi)容數(shù)據(jù)缺失時(shí)的融合算法結(jié)果?？梢钥吹?，第一，隨著缺失數(shù)據(jù)的增加，算法融合的性能也隨之發(fā)生顯著的有規(guī)律的下降，尤其是當(dāng)缺失數(shù)據(jù)大于30%時(shí)，性能下降明顯，這是因?yàn)椋孩?內(nèi)容數(shù)據(jù)的數(shù)據(jù)質(zhì)量較鏈接關(guān)系數(shù)據(jù)要好，因此內(nèi)容數(shù)據(jù)的缺失對(duì)算法性能的影響比較明顯；② 內(nèi)容數(shù)據(jù)是屬性矩陣，用戶數(shù)據(jù)缺失只影響用戶自己本身，因此隨著缺失數(shù)據(jù)的增加，算法性能存在有規(guī)律的下降，僅在Wisconsin和Cora數(shù)據(jù)集上，當(dāng)缺失數(shù)據(jù)在5%時(shí)，融合后的性能好于沒(méi)有數(shù)據(jù)缺失時(shí)的結(jié)果，在其他數(shù)據(jù)集上，融合后的結(jié)果都隨之減小。

第二，在正則項(xiàng)2和正則項(xiàng)1的約束下，算法融合的性能都隨之發(fā)生有規(guī)律的下降，隨著缺失數(shù)據(jù)的增加，正則項(xiàng)2的性能要略好于正則項(xiàng)1。如在Washington、Cornell、CiteSeer數(shù)據(jù)集上，當(dāng)數(shù)據(jù)缺失40%以上時(shí)，正則項(xiàng)2的性能要高于正則項(xiàng)1。

(a) Wisconsin數(shù)據(jù)集

(b) Washington數(shù)據(jù)集

(c) Texas數(shù)據(jù)集

(d) Cornell數(shù)據(jù)集

(e) Cora數(shù)據(jù)集

(f) CiteSeer數(shù)據(jù)集 圖2 內(nèi)容數(shù)據(jù)缺失時(shí)不同社區(qū)檢測(cè)算法性能比較

比較圖1和圖2也可以發(fā)現(xiàn)，當(dāng)內(nèi)容數(shù)據(jù)質(zhì)量較好，而鏈接關(guān)系數(shù)據(jù)質(zhì)量較差時(shí)，鏈接關(guān)系數(shù)據(jù)的缺失對(duì)社區(qū)檢測(cè)結(jié)果的影響要小于內(nèi)容數(shù)據(jù)的缺失，這也說(shuō)明，本文提出的算法能夠適應(yīng)數(shù)據(jù)質(zhì)量差異大的特點(diǎn)，避免了“1+1<2”的尷尬結(jié)果出現(xiàn)，適應(yīng)性較好。同時(shí)也可以看到，由于節(jié)點(diǎn)在鏈接關(guān)系網(wǎng)絡(luò)中所處的地位、作用不同，節(jié)點(diǎn)數(shù)據(jù)的缺失，會(huì)造成整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)全局的變化，缺失的數(shù)據(jù)越多，網(wǎng)絡(luò)變化越明顯，社區(qū)檢測(cè)的結(jié)果越敏感，因此，獲得真實(shí)反映用戶結(jié)構(gòu)特點(diǎn)的鏈接關(guān)系網(wǎng)絡(luò)對(duì)于社區(qū)檢測(cè)來(lái)說(shuō)也是非常重要的。

3 結(jié) 語(yǔ)

本文對(duì)數(shù)據(jù)缺失情況下的多視角異構(gòu)社區(qū)檢測(cè)問(wèn)題進(jìn)行了討論，構(gòu)造了兩種處理缺失數(shù)據(jù)的正則項(xiàng)，并在此基礎(chǔ)上提出了基于兩種正則項(xiàng)的異構(gòu)多視角社區(qū)檢測(cè)算法。真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，算法能夠適應(yīng)視角性能差別大、數(shù)據(jù)缺失的社區(qū)檢測(cè)問(wèn)題，獲得真實(shí)、可靠的社區(qū)檢測(cè)結(jié)果。