約束張量規(guī)范多元分解時(shí)變社區(qū)圖模型檢測(cè)

趙 莉，李宗明

(1.武漢東湖學(xué)院 計(jì)算機(jī)科學(xué)學(xué)院，湖北 武漢 430212；2.武漢大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430212)

0 引 言

復(fù)雜現(xiàn)實(shí)網(wǎng)絡(luò)的圖形表示提供了社會(huì)、生物和金融網(wǎng)絡(luò)中存在的寶貴內(nèi)在屬性，一般存在小的子圖，稱為“社區(qū)”或“集群”，其密集內(nèi)部連接和稀疏外部連接可表征參與實(shí)體(節(jié)點(diǎn))間潛在“關(guān)聯(lián)”[1,2]。社區(qū)識(shí)別目標(biāo)是發(fā)現(xiàn)這種高度交織的節(jié)點(diǎn)，如揭示大腦、社交媒體中的趨勢(shì)分析以及推薦系統(tǒng)中的客戶群等[3,4]。

現(xiàn)有社區(qū)檢測(cè)工具包括基于模塊最大化、生成和統(tǒng)計(jì)模型的研究，例如，文獻(xiàn)[5]提出基于混合成員隨機(jī)塊模型(MMSB)的社區(qū)檢測(cè)算法，實(shí)現(xiàn)對(duì)社區(qū)深層次信息發(fā)掘；文獻(xiàn)[6]提出局部度量?jī)?yōu)化社區(qū)檢測(cè)算法，提高算法收斂速度；文獻(xiàn)[7]提出基于譜聚類社區(qū)檢測(cè)算法，缺點(diǎn)是聚類算法在計(jì)算效率上無(wú)法保證；文獻(xiàn)[8]提出基于矩陣分解模型社區(qū)檢測(cè)算法，但矩陣分解模型構(gòu)建較復(fù)雜。隨著對(duì)當(dāng)代現(xiàn)實(shí)網(wǎng)絡(luò)的探索性研究，對(duì)社區(qū)節(jié)點(diǎn)的多模式交互、節(jié)點(diǎn)和節(jié)點(diǎn)間的連接邊相關(guān)信息的開(kāi)發(fā)以及動(dòng)態(tài)交互等方面提出新挑戰(zhàn)，上述文獻(xiàn)算法均無(wú)法有效解決此類問(wèn)題。為此，文獻(xiàn)[9]構(gòu)造高階張量模型，如果一組節(jié)點(diǎn)共同屬于一循環(huán)，則其條目為非零，而文獻(xiàn)[10]則通過(guò)張量模型捕捉群體社區(qū)的時(shí)間動(dòng)態(tài)屬性。在一定條件下，張量分解是唯一的，可保證群落結(jié)構(gòu)的可識(shí)別性。

本文提出一種基于張量的網(wǎng)絡(luò)表示方法。每個(gè)節(jié)點(diǎn)定義Egonet作為由節(jié)點(diǎn)本身、其期望鄰居及其所有連接所構(gòu)成的子圖。通過(guò)構(gòu)建新網(wǎng)絡(luò)表示形式，可實(shí)現(xiàn)對(duì)其單跳連接模式之外節(jié)點(diǎn)信息捕獲。同時(shí)，為所提約束非凸優(yōu)化開(kāi)發(fā)了具有收斂性保證的解算器，用于社區(qū)分配，揭示了可能重疊的社區(qū)。

1 模型描述

1.1 張量模型構(gòu)建

(1)

圖1 張量模型構(gòu)建

1.2 社區(qū)分配和評(píng)估

(2)

(1)NMI指標(biāo)可定義為[14,15]

(3)

(4)

(5)

(2)F1分?jǐn)?shù)指標(biāo)可定義為[16]

(6)

2 基于EGONET低秩張量社區(qū)檢測(cè)

2.1 約束張量CPD分解

(1)Egonet-CPD模型構(gòu)建：假設(shè)社區(qū)數(shù)量以K為上界，則可通過(guò)求解以下約束最小二乘(LS)問(wèn)題實(shí)現(xiàn)秩K模型CPD求解

(7)

式中：術(shù)語(yǔ)(ak°bk°ck)是3個(gè)矢量的外積。A:=[a1,…,aK]，B:=[b1,…,bK]，C:=[c1,…,cK]，且有A,B,C∈RN×K≥0，該約束加強(qiáng)了Egonet鄰接矩陣的非負(fù)性，從而引導(dǎo)了所CPD求解結(jié)構(gòu)，并提供了分解因子的解釋。模型(7)可改寫(xiě)為

(8)

(9)

現(xiàn)實(shí)世界中的網(wǎng)絡(luò)通常涉及與多個(gè)社區(qū)關(guān)聯(lián)的節(jié)點(diǎn)，從而對(duì)應(yīng)于通用節(jié)點(diǎn)n，在關(guān)聯(lián)向量中產(chǎn)生多個(gè)非零條目[cn1,cn2,…,cnK]。在施加單純形約束時(shí)，模型(7)可進(jìn)一步正則化為

(10)

(2)Egonet-CPD模型求解：在所提出的交替優(yōu)化方案中，每一步都由固定兩個(gè)因子和最小化第三個(gè)因子引起的子問(wèn)題組成。

步驟1 因子A更新:首先考慮迭代k時(shí)因子A的更新，在確定B=B(k-1)和C=C(k-1)并求解相應(yīng)的最小化后獲得。操作后產(chǎn)生子問(wèn)題如下

(11)

(12)

(13)

(14)

(15)

步驟2 因子B更新:因子B的更新同樣可以通過(guò)求解子問(wèn)題來(lái)實(shí)現(xiàn)

(16)

步驟3 因子C更新: 因子C的更新可通過(guò)將A和B固定在其最新值，并求解子問(wèn)題得到的

(17)

(18)

(19)

然后，ADMM解算器迭代更新過(guò)程如下

(20)

2.2 時(shí)變社區(qū)圖模型檢測(cè)

考慮新社區(qū)產(chǎn)生，新互動(dòng)將反映在在社交聯(lián)系上，在這個(gè)網(wǎng)絡(luò)中，某個(gè)任務(wù)期間不同區(qū)域的激活/失活可通過(guò)時(shí)變圖來(lái)捕捉。目的是利用所提Egoten方法來(lái)識(shí)別動(dòng)態(tài)社區(qū)，以及相應(yīng)節(jié)點(diǎn)時(shí)變關(guān)聯(lián)。

(21)

(22)

(23)

式中：乘向量dtkcnk在t時(shí)提供節(jié)點(diǎn)n與社區(qū)k的關(guān)聯(lián)。類似于式(10)求解，式(23)中的分解通過(guò)交替最小二乘法求解，以更新因子。算法1提供了整體解算器，其中我們使用了前述章節(jié)算法來(lái)處理新出現(xiàn)的子問(wèn)題。

算法1：時(shí)變圖的約束交替最小二乘求解

初始化：A,B,C∈RN×K，D∈RT×K，k=0

重構(gòu)張量矩陣W1，W2，W3，W4：

Whilek

k←k+1；

Endwhile

返回A(k),B(k),C(k),D(k)；

注意，所提分解過(guò)程實(shí)際上是通過(guò)因子D的列來(lái)揭示檢測(cè)到的群落隨時(shí)間的演化，并不是顯式地發(fā)現(xiàn)n節(jié)點(diǎn)的時(shí)間群落關(guān)聯(lián)，而是利用因子D的k-列來(lái)調(diào)節(jié)n節(jié)點(diǎn)與k群落的關(guān)聯(lián)隨時(shí)間的變化，對(duì)于時(shí)間t采用dtk*cnk表示。因此，不同節(jié)點(diǎn)關(guān)聯(lián)將在時(shí)間t以相同方式調(diào)制，而最終結(jié)果同時(shí)受到dtk和cnk的影響。此外，還可聯(lián)合使用因子A、B和C來(lái)發(fā)現(xiàn)節(jié)點(diǎn)社區(qū)關(guān)聯(lián)，應(yīng)對(duì)其它兩個(gè)因子(至少一個(gè))施加類似約束。為了更快地收斂，我們沒(méi)有施加這種額外結(jié)構(gòu)，且僅使用系數(shù)C來(lái)實(shí)現(xiàn)這一目的。

2.3 EGONET低秩張量分析

(24)

(25)

(26)

(27)

(28)

定理1 在SBM(N;2;p;q)網(wǎng)絡(luò)中，其期望鄰接張量近似為q→0的秩2張量

(29)

當(dāng)N足夠大時(shí)，近似誤差為

(30)

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

實(shí)驗(yàn)是在Intel(R)Core i5 3.2 GHz CPU上運(yùn)行的，該實(shí)驗(yàn)主機(jī)具有4個(gè)內(nèi)核CPU和16 GB的運(yùn)行RAM。在本小節(jié)中，評(píng)估了算法1中所提社區(qū)檢測(cè)算法在時(shí)變網(wǎng)絡(luò)上的社區(qū)識(shí)別性能。

3.1 時(shí)變網(wǎng)絡(luò)檢測(cè)性能測(cè)試

圖2 實(shí)驗(yàn)社區(qū)網(wǎng)絡(luò)初始模型(t=1時(shí)刻)

將本文算法的性能與受約束的非負(fù)矩陣分解(NMF)、非負(fù)矩陣分解(NMF)以及三維張量分解方案的性能進(jìn)行了比較，其中使用t時(shí)刻的U和V作為t+1時(shí)刻的初始化模型，以提供一個(gè)隨時(shí)間變化的一致性NMF。還提供了在不使用初始化時(shí)NMF的結(jié)果。此外，通過(guò)三維張量的秩k張量分解，將其性能與社區(qū)檢測(cè)結(jié)果進(jìn)行了比較，張量的第t個(gè)模塊是t時(shí)網(wǎng)絡(luò)的鄰接矩陣。除非總體性約束外，第一和第二因子用Frobenius范數(shù)正則化以解決標(biāo)量模糊性，第三項(xiàng)的行服從單純形約束。這一比較突出了通過(guò)Egonets張量提出的增強(qiáng)網(wǎng)絡(luò)表示優(yōu)點(diǎn)，如圖3所示。

圖3 社區(qū)合成時(shí)變圖NMI指標(biāo)

3.2 真實(shí)網(wǎng)絡(luò)檢測(cè)性能測(cè)試

(31)

圖4 實(shí)驗(yàn)結(jié)果對(duì)比

根據(jù)圖4繪制了傳導(dǎo)率-覆蓋率曲線，結(jié)果表明，通過(guò)Egoten檢測(cè)到的社區(qū)的質(zhì)量與其它方法相比具有顯著的性能優(yōu)勢(shì)。其所具有的線下覆蓋區(qū)域的面積最小，這表明本文算法所獲得的社區(qū)檢測(cè)結(jié)果具有更佳的凝聚力。對(duì)比算法中，Bigclam算法的社區(qū)檢測(cè)效果最差，這主要是Bigclam算法主要針對(duì)大型社區(qū)檢測(cè)過(guò)程中計(jì)算效率提升而設(shè)計(jì)的，其主要側(cè)重于算法計(jì)算效率的提升。Louvain算法的檢測(cè)效果弱于NMSB算法，主要原因是Louvain算法采用了剪枝算法，有助于降低數(shù)據(jù)的處理量，但是在算法精度上相對(duì)不佳。上述實(shí)驗(yàn)結(jié)果驗(yàn)證了所提算法的有效性。

3.3 重疊社區(qū)檢測(cè)實(shí)驗(yàn)

對(duì)于算法重疊社區(qū)檢測(cè)性能驗(yàn)證，本文選取NMI指標(biāo)進(jìn)行實(shí)驗(yàn)評(píng)估。對(duì)于兩個(gè)社區(qū)A和B的NMI指標(biāo)可定義為

(32)

其中，Cij是重疊社區(qū)頂點(diǎn)，N是頂點(diǎn)數(shù)，CA和CB是社區(qū)數(shù)，C是混淆矩陣。實(shí)驗(yàn)對(duì)象仍然選取Dolphins海豚網(wǎng)絡(luò)和Football足球網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)對(duì)比，這兩種網(wǎng)絡(luò)中存在一定重疊社區(qū)。對(duì)比算法選取文獻(xiàn)[14,15]。結(jié)果如圖5所示。

圖5 NMI實(shí)驗(yàn)對(duì)比結(jié)果

通過(guò)圖5實(shí)驗(yàn)結(jié)果可知，隨著社區(qū)數(shù)量增加，3種對(duì)比算法均表現(xiàn)出一定的下降趨勢(shì)，表明網(wǎng)絡(luò)在多社區(qū)情況下對(duì)于重疊社區(qū)的識(shí)別效果降低，這與重疊社區(qū)情況惡化有一定關(guān)系。從3種算法對(duì)比看，本文算法對(duì)于重疊社區(qū)的惡化具有相對(duì)較強(qiáng)的抵抗能力，表明算法具有相對(duì)更理想的性能。

4 結(jié)束語(yǔ)

本研究提出了一種基于張量的高階節(jié)點(diǎn)連通性捕獲方法。構(gòu)造的Egonet張量中的誘導(dǎo)冗余賦予了新的具有豐富結(jié)構(gòu)的表示方法，并將該問(wèn)題作為約束張量分解任務(wù)，用于群體檢測(cè)。張量稀疏和并行計(jì)算的應(yīng)用使該算法具有可擴(kuò)展性，而結(jié)構(gòu)化冗余增強(qiáng)了對(duì)重疊和高度混合的群體的性能。該框架被擴(kuò)展以適應(yīng)時(shí)變圖，其中四維張量能夠在整個(gè)范圍內(nèi)同時(shí)進(jìn)行社區(qū)識(shí)別，從而提高了社區(qū)檢測(cè)算法性能。

這種方法強(qiáng)調(diào)了靈活性和冗余之間的權(quán)衡，因?yàn)橄鄳?yīng)CPD的內(nèi)存和計(jì)算強(qiáng)度以及參數(shù)的適當(dāng)調(diào)整將影響檢測(cè)社區(qū)的質(zhì)量。下一步工作中，可以分析這種權(quán)衡，進(jìn)一步描述隨著擴(kuò)展覆蓋范圍的增加，被檢測(cè)社區(qū)的質(zhì)量是如何演變的，這超出了本文研究范圍，將在后續(xù)工作中進(jìn)行擴(kuò)展。