0 概述

通过将每个实体视为一个顶点网络, 每条边看作一对顶点之间的相互作用, 可实现社区网络图模型的构建。现实中存在各种各样的网络, 如社交网络、互联网络和生物网络等。研究结果表明, 许多网络具有社群(模块)结构, 该结构被定义为子图, 该子图具有更多的边连接同一组中的顶点, 而相对较少的边连接不同组中的顶点。例如, 蛋白质相互作用网络中的社区对应于生物过程至关重要的蛋白质复合物^[1-2]。在科学合作网络中, 社区对应于具有相同或相似研究方向的科学家群体^[3]。

社区检测为分析社交网络系统的结构和功能提供了有效的分析方法, 但设计有效且高效的社区检测算法仍具有挑战性, 主要原因是没有统一的标准量化网络中的社区^[4]。当前针对社区检测已提出许多方法, 例如:文献[5]设计了采用模块度指标评价的动态社区发现算法, 其本质上是一种贪婪社区检测算法, 缺点是指标并未对模块密度问题进行综合分析, 具有一定的片面性; 文献[6]设计了采用Girvan策略的动态社区检测算法, 其基于层次聚类进行社区检测计算, 但是层次聚类算法的计算复杂度过高, 同时中心层次的构建存在先天缺陷; 文献[7]研究设计了基于图模型的动态社区检测算法, 图模型采用的是有向权重模型构建算法, 可实现对信息流的有效压缩, 获得更加优异的社区发现效果; 文献[8]设计了基于信息传播方法的动态社区检测算法, 算法对于社区检测过程的指标属性考虑不够充分, 社区划分精度不高。以上算法对于复杂社区检测过程中的边缘密度具有一定要求, 并且未对社区间的交互力问题进行有效分析。

为实现复杂网络的快速分析, 较为理想的社区检测方式是对计算效率和精度进行同步考虑。因此, 本文提出基于聚类质量(Clustering Quality, CQ)的改进非负矩阵分解(Improved Non-Negative Matrix Factorization, INMF)算法, 并将其用于动态社区检测。

1 问题描述 1.1 符号定义

定义1(动态网络)   令{1, 2, …, T}表示一组有限的时间步长。对于给定的变量, 附加的下标t表示时间t上变量的值。动态网络G被定义为网络的一个序列G={G₁, G₂, …, G_T}, 其中G_t是时间t上的网络, 具有顶点集V_t和边缘集E_t。假设G中的所有网络都具有相同的顶点集, 即G_t=(V_t, E_t)等效为G_t=(V, E_t)。

定义2(三维邻接矩阵)   动态网络G可以用三维邻接矩阵表示A=(a_ijt)_n×n×T, 其中n是顶点的个数(即n=|V|), 如果网络G_t中第i个顶点与第j个顶点连接, 则a_ijt=1;否则a_ijt=0。实际上, A=[A₁, A₂, …, A_T]是网络G_t的邻接矩阵, A_t=(a_ijt)_n×n。如果G_t是无向网络, 则邻接矩阵A_t是对称的。

定义3  (度矩阵)假设所有的网络是无向和未加权的。网络G_t中的第i个顶点的度数定义为连接到它的边数, 即d_it=$\sum\limits_j$a_ijt。动态网络G的度矩阵定义为D=[D₁, D₂, …, D_T], 其中D_t是具有G_t度序列的对角矩阵, 即D_t=diag(d_1t, d_2t, …, d_nt)。

网络中的社区检测是将顶点划分成不连续的组, 其中同一簇中的边缘数量大于组中的边缘数量。具体而言, 对于给定网络G_t=(V, E_t), 社区结构对应于硬划分{C_1t, C_2t, …, C_kt}(表示为{C_it}_i=1^k), 如果i≠j且V=$\sum\limits_i$iC_it, 则使得C_it∩C_jt=∅。C_it是时间t的第i个本地社区(集群)。{C_it}_i=1^k可利用n×k归一化指示符矩阵Z_t=(z_ijt)_n×k进行表示, 其中如果在时间t上, 第i个顶点属于第j个局部簇, 则z_ijt=1, 否则z_ijt=0。为简化, 利用局部簇的大小参数对矩阵Z_t列进行归一化处理, 即$\tilde {z}_{.jt}=z_{.jt}/ \sqrt {(C_{jt})} $, 其中$\tilde {z}$_.jt是Z_t的第j列, $\mathit{\boldsymbol{\tilde {Z}}}_t$=[$\tilde {z}_{.1t}$, $\tilde {z}_{.2t}$, …, $\tilde {z}_{.kt}$], $\mathit{\boldsymbol{\tilde {Z}}}_t$是列正交的, 容易验证$\mathit{\boldsymbol{\tilde {Z}}}′_t$$\mathit{\boldsymbol{\tilde {Z}}}_t$=I_k, 其中, I_k是单位矩阵, $\mathit{\boldsymbol{\tilde {Z}}}′_t$是矩阵$\mathit{\boldsymbol{\tilde {Z}}}_t$的转置。

1.2 社区定量评价函数

给定网络G_t=(V_t, E_t)以及硬划分{C_it}_i=1^k, 定义L(C_it, C_jt)=$\sum\limits_{i∈C_{it}, j∈C_{jt}}$a_ijt和C_it=V\C_it。模块化指标Q可定义为^[9]:

$ Q\left( {\left\{ {{C_{it}}} \right\}_{i = 1}^k} \right) = \sum\limits_{i = 1}^k {\frac{{L\left( {{C_{it}},{C_{it}}} \right)}}{{L(V,V)}}} - {\left( {\frac{{L\left( {{C_{it}},V} \right)}}{{L(V,V)}}} \right)^2} $

(1)

模块密度指标Q_D可定义为:

$ {Q_{\rm{D}}}\left( {\left\{ {{C_{it}}} \right\}_{i = 1}^k} \right) = \sum\limits_{i = 1}^k {\frac{{L\left( {{C_{it}},{C_{it}}} \right) - L\left( {{C_{it}},{{\bar C}_{it}}} \right)}}{{\left| {{C_{it}}} \right|}}} $

(2)

负相关性指标可定义为:

$ NA = {\rm Tr}\left( {{\mathit{\boldsymbol{A}}_t}} \right) - \sum\limits_{i = 1}^k {\frac{{L\left( {{C_{it}},{C_{it}}} \right)}}{{\left| {{C_{it}}} \right|}}} $

(3)

其中, Tr(A_t)是矩阵A_t的迹, 即$\sum\limits^n_{i=1}$a_ijt。文献[10]提出的模块化指标是目前常用的一种衡量网络中社区稳定度的方法; 模块密度指标主要评价社区中社区间的距离程度, 对网络社区的稀疏性进行表征; 负相关性指标评价的主要是社区之间的相关性。

2 基于CQ的聚类算法等价性描述 2.1 基于CQ的聚类算法分析

基于聚类时间(Clustering Time, CT)的定义, 可利用聚类质量指标对聚类算法的等价性进行定义。利用前一时间步长网络以及当前网络聚类结果的一致性进行定义, 图 1表示了在t-1和t时刻网络间的节点连接及节点间的权重(暂不考虑虚线部分)。由于聚类只考虑将同类的节点归类, 因此图中虚线清晰地将t-1和t时刻的聚类结果进行表示, 而没有考虑节点间的权重。

在该算法中, 前一时间步的局部社区用于指导当前时间步的社区发现, 并证明进化非负矩阵分解、演化谱聚类和模块密度在该过程中的等价性。虽然它们看似无关, 但在轨迹优化方面是等价的, 其关键问题是如何将目标函数转化为轨迹优化。在CQ算法框架中, CT表示当前划分对历史数据的聚类程度。网络G_t的划分Z_t^[1]和Z_t^[2]是等价的, 即CS₁=CS₂。

2.2 演化谱聚类

在CQ框架下, 使用负相关性的演化谱聚类的总成本可定义为:

$ \begin{array}{l} \mathit{Cos}{\mathit{t}_{NA}} = \alpha C{S_{NA}} + (1 - \alpha )C{T_{NA}} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;{\left. {\alpha N{\mathit{\boldsymbol{A}}_t}} \right|_{{\mathit{\boldsymbol{Z}}_t}}} + {\left. {(1 - \alpha )N{\mathit{\boldsymbol{A}}_{t - 1}}} \right|_{{\mathit{\boldsymbol{Z}}_t}}} \end{array} $

(4)

其中, |_Zt表示基于社区划分Z_t的谱聚类社区优化评价, 时间成本CT_NA=NA_t－1|_Zt表示对不属于网络G_t－1的Z_t的惩罚。将式(4)转化为轨迹优化问题:

$ \begin{array}{l} \mathit{Cos}{\mathit{t}_{NA}} = Tr \left[ {\alpha {\mathit{\boldsymbol{A}}_t} + (1 - \alpha ){\mathit{\boldsymbol{A}}_{t - 1}}} \right] - \\ \;\;\;\;\;\;\;\;\;\;\;\;Tr \left[ {{{\mathit{\boldsymbol{\tilde Z'}}}_t}\left( {\alpha {\mathit{\boldsymbol{A}}_t} + (1 - \alpha ){\mathit{\boldsymbol{A}}_{t - 1}}} \right){{\mathit{\boldsymbol{\tilde Z}}}_t}} \right] \end{array} $

(5)

其中, 第一项Tr[αA_t+(1－α)A_t－1]为常数, 因为它独立于局部分区$\mathit{\boldsymbol{\tilde {Z}}}_t$。因此, 最小化Cost_NA等同于最大化最后一项, 即:

$ \min \mathit{Cos}{\mathit{t}_{NA}} \propto {\mathop{\rm max \;Tr}\nolimits} \left[ {{{\mathit{\boldsymbol{\tilde Z'}}}_t}\left( {\alpha {\mathit{\boldsymbol{A}}_t} + (1 - \alpha ){\mathit{\boldsymbol{A}}_{t - 1}}} \right){{\mathit{\boldsymbol{\tilde Z}}}_t}} \right] $

(6)

2.3 模块密度优化

通过优化模块密度Q_D可优化聚类的总成本, 定义成本函数:

$ \begin{array}{l} \mathit{Cos}{\mathit{t}_{{Q_{\rm{D}}}}} = \alpha C{S_{{Q_{\rm{D}}}}} + (1 - \alpha )C{T_{{Q_{\rm{D}}}}} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\alpha \left( {{{\left. {{Q_{\rm{D}}}} \right|}_{{\mathit{\boldsymbol{Z}}_t}}} + (1 - \alpha )\left( {{{\left. {{Q_{\rm{D}}}} \right|}_{{\mathit{\boldsymbol{Z}}_{\rm{t}}}}}} \right.} \right. \end{array} $

(7)

为导出Cost_QD的轨迹优化, 需先导出(Q_D)_t|_Zt的轨迹优化问题:

$ \begin{array}{l} {\left. {{{\left( {{Q_{\rm{D}}}} \right)}_t}} \right|_{{\mathit{\boldsymbol{Z}}_t}}} = \sum\limits_{i = 1}^k {\frac{{L\left( {{C_{it}},{C_{it}}} \right) - L\left( {{C_{it}},{{\bar C}_{it}}} \right)}}{{\left| {{C_{it}}} \right|}}} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm Tr} \left[ {{{\mathit{\boldsymbol{\tilde Z'}}}_t}\left( {2{\mathit{\boldsymbol{A}}_t} - {\mathit{\boldsymbol{D}}_t}} \right){{\mathit{\boldsymbol{\tilde Z}}}_t}} \right] \end{array} $

(8)

将式(8)代入式(7), 可使Cost_QD的整体成本优化问题转换为轨迹优化问题:

$ \begin{array}{l} \mathit{Cos}{\mathit{t}_{{Q_{\rm{D}}}}} = {\rm Tr} \left[ {{{\mathit{\boldsymbol{\tilde Z'}}}_t}\left( {\alpha \left( {2{\mathit{\boldsymbol{A}}_t} - {\mathit{\boldsymbol{D}}_t}} \right) + } \right.} \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\left. {\left. {(1 - \alpha )\left( {2{\mathit{\boldsymbol{A}}_{t - 1}} - {\mathit{\boldsymbol{D}}_{t - 1}}} \right)} \right){{\mathit{\boldsymbol{\tilde Z}}}_t}} \right] \end{array} $

(9)

对比式(6)和式(9), 除了使用的矩阵不同外, 它们具有相同的优化形式, 表明模块密度优化Q_D与演化谱聚类是等价的, 即:

$ \max \mathit{Cos}{\mathit{t}_{{Q_{\rm{D}}}}} \propto \min \mathit{Cos}{\mathit{t}_{\mathit{NA}}} $

(10)

该结果从理论上解释了为何拓扑结构可用于动态社区检测。

2.4 非负矩阵分解

矩阵分解是进行图中挖掘的有效模式, 旨在通过将目标矩阵近似为两个低秩矩阵的乘积来学习原始数据的表示。具体地, 对于给定n×m矩阵F, 非负矩阵分解将F分解为2个非负矩阵R_n×s和S_s×m, 使得^[11]:

$ \mathit{\boldsymbol{F}} \approx \mathit{\boldsymbol{RS}},{\rm{s}}{\rm{. t}}{\rm{. }}\mathit{\boldsymbol{R}} \ge 0,\mathit{\boldsymbol{S}} \ge 0 $

(11)

在通常情况下, s比min{n, m}小得多; 对称非负矩阵分解(Symmetric Non-Negative Matrix Factorization, SNMF)是非负矩阵分解的一个扩展, 它将矩阵F近似分解成n×s矩阵R, 使得:

$ \mathit{\boldsymbol{F}} \approx \mathit{\boldsymbol{RR'}},{\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{.}}\;\mathit{\boldsymbol{R}} \ge 0 $

(12)

给定网络G_t的邻接矩阵, 利用SNMF可以得到局部簇$\mathit{\boldsymbol{\tilde {Z}}}_t$:

$ {\mathit{\boldsymbol{A}}_t} \approx {\mathit{\boldsymbol{\tilde Z}}_t}{\mathit{\boldsymbol{\tilde Z'}}_t} $

(13)

通过最小化平方误差来求解上述方程, 即:

$ SNM{F_t} = \mathop {\min }\limits_{{{\mathit{\boldsymbol{\tilde Z}}}_t} \ge 0,{{\mathit{\boldsymbol{\tilde Z'}}}_t}{{\mathit{\boldsymbol{\tilde Z}}}_t} = {\mathit{\boldsymbol{I}}_k}} {\left\| {{\mathit{\boldsymbol{A}}_t} - {{\mathit{\boldsymbol{\tilde Z'}}}_t}{{\mathit{\boldsymbol{\tilde Z}}}_t}} \right\|^2} $

(14)

其中, ‖B‖是矩阵B的Frobeneus范数。将等式(14)改写为轨迹优化, 即:

$ SNM{F_t} = \mathop {\max }\limits_{{{\mathit{\boldsymbol{\tilde Z}}}_t} \ge 0,{{\mathit{\boldsymbol{\tilde Z'}}}_t}{{\mathit{\boldsymbol{\tilde Z}}}_t} = {\mathit{\boldsymbol{I}}_k}} {\rm Tr}\left( {{{\mathit{\boldsymbol{\tilde Z'}}}_t}{\mathit{\boldsymbol{A}}_t}{{\mathit{\boldsymbol{\tilde Z}}}_t}} \right) $

(15)

利用松弛正交性$\mathit{\boldsymbol{\tilde {Z}}}′_t$$\mathit{\boldsymbol{\tilde {Z}}}_t$=I_k, 式(15)可改写为下列形式:

$ SNM{F_t} \propto \mathop {\max }\limits_{{{\mathit{\boldsymbol{\tilde Z}}}_t} \ge 0} \;{\rm Tr} \left( {{{\mathit{\boldsymbol{\tilde Z'}}}_t}{\mathit{\boldsymbol{A}}_t}{{\mathit{\boldsymbol{\tilde Z}}}_t}} \right) $

(16)

结合式(4)可定义非负矩阵分解的整体成本函数形式为:

$ \begin{array}{l} \mathit{Cos}{\mathit{t}_{{\rm{INMF}}}} = \alpha C{S_{{\rm{SNMF}}}} + (1 - \alpha )C{T_{{\rm{SNMF}}}} = {\left. {\alpha SNM{F_t}} \right|_{{\mathit{\boldsymbol{Z}}_t}}} + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\left. {(1 - \alpha )SNM{F_{t - 1}}} \right|_{{\mathit{\boldsymbol{Z}}_t}}} \end{array} $

(17)

基于式(16), 将式(7)重新表述为:

$ \begin{array}{l} \mathit{Cos}{\mathit{t}_{INMF}} \propto \alpha Tr\left( {{{\mathit{\boldsymbol{\tilde Z'}}}_t}{\mathit{\boldsymbol{A}}_t}{{\mathit{\boldsymbol{\tilde Z}}}_t}} \right) + \left( {1 - \alpha } \right) Tr \left( {{{\mathit{\boldsymbol{\tilde Z'}}}_t}{\mathit{\boldsymbol{A}}_{t - 1}}{{\mathit{\boldsymbol{\tilde Z}}}_t}} \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;Tr\left[ {{{\mathit{\boldsymbol{\tilde Z'}}}_t}\left( {\alpha {\mathit{\boldsymbol{A}}_t} + (1 - \alpha ){\mathit{\boldsymbol{A}}_{t - 1}}} \right){{\mathit{\boldsymbol{\tilde Z}}}_t}} \right] \end{array} $

(18)

对比式(6)、式(9)及式(18)可得出, SNMF、演化谱聚类和模块密度优化是等价的, 即:

$ \left\{ {\begin{array}{*{20}{l}} {\min \mathit{Cos}{\mathit{t}_{{\rm{NMF}}}} \propto \min \mathit{Cos}{\mathit{t}_{NA}}}\\ {\min \mathit{Cos}{\mathit{t}_{{\rm{INMF}}}} \propto \max \mathit{Cos}{\mathit{t}_{{Q_{\rm{D}}}}}} \end{array}} \right. $

(19)

由此证明SNMF和演化谱聚类之间的等价性, 表明SNMF算法也可以用于动态社区检测。

3 半监督INMF算法 3.1 半监督局部社区聚类发现

为基于时间平滑框架在时刻t发现局部簇, 通过线性函数同时考虑G_t和G_t－1, 定义该线性函数为^[12]:

$ \mathit{\boldsymbol{A}}_t^ * = \alpha {\mathit{\boldsymbol{A}}_t} + (1 - a)\left( {{\mathit{\boldsymbol{A}}_t} - {\mathit{\boldsymbol{A}}_{t - 1}}} \right) $

(20)

其中, 参数α控制CS和CT的相关重要性。基本的假设是:如果一组顶点的连通性在G_t和G_t－1中都很强, 那么它们很可能在时刻t是本地集群。通常选取参数α=0.8。许多研究成果表明^[5-6], 在聚类算法中加入先验信息可显著提高算法精度, 如Pagerank算法、半监督NMF算法和半监督谱聚类算法。本文提出结合非负矩阵算法和谱聚类算法的半监督改进非负矩阵分解算法。采用谱聚类的原因为:1)谱聚类通常可获得良好的聚类性能; 2)演化谱聚类和非负矩阵分解算法之间的等价性为它们组合奠定了坚实的理论基础。

构建先验信息的策略包括两个步骤:1)获得高质量的顶点群; 2)部分信息的构建。首先使用由指示符矩阵Z_t^sc表示谱聚类算法来获得时刻t的局部聚类, 其中如果第i个顶点属于第j个局部社区, 则Z_ijt^sc=1;否则Z_ijt^sc=0。为确保先验信息的质量, 对于每个局部社区, 需移除社区内的顶点, 直到社区的诱导子网络的密度达到阈值β。基本假设是强连通顶点很可能被分组为一个社区。由于在随机网络中普遍存在小的密集子图, 因此保留了至少5个顶点的子图作为先验信息, 细化的局部社区由Z_t^rc表示。将先验信息结合到A_t^*中:

$ \mathit{\boldsymbol{\hat A}}_t^ * = \mathit{\boldsymbol{A}}_t^ * + \gamma \mathit{\boldsymbol{Z}}_t^{{\rm{rc}}}{\left( {\mathit{\boldsymbol{Z}}_t^{{\rm{rc}}}} \right)^\prime } $

(21)

其中, γ是控制先验信息的相关权重参数。为获得时间t上的局部簇, 本文所提算法通过最小化平方误差对矩阵$\mathit{\boldsymbol{\hat A}}$_t^*进行分解, 即:

$ {\mathit{\boldsymbol{J}}_t} = {\left\| {\mathit{\boldsymbol{A}}_t^* - {\mathit{\boldsymbol{B}}_t}{\mathit{\boldsymbol{F}}_t}} \right\|^2},{\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{.}}\;{\mathit{\boldsymbol{B}}_t} \ge 0,{\mathit{\boldsymbol{F}}_t} \ge 0 $

(22)

为求解上述方程, 将J_t的导数设为:

$ \frac{{\partial {\mathit{\boldsymbol{J}}_t}}}{{\partial {\mathit{\boldsymbol{B}}_t}}} = 0,\frac{{\partial {\mathit{\boldsymbol{J}}_t}}}{{\partial {\mathit{\boldsymbol{F}}_t}}} = 0 $

(23)

得到以下更新规则:

$ {\mathit{\boldsymbol{B}}_t} = {\mathit{\boldsymbol{B}}_t}\frac{{\mathit{\boldsymbol{\hat A}}_t^*\mathit{\boldsymbol{F}}_t^\prime }}{{{\mathit{\boldsymbol{B}}_t}{\mathit{\boldsymbol{F}}_t}\mathit{\boldsymbol{F}}_t^\prime }} $

(24)

$ {\mathit{\boldsymbol{F}}_t} = {\mathit{\boldsymbol{F}}_t}\frac{{{{\mathit{\boldsymbol{B'}}}_t}\mathit{\boldsymbol{\hat A}}_t^*}}{{{{\mathit{\boldsymbol{B'}}}_t}{\mathit{\boldsymbol{B}}_t}{\mathit{\boldsymbol{F}}_t}}} $

(25)

基于矩阵F_t构造G_t局部簇的指示矩阵Z_t, 即如果j^*=$\mathop {\arg \max }\limits_j $F_ij, 则可得Z_ij^*t=1;否则Z_ij^*t=0。该过程如图 2所示。

3.2 动态社区发现

给定时间步长t－1和t的局部簇, 通过局部簇映射来发现动态社团。令C_t为时间t时的局部簇集合, C_it是C_t的第i个局部集群。构造C_t和C_t－1之间的二分图, 其中每个局部聚类被视为顶点, C_{i, t－1}和C_jt之间的链接权重被定义为重叠顶点的数目, 即:

$ {l_{ijt}} = \left| {{C_{i,t - 1}} \cap {C_{jt}}} \right| $

(26)

潜在的假设是:若更多的顶点重叠, 则更可能多的局部集群将被映射。类似地, 构造从C₁到C_T的T划分图如图 3所示。

利用互信息定义T图的拓扑相似度^[13-14]:

$ \mathit{MI}\left( {{C_{i,t - 1}},{C_{jt}}} \right) = \frac{{{l_{ijt}}}}{{\sum\limits_j {{l_{ijt}}} }}\lg \frac{{{l_{ijt}}\sum\limits_{i,j} {{l_{ijt}}} }}{{\sum\limits_i {{l_{ijt}}} \sum\limits_j {{l_{ijt}}} }} $

(27)

假设局部簇之间的互信息越高, 两个局部簇就越有可能相关。贪婪搜索程序用于从C_t－1到C_t的局部映射集群:对于每一次迭代, 选择具有最大MI值的局部簇对; 一旦C_{i, t－1}和C_jt之间的映射完成, C_t－1内的其他局部簇就不能映射到C_jt; 此过程继续, 直到没有可用的映射。动态社区是这些映射的局部集群。半监督非负矩阵分解算法具体步骤如下:

算法1  半监督非负矩阵分解算法

输入  动态网络G、局部聚类数量{k_i}_i=1^T、局部簇密度阈值β、先验信息权重γ

输出   局部集群与演化社区{Z_t}_t=1^T

//局部社区发现

1.对于每个时间步长t, 根据式(26)构造A_t^*;

2.利用谱聚类算法获取局部信息Z_t^rc;

3.根据式(27)构造划分矩阵A_t^*;

4.根据式(28)、式(29), 利用NMF获得局部聚类发现{Z_t}_t=1^T;

//改进社区发现

5.利用局部聚类{Z_t}_t=1^T, 构造T划分图;

6.利用贪心搜索算法发现改进社区;

7.返回查询结果

3.3 参数选择

本文算法包含3个参数:k_t, β和γ, 其中, k_t是网络G_t中的局部簇数量, β是先验信息的密度阈值, γ是控制先验信息的重要性占比。

在聚类中确定簇数目的方法有很多, 例如:在谱聚类算法中, 使用两个连续特征值之间的间隙来选择适当的k_t参数, 当网络规模较小时, 容易获得较大的间隙, 当网络规模较大时, 由于难以定义阈值, 因此难以找到间隙; 目标函数引导策略也是常用方法, 其中k_t是与给定目标函数(例如模块化Q)的最大(最小)值相对应的值。本文在矩阵谱理论的基础上选择k_t取值。给定网络G_t, 邻接矩阵A_t的谱是特征值λ_1t, λ_2t, …, λ_nt以及相应的特征向量x_1t, x_2t, …, x_nt的集合。

不失一般性, 假设λ_1t≥λ_2t≥…≥λ_nt。矩阵可以在特征值和特征向量的基础上重建, 即:

$ {\mathit{\boldsymbol{A}}_t} = \sum\limits_{i = 1}^n {{\lambda _{it}}} {x_{it}}x_{it}^\prime $

(28)

选择k_t作为最小值k, 可得:

$ {k_t} = \mathop {\arg \min }\limits_k \sqrt {\left\| {\sum\limits_{i = 1}^k {{\lambda _{it}}} {x_{it}}x_{it}^\prime } \right\|/\left\| {{\mathit{\boldsymbol{A}}_t}} \right\|} > \delta $

(29)

其中, δ是控制近似值的参数。一方面, 随着特征向量个数的增加, A_t和局部解之间的误差(即‖A_t－$\sum\limits^k_{i=1}$λ_itx_itx′_it‖²)减小。另一方面, 随着特征值个数的增加, 特征是冗余的。因此, 对δ来说, 用相当少的特征值来实现合理、近似的值, 可使结果趋向于良好的方向。设置δ、γ和β作为调谐参数, 并根据经验进行选取。

3.4 计算复杂度分析

对本文算法的空间复杂度进行分析, 在给定动态网络G的情况下, 三维邻接矩阵A_n×n×T需要的空间复杂度为O(n²T)。在给定邻接矩阵的情况下, 指标矩阵的空间复杂度为O(nk_t)。分解矩阵A所需的总计算复杂度为:

$ \begin{array}{*{20}{r}} {O\left( {{n^2}T} \right)O\left( {n\left( {{k_1} + {k_2} + \cdots + {k_n}} \right)} \right) = }\\ {O\left( {nT\max \left\{ {{k_1},{k_2}, \cdots ,{k_n}} \right\}} \right)} \end{array} $

(30)

因为k_i≤n(1≤i≤T), 所以式(30)的计算复杂度为O(n²T)。在社区映射过程中, T划分图的空间复杂度是O(T(max_i, k_i)²)。因此, 总的空间复杂度为O(n²T), 从而证明本文算法在空间复杂度上的计算是有效的。

然后, 对时间复杂度进行分析。对于每个时间t, 本文算法包含3个主要组成部分:采用谱聚类算法的先验信息构造、局部聚类矩阵分解以及模块映射过程。谱聚类的时间复杂度为O(n³)。在时间t上, 局部簇的非负矩阵分解的时间复杂度为O(rn²k_t), 其中r是迭代次数。局部聚类映射过程的时间复杂度为O(k_t－1k_t)。因为k_i < n, 所以每个时间步长的时间复杂度为:

$ O\left( {{n^3} + r{n^2}{k_t} + {k_{t - 1}}{k_t}} \right) = O\left( {{n^3} + r{n^2}{k_t}} \right) $

(31)

本文算法的整体时间复杂度为O(T(n³+rn²max{k_t}_t=1^T)), 分析结果显示, 本文算法的时间复杂度与INMF相当。

4 实验结果与分析 4.1 实验环境设置

在实验中, 选取的实验模型分为两组:1)具有静态属性的社区发现模型; 2)具有动态属性的社区发现模型。实验平台的硬件情况:CPU-i5-6200k, 内存大小为16 GB ddr4-2400, 系统为Win7旗舰版。

实验模型的具体选取情况如下:1)具有静态属性的社区发现模型, 主要有微博网络(Polblogs)、海豚网络(Dolphins)、新陈代谢网络(Cel)、爵士乐网络(Jazz)、邮箱网络(Email)、足球社网络(Football)、空手道网络(Karate); 2)具有动态属性的社区发现模型, 主要有arXive-print网络和Enron Email网络。

选取的对比实验算法为CNM算法、GN算法、LPA算法、Spin-glass算法、Similarity算法、NEC算法、QCA算法(以上算法相关定义见文献[15])及MIEN算法^[16]。实验包含3个主要过程:静态社区发现模型有效性验证, 静态社区发现模型可视化验证, 动态社区发现模型性能验证。

4.2 静态社区发现模型有效性验证

为验证不同算法的社区划分性能, 在此选取模块度以及社区划分数量作为实验对比指标, 选取的对比实验算法在上述具有静态属性的社区发现模型上的性能测试结果如表 1所示。

在表 1实验对比数据中, 除了本文算法是通过本文实验结果获得外, 其他对比算法均来自于文献[15]。根据表 1实验结果可知, Spin-glass算法和本文考虑聚类质量的半监督INMF动态社区检测算法在所选取的静态社区发现模型上, 均可获得较为理想的社区发现结果。从模块度指标的评估结果看, Spin-glass算法的指标分布区间是0.41~0.62, 本文算法的社区发现结果的指标分布区间是0.42~0.64。CNM算法、GN算法、LPA算法、Similarity算法、NEC算法的指标分布区间均低于Spin-glass算法和本文算法。上述实验结果验证了本文算法在社区发现模块度指标上的性能优势。

4.3 静态社区发现模型可视化验证

在可视化实验验证阶段, 因为受到文章篇幅的限制, 仅选取静态属性的社区发现模型中的Karate、Dolphins和Jazz 3种社区发现模型进行可视化实验验证。同时, 选取这3种社区发现模型的另一个原因是其模型中的节点规模数量相对较少, 如果节点规模数量过大, 则不利于直观显示实验结果。可视化实验验证结果如图 4~图 6所示。

在上述实验模型中, Karate模型是针对俱乐部内部成员之间的社会关系构建的社区发现模型, 成员模型的数量是34, 也就是其节点是34个。如图 4所示的Karate模型中, 节点1是俱乐部中的教练角色, 其余节点是俱乐部中的经理角色, 相互之间存在冲突, 且具有不可调和性, 进而影响俱乐部内部成员之间的关系, 存在派系问题。在本文算法的可视化社区检测结果中, 共可得到Karate模型的2个派系4个社区检测结果, 该划分结果同原始模型构建过程中的真实情况完全吻合。Dolphins模型主要是为研究海豚群体而建立的社区分析模型, 该模型的原始对象由2个不同的海豚家族构成, 模型的构建节点数量是62。图 6为本文算法对Dolphins模型的社区划分结果, 可视化实验结果显示, 本文算法可将海豚群体划分为4个社区检测结果, 该划分结果同原始模型构建过程中的真实情况完全吻合。Jazz模型对象主要是为研究爵士乐队社会关系构建的社区发现模型, 本文算法的划分结果如图 5所示, 因为其中所涉及的节点数量过多, 这里并未对其节点的顺序号进行一一标注, 根据图 6的Jazz模型的社区发现结果可知, 本文算法可将Jazz模型划分成4个社区, 该划分结果同原始模型构建过程中的真实情况完全吻合。上述实验结果显示, 本文算法在选取的Karate、Dolphins和Jazz这3种静态社区检测模型上可获得非常精确的社区划分结果。

4.4 动态社区发现模型性能验证

本文算法主要考虑的是针对社区划分质量的动态社区发现问题, 为验证本文算法的有效性, 在此选取QCA算法^[15]、MIEN算法^[16]进行算法性能测试。动态社区划分实验对象选取Enron Email网络。实验过程中的硬件配置同上, 测试指标使用的是社区检测算法获得的社区数量、模块度指标以及计算时间3组评价结果。实验对比数据如图 7所示。

Enron Email模型主要是针对Enron公司中高管之间的邮件关系进行设计, 其考虑的高管节点数量是151。选取网络模型中一半的边建立实验模型, 此外构建21组具有静态属性的模型结构, 其中边缘的增加速度是1 000。根据实验对比结果, 本文算法相对于QCA动态社区发现算法和MIEN动态社区发现算法, 在社区数量、模块度指标以及计算时间3组评价指标上具有更加优异的性能表现。

综合上述实验结果可知, 本文算法相对于选取的对比实验算法在社区检测质量和社区检测效率上性能更优, 验证了本文算法在动态社区发现上的性能优势。

5 结束语

本文为推导改进聚类算法之间的理论关系, 证明了模块密度优化、演化谱聚类和INMF之间的等价性, 从而扩展演化谱聚类和局部聚类之间的等价性。结合INMF和谱聚类, 提出半监督INMF算法, 并将其引入到INMF目标函数中。在不增加时间复杂度的情况下, 通过使用人工构造和真实世界的动态网络, 证明了该算法的性能优势。但由于半监督INMF算法前一时间步社区中的错误会被传递到当前时间步的社区检测中, 从而影响算法准确性, 因此下一步将对此进行研究及改进。