約束張量規范多元分解時變社區圖模型檢測

趙 莉，李宗明

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

0 引 言

復雜現實網絡的圖形表示提供了社會、生物和金融網絡中存在的寶貴內在屬性，一般存在小的子圖，稱為“社區”或“集群”，其密集內部連接和稀疏外部連接可表征參與實體(節點)間潛在“關聯”[1,2]。社區識別目標是發現這種高度交織的節點，如揭示大腦、社交媒體中的趨勢分析以及推薦系統中的客戶群等[3,4]。

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

本文提出一種基于張量的網絡表示方法。每個節點定義Egonet作為由節點本身、其期望鄰居及其所有連接所構成的子圖。通過構建新網絡表示形式，可實現對其單跳連接模式之外節點信息捕獲。同時，為所提約束非凸優化開發了具有收斂性保證的解算器，用于社區分配，揭示了可能重疊的社區。

1 模型描述

1.1 張量模型構建

(1)

圖1 張量模型構建

1.2 社區分配和評估

(2)

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

(3)

(4)

(5)

(2)F1分數指標可定義為[16]

(6)

2 基于EGONET低秩張量社區檢測

2.1 約束張量CPD分解

(1)Egonet-CPD模型構建：假設社區數量以K為上界，則可通過求解以下約束最小二乘(LS)問題實現秩K模型CPD求解

(7)

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

(8)

(9)

現實世界中的網絡通常涉及與多個社區關聯的節點，從而對應于通用節點n，在關聯向量中產生多個非零條目[cn1,cn2,…,cnK]。在施加單純形約束時，模型(7)可進一步正則化為

(10)

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

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

(11)

(12)

(13)

(14)

(15)

步驟2 因子B更新:因子B的更新同樣可以通過求解子問題來實現

(16)

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

(17)

(18)

(19)

然后，ADMM解算器迭代更新過程如下

(20)

2.2 時變社區圖模型檢測

考慮新社區產生，新互動將反映在在社交聯系上，在這個網絡中，某個任務期間不同區域的激活/失活可通過時變圖來捕捉。目的是利用所提Egoten方法來識別動態社區，以及相應節點時變關聯。

(21)

(22)

(23)

式中：乘向量dtkcnk在t時提供節點n與社區k的關聯。類似于式(10)求解，式(23)中的分解通過交替最小二乘法求解，以更新因子。算法1提供了整體解算器，其中我們使用了前述章節算法來處理新出現的子問題。

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

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

重構張量矩陣W1，W2，W3，W4：

Whilek

k←k+1；

Endwhile

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

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

2.3 EGONET低秩張量分析

(24)

(25)

(26)

(27)

(28)

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

(29)

當N足夠大時，近似誤差為

(30)

3 實驗分析

實驗是在Intel(R)Core i5 3.2 GHz CPU上運行的，該實驗主機具有4個內核CPU和16 GB的運行RAM。在本小節中，評估了算法1中所提社區檢測算法在時變網絡上的社區識別性能。

3.1 時變網絡檢測性能測試

圖2 實驗社區網絡初始模型(t=1時刻)

將本文算法的性能與受約束的非負矩陣分解(NMF)、非負矩陣分解(NMF)以及三維張量分解方案的性能進行了比較，其中使用t時刻的U和V作為t+1時刻的初始化模型，以提供一個隨時間變化的一致性NMF。還提供了在不使用初始化時NMF的結果。此外，通過三維張量的秩k張量分解，將其性能與社區檢測結果進行了比較，張量的第t個模塊是t時網絡的鄰接矩陣。除非總體性約束外，第一和第二因子用Frobenius范數正則化以解決標量模糊性，第三項的行服從單純形約束。這一比較突出了通過Egonets張量提出的增強網絡表示優點，如圖3所示。

圖3 社區合成時變圖NMI指標

3.2 真實網絡檢測性能測試

(31)

圖4 實驗結果對比

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

3.3 重疊社區檢測實驗

對于算法重疊社區檢測性能驗證，本文選取NMI指標進行實驗評估。對于兩個社區A和B的NMI指標可定義為

(32)

其中，Cij是重疊社區頂點，N是頂點數，CA和CB是社區數，C是混淆矩陣。實驗對象仍然選取Dolphins海豚網絡和Football足球網絡進行實驗對比，這兩種網絡中存在一定重疊社區。對比算法選取文獻[14,15]。結果如圖5所示。

圖5 NMI實驗對比結果

通過圖5實驗結果可知，隨著社區數量增加，3種對比算法均表現出一定的下降趨勢，表明網絡在多社區情況下對于重疊社區的識別效果降低，這與重疊社區情況惡化有一定關系。從3種算法對比看，本文算法對于重疊社區的惡化具有相對較強的抵抗能力，表明算法具有相對更理想的性能。

4 結束語

本研究提出了一種基于張量的高階節點連通性捕獲方法。構造的Egonet張量中的誘導冗余賦予了新的具有豐富結構的表示方法，并將該問題作為約束張量分解任務，用于群體檢測。張量稀疏和并行計算的應用使該算法具有可擴展性，而結構化冗余增強了對重疊和高度混合的群體的性能。該框架被擴展以適應時變圖，其中四維張量能夠在整個范圍內同時進行社區識別，從而提高了社區檢測算法性能。

這種方法強調了靈活性和冗余之間的權衡，因為相應CPD的內存和計算強度以及參數的適當調整將影響檢測社區的質量。下一步工作中，可以分析這種權衡，進一步描述隨著擴展覆蓋范圍的增加，被檢測社區的質量是如何演變的，這超出了本文研究范圍，將在后續工作中進行擴展。