约束张量规范多元分解时变社区图模型检测

赵 莉，李宗明

(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的内存和计算强度以及参数的适当调整将影响检测社区的质量。下一步工作中，可以分析这种权衡，进一步描述随着扩展覆盖范围的增加，被检测社区的质量是如何演变的，这超出了本文研究范围，将在后续工作中进行扩展。