一種基于多視角數據融合的網絡社區檢測算法

2018-07-25 11:35:22馬曉峰耿君鋒

計算機應用與軟件 2018年7期

馬曉峰耿君鋒范超

1(中國人民解放軍戰略支援部隊信息工程大學河南鄭州 450000) 2(國防科技大學信息通信學院湖南長沙 410073)

0 引言

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

與一般數據不全現象相比，這里部分數據集表現在用戶某一視角信息全部丟失，而不是丟失某一視角信息中的部分特征數據。目前，許多研究集中于處理數據不全等問題[2-3]，但是對于部分數據集的社區檢測研究不多。多視角聚類[4]依靠不同視角之間的信息補充提高聚類的性能，由于用戶存在多個視角，不同視角之間可以相互補充，這為部分數據集的融合聚類提供了有效的方法。但是，如何有效處理孤立節點，使得算法更加魯棒，避免因為孤立節點而造成性能的急劇下降，是一個重要的研究內容，特別是在不同視角之間數據質量差異較大的情況下，顯得尤為重要。

文獻[2]首先研究了包含兩個視角的部分數據集聚類問題。在該方法中，數據節點被分為包含每個視角數據的正常數據和只包含一個視角信息的部分數據節點，對于正常數據，仍舊采用NMF(Nonnegative Matrix Factorization)的融合策略進行多視角融合，而對于部分數據節點，則不進行多視角融合，只在單視角內進行數據聚類。其目標函數描述如下：

(1)

s.t.U1≥0U2≥0

在此基礎上，文獻[5-6]在聚類過程中，對每個視角引入了圖正則信息以強化節點的局部結構保持特性。同樣的，基于該思想，文獻[7]則研究了如何實現算法的“online”處理。文獻[8]則建立了針對部分數據集的監督特征提取方法。

在網絡社區檢測中，可以借鑒多視角聚類的方法研究部分數據集的社區檢測問題。一種思想如文獻[2]所述，對孤立節點不進行處理；另一種思想是對于孤立節點，通過沒有缺失數據的視角，找到該節點的最近鄰，利用最近鄰節點的特征信息作為該孤立節點的特征，參與到多視角融合當中，從而實現部分數據集的多視角聚類。

1 多視角數據融合社區檢測算法

1.1 正則約束項構造

文獻[2]利用兩個視角的統一低維表示矩陣來構建融合策略，這里仍采用視角之間的差來描述視角之間的融合：

(2)

為了在部分數據集的情況下建立融合正則項，需要引入指示矩陣來加以區分。考慮兩種正則約束項。第一種：對于內容屬性數據Xn×m，若Xn×m是部分數據集，則可以構造缺失用戶指示矩陣MM_C∈n×n，公式如下：

(3)

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

(4)

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

(5)

(6)

據此，可以構造兩種融合約束正則項如下：

(7)

(8)

對于第一種，其表示：對于缺失的用戶數據，在融合約束中將其剔除掉，即只考慮對于兩種視角的數據都有的用戶進行融合，而對于某種視角數據缺失的用戶不進行約束；對于第二種，在融合約束時，利用沒有缺失數據的最近鄰關系來彌補缺失的視角數據信息，即對于內容數據缺失的用戶，在進行視角逼近時，利用鏈接關系數據的最近鄰用戶的數據代替該用戶缺失的數據。

由此構建兩種優化目標如下：

(9)

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

(10)

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

1.2 優化目標的求解

優化目標J2可以重新描述為：

αtr(MCHHTMCT-MCHVTMLT-MLVHTMCT+MLVVTMLT)

(11)

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

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

(12)

L對H、V、SX,SG的一階導數分別為：

(13)

(14)

(15)

(16)

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

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

(17)

(18)

(19)

(20)

綜上，經過迭代計算可以獲得每個視角的社區指示矩陣H和V，再利用K-近鄰分類法的方法將節點歸屬到相應的社區中去。

算法：基于多視角數據融合和NMF的社區檢測算法輸入：鏈接關系矩陣Gn×n, 屬性矩陣Xm×n，參數{θ,α}, 聚類個數K;

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

1 初始化H、V、SX、SG

2 While 迭代次數和優化誤差< 閾值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 算法復雜性分析

2 實驗結果與分析

2.1 數據集與實驗設置

實驗中用到如下三個數據集：

CiteSeer[11]：該數據集包含3 312個節點和4 732條邊，每一個節點代表一篇科技文獻，每一條邊代表科技文獻之間的引用關系，此外每一個節點都關聯一個類別屬性，社區數為6。

Cora[12]：該數據集也是科技文獻引文網絡數據集，包含2 708個節點和5 429條邊，每一個節點都關聯一個類別屬性，社區數為7。

WebKB[13]：該數據集由 Cornell、Texas、Washington、Wisconsin等4所大學的網頁及網頁之間的鏈接關聯關系構成，共分為5個社區。

實驗設置如下：

(2) 缺失數據選擇：針對內容屬性數據X，按照[0, 0.05,0.1, 0.2, 0.3, 0.4, 0.5,]的比例，在所用節點中隨機選取若干設置X的行向量為0，分別根據兩種不同的約束正則項與鏈接關系網絡進行融合社區檢測，統計結果的AC(Accuracy)和NMI(Normalized mutual information)[14]；針對鏈接關系網絡cites、inbound和outbound，分別按照上述比例隨機選取若干節點，并在這三個網絡中隨機設置節點的所有鏈接關系為0。

(3) 正則約束項設置：根據算法的兩種正則項生成方法，分別進行實驗，最近鄰產生方法按照文獻[9]的方法進行。

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

2.2 結果分析與討論

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

(a) Wisconsin數據集

(b) Washington數據集

(d) Cornell數據集

(e) Cora數據集

(f) CiteSeer數據集圖1 鏈接關系數據缺失時不同社區檢測算法性能比較

從圖1中可以看出：第一，雖然有鏈接關系數據缺失，但是在Wisconsin、Washington、Cornell和CiteSeer數據集上，融合算法的性能與沒有缺失數據時的性能大致相等甚至于略好于它們，這說明：① 社區檢測算法中，三個鏈接關系的融合，可以有效彌補數據缺失帶來的信息丟失，保證了社區檢測的穩定；② 由于內容屬性數據的質量好于鏈接關系數據，因此減小了鏈接關系數據的缺失對社區檢測結果的影響；③ 部分鏈接關系數據的缺失客觀上也減少了部分錯誤信息的影響和干擾，因此提高了社區檢測結果的精度；④ 兩種融合約束項都可以發揮較好的互補效果，在Wisconsin數據集上，約束2要好于約束1，而在Cornell數據集上，約束1要好于約束2。

第二，由于鏈接關系網絡中每個節點的重要性、作用等不盡相同，即節點在網絡中的地位是不相等的，因此，隨著丟失鏈接關系數據的用戶增加，社區檢測的結果并沒有隨之簡單的增加或者減少，如在Wisconsin數據集中，當隨機丟失5%、10%的數據時，算法性能略有下降，而當隨機丟失30%、40%的數據時，算法的性能略有增加。

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

圖2所示是當內容數據缺失時的融合算法結果。可以看到，第一，隨著缺失數據的增加，算法融合的性能也隨之發生顯著的有規律的下降，尤其是當缺失數據大于30%時，性能下降明顯，這是因為：① 內容數據的數據質量較鏈接關系數據要好，因此內容數據的缺失對算法性能的影響比較明顯；② 內容數據是屬性矩陣，用戶數據缺失只影響用戶自己本身，因此隨著缺失數據的增加，算法性能存在有規律的下降，僅在Wisconsin和Cora數據集上，當缺失數據在5%時，融合后的性能好于沒有數據缺失時的結果，在其他數據集上，融合后的結果都隨之減小。

第二，在正則項2和正則項1的約束下，算法融合的性能都隨之發生有規律的下降，隨著缺失數據的增加，正則項2的性能要略好于正則項1。如在Washington、Cornell、CiteSeer數據集上，當數據缺失40%以上時，正則項2的性能要高于正則項1。