New Community Detection and Evolution Analysis Method for Dynamic Networks

文献[10]提出了基于事件的动态网络演化分析框架，如图 1所示。其中，生成的时间轴用来刻画网络的变化情况；网段抽取是用平稳的或相对多变的趋势来近似时间轴上网络的变化；图近似是对网段抽取后的结果用网络图进行表示；社团检测是发现近似动态网络某时刻所对应静态网络中的社团；社团演化分析是将不同时刻所发现的社团关联起来，得到相应的演化事件。

生成时间轴、网段抽取和图近似属于对动态网络的近似和简化，与被研究动态网络的规模有直接关系。因此，本文以该框架为基础，以社团检测和社团演化分析为研究重点，提出了一种面向动态网络的社团检测与演化分析方法。

动态网络研究中涉及到很多与静态网络类似的概念与问题，本节首先对文中通用的概念与问题给出形式化的定义，符号说明如表 1所示。

定义  1^[4]  动态网络。动态网络$ G = \langle {g^{(1)}}, {g^{(2)}}, \cdots, {g^{(t)}}, \cdots \rangle $是时间上的有序图集，其中$ {{g}^{(t)}}=(V({{g}^{(t)}}),E({{g}^{(t)}})) $是t时刻拓扑图。

定义  2^[10]  社团。社团是网络中的一种子结构，在社团内部，点之间的联系比较紧密，相比之下，这些点和社团外部点的联系则比较稀疏。

采用基于事件的动态网络演化分析架构，本文提出了一种面向动态网络的社团检测与演化分析方法，该方法将动态网络的时序动态性和时刻静态性用时间序列的方式进行表示，在时刻上运行基于Memetic的静态社团检测算法，在时序上运行社团演化分析算法，最终可以得到社团的动态演变轨迹。

Memetic是一种结合遗传算法和局部搜索策略的新型智能算法，在优化问题上具有较高的搜索效率^[11-14]。本文以其为基础，设计了一种具有指向性的变异策略，将变邻域搜索算法作为局部搜索算子，提出了一种基于Memetic的静态社团检测算法。

1) 编码策略

对t时刻的网络快照g^(t)，采用字符串编码方式。假设该快照中包含5个节点$ \{ {v_1}, {v_2}, {v_3}, {v_4}, {v_5}\} $，若字符串编码的染色体为$ (1, 2, 2, 1, 3) $，则表示$ \{ {v_1}, {v_4}\} $属于社团1，$ \{ {v_2}, {v_3}\} $属于社团2，$ \{ {v_5}\} $属于社团3。

2) 具有指向性的变异策略

在Memetic算法中，变异概率通常是随机取值或给定特定的值，收敛速度较慢，因此本文提出了一种具有指向性的变异策略，即计算每个个体中不同社团之间的结构相似度$ {\rm{{\rm{Sim}}}}(C_i^{(t)}, C_j^{(t)}) $，i≠j，设置个体的变异概率$ {P_m} = \max {\rm{Sim}}(C_i^{(t)}, C_j^{(t)}) $，i≠j，其中$ {\rm{Sim}}(C_i^{(t)}, C_j^{(t)}) $的定义如下。

定义  3^[15]  结构相似度。对于t时刻的网络快照g^(t)，对于任意两个社团$ C_i^{(t)}, C_j^{(t)} \in C_{}^{(t)} $，结构相似度定义为：

采用具有指向性的变异策略可以尽量保留社团间结构相似度较小的个体，变异社团间结构相似度较大的个体，使变异朝社团内部点和外部点联系稀疏的方向进行，进而快速收敛到最优个体。

3) 适应度函数

本文适应度函数使用基于相似度的模块度函数，使得网络中社团内部节点对的相似度要高于分属于不同社团的节点对相似度，其定义如下。

定义  4^[15]  模块度。对于t时刻的网络快照g^(t)，若个体x所对应的社团集合为$ {C^{(t)}}\left| x \right. = $$ \{ C_1^{(t)}, C_2^{(t)}, \cdots, C_p^{(t)}\} $，则其模块度函数被定义为：

式中，$ \text{IS}_{i}^{(t)}=\sum\limits_{u,v\in C_{i}^{(t)}}{\text{Sim}(u,v)} $；$ {\rm{DS}}_i^{(t)} = $$ \sum\limits_{u \in C_i^{(t)}, v \in V({g^{(t)}})} {{\rm{Sim}}(u, v)} $；$ {{\rm{TS}}^{(t)}} = \sum\limits_{u, v \in V({g^{(t)}})} {{\rm{Sim}}(u, v)} $；从社团集合$ {C^{(t)}}\left| x \right. $到$ {C^{(t)}}\left| {x'} \right. $的模块度变化定义为$ \Delta {Q_{{C^{(t)}}\left| x \right. \to {C^{(t)}}\left| {x'} \right.}} = Q({C^{(t)}}\left| {x'} \right.) - Q({C^{(t)}}\left| x \right.) $，$ {\rm{Sim}}(u, v) $为节点之间的结构相似度，将节点视为一个社团，其计算方法同式(1)。

4) 变邻域搜索算法

变邻域搜索(variable neighborhood search, VNS)^[16-18]算法是一种求解优化问题的启发式算法。本文将该算法作为局部搜索算子引入到Memetic算法中，可以在社团划分过程中通过动态地改变邻域结构来拓展搜索范围，从而使搜索过程跳出局部最优向全局最优靠近。

邻域结构集N_l(x)(l=1, 2, …, l_max)的构造是VNS算法最核心的部分。本文设计了3种邻域结构，具体形式如下：

① 交换/N₁(x)

随机选择第i个个体的任意两节点v_m和$ {v_n}(m \ne n) $；交换v_m和v_n所属社团。

② 多点交换/N₂(x)

随机选择第i个个体的任意两节点v_m和$ {v_n}(m \ne n) $；交换v_m和v_n所属社团；重复以上两个步骤至少两次。

③ 复合交换/N₃(x)

随机选择第i个个体的任意两节点v_m和v_n$ (m \ne n) $；随机选择第i个个体中任意两个序列p和q，$ p \ne q \ne m \ne n $；将v_m所属社团置于p序列，将v_n所属社团置于q序列。

仿真实验发现，调用VNS算法时，按照先N₁(x)交换，再多点交换，最后复合交换的顺序(即l单调递增)，算法性能表现最好，因此本文仿真实验按此顺序使用这3种离散邻域结构。以下是VNS算法的详细步骤。

输入：初始个体x^*、l_max

输出：局部最优个体

  构造离散邻域结构集N_l(x)；

  for l=1: l_max do

    x←x^*；

    根据个体x所对应的社团集合$ {C^{(t)}}\left| x \right. $，计算

    模块度函数$ Q({C^{(t)}}\left| x \right.) $；

    在x的第l个邻域中随机搜索产生x'($ x' \in {N_l}(x) $)；

    令随机搜索产生的解x'作为初始解，通过局部搜索获得局部最优解x"；

    if $ Q({C^{(t)}}\left| {x''} \right.) > Q(\left. {{C^{(t)}}} \right|{x^*}) $ then

      $ x* $←$ x'' $;

    继续在当前邻域结构内搜索；

      else

        continue;

    end if

end for

5) 算法步骤

基于Memetic的静态网络社团检测算法的整体步骤如下所示。

输入：g^(t)、交叉概率、变异概率、最大迭代次数iter_max

输出：t时刻的社团结构

随机初始化M个个体；

for iter=1: iter_max do

  交叉算子采用均匀交叉，生成下一代种群；

  将VNS作为局部搜索算子，执行该算子；

  执行具有指向性的变异策略；

  再次按照上步执行局部搜索算子，对种群中的每一个个体进行局部搜索，更新所有个体；

  用适应度函数计算种群中所有个体的适应度；

  用锦标赛法作为选择算子，对种群进行更新；

  if $ \Delta {Q_{{C^{(t)}}\left| x \right. \to {C^{(t)}}\left| {x'} \right.}} < 0 $ then

    break;

    else

      继续进行迭代;

    end if

end for

基于本文所定义的匹配度和社团生存周期，提出了一种社团演化分析算法。该算法通过分析不同时刻社团集合的匹配度来发现社团演变事件，从而获得社团的动态演变轨迹。

1) 演变事件

演变事件用来刻画不同时刻的社团演变特征，常用演变事件的定义如下^[19-21]：

① 社团生长(community survives)：在t+1时刻存在一个社团使得$ C_j^{(t + 1)} = {\rm{match}}(C_i^{(t)}) $成立。

② 社团合并(community absorb)：在t+1时刻存在一个社团使得$ C_j^{(t + 1)} = {\rm{match}}(C_i^{(t)}) $和$ C_i^{(t)} \subseteq C_j^{(t + 1)} $同时成立。

③ 社团分裂(community split)：在t+1时刻存在p个社团使得$ \bigcup\limits_{k = 1}^p {C_k^{(t + 1)}} = {\rm{match}}(C_i^{(t)}) $成立。

④ 社团消失(community disappear)：在t时刻存在社团$ C_i^{(t)} $在$ {C^{(t + 1)}} $中找不到社团与之对应。

⑤ 社团出生(community appear)：在t+1时刻存在社团$ C_i^{(t + 1)} $在$ {C^{(t)}} $中找不到社团与之对应。

2) 匹配度及match函数

传统的社团演化分析主要有点重合度^[22]和结构相似^[23]两种方法，它们的不足在于只孤立地分析点或者边，忽略了社团的整体性，因此本文通过综合考虑节点和边的相似度，定义了匹配度，如定义5。

定义  5  匹配度。前后两个时刻的任意两个社团$ C_i^{(t)} $和$ C_j^{(t + 1)} $之间的匹配度定义为：

式中，

分别表示$ C_i^{(t)} $和$ C_j^{(t + 1)} $节点和边的相似度。

式(3)可使$ V{\rm{Sim}}(C_i^{(t)}, C_j^{(t + 1)}) $和$ E{\rm{Sim}}(C_i^{(t)}, C_j^{(t + 1)}) $两个值达到一个合理的均衡程度，令社团$ C_i^{(t)} $和$ C_j^{(t + 1)} $不仅节点相似，边也相似。

基于匹配度，本文设计了在演变事件定义中所用到的match函数，如下所示。其中匹配度阈值要根据实际动态网络的情况和用户的偏好进行设置。

输入：$ C_i^{(t)} $、$ {C^{(t + 1)}} $、τ

输出：$ {C^{(t + 1)}} $中与$ C_i^{(t)} $匹配的$ {C_j}^{(t + 1)} $

maxMat=0，c= $ {C_1}^{(t + 1)} $；

for each $ {C_j}^{(t + 1)} \in {C^{(t + 1)}} $ do

  currMat= $ {\rm{Mat}}(C_i^{(t)}, C_j^{(t + 1)}) $；

    if (currMat>maxMat) then

      maxMat=currMat;

      c= $ C_j^{(t + 1)} $;

  end if

end for

if (maxMat > τ)

  return c;

else

  return Φ;

end if

3) 社团演化分析算法

在所刻画的5种演变事件中，社团出生和分裂都表示有新的社团产生，社团消失表示有现存的社团瓦解，而社团生长和合并则表示现存社团的延续。因此为了描述动态网络的演变轨迹，本文定义了社团生存周期，如定义6。

定义  6  社团生存周期。假设社团$ C_i^{(t)} $在t时刻出现，其社团生存周期被定义为$ C_i^{(t)} $生长或合并的次数$ \left| {{\rm{lifetime}}(C_i^{(t)})} \right| $，其中：

表示社团$ C_i^{(t)} $生长或合并的社团序列集合。

根据上述的定义和分析，本文所提出的社团演化分析算法如下所示。

输入：动态网络$ G = \langle {g^{(1)}}, {g^{(2)}}, \cdots, {g^{(3)}}, \cdots \rangle $，τ

输出：$ {\rm{lifetime}}(C_i^{(t)}) $

初始化  $ {\rm{lifetime}}(C_i^{(t)}) = \left\{ {C_{i1}^{(1)}\left| {C_{i1}^{(1)} \in {C^{(1)}}} \right.} \right\} $，$ i = 1, 2, \cdots, |{C^{(1)}}| $；

for t > 1 do

  从$ {g^{(t)}} $抽取社团集合$ {C^{(t)}} $；

  for $ C_{ij}^{(t -1)} \in {\rm{lifetime}}(C_i^{(t -1)}){\rm{s}}{\rm{.t}}{\rm{.}}j = \left| {{\rm{lifetime}}(C_i^{(t - 1)})} \right| $ do

  if $ ((C_{ik}^{(t)} = {\rm{survives}}(C_{ij}^{(t - 1)}, {C^{(t - 1)}}, {C^{(t)}}, \tau )) \ne \phi \vee $ $ (C_{ik}^{(t)} = {\rm{absorbed}}(C_{ij}^{(t - 1)}, {C^{(t - 1)}}, {C^{(t)}}, \tau )) \ne \phi ) $

  then

    $ {\rm{lifetime}}(C_i^{(t - 1)}) = {\rm{lifetime}}(C_i^{(t - 1)}) \cup \{ C_{ik}^{(t)}\} $；

  else if $ ((S = {\rm{split}}(C_{ij}^{(t - 1)}, {C^{(t - 1)}}, {C^{(t)}}, \tau )) \ne \phi ) $ then

    for $ C_{ik}^{(t)} \in S $ do

    $ {\rm{lifetime}}(C_i^{(t - 1)}) = {\rm{lifetime}}(C_i^{(t - 1)}) \cup \{ C_{ik}^{(t)}\} $；

    end for

else

    $ C_{ij}^{(t - 1)} $消失，$ {\rm{lifetime}}(C_i^{(t - 1)}) $不再延伸；

end if

end for

for $ C_{ij}^{(t - 1)} \notin {\rm{lifetime}}(C_i^{(t - 1)}) $ do

    $ C_i^{\left( t \right)} $是新生社团，创建$ {\rm{lifetime}}(C_i^{(t)}) = $$ \{ C_{i1}^{(t)}\} $；

end for

end for

本文使用真实网络数据集进行实验，以验证算法的可行性与有效性。

数据集1：Zachary空手道俱乐部网络^[5]

Zachary空手道俱乐部网络是根据1970年~1972年美国一所大学空手道俱乐部34名成员之间的社会关系所构造的。节点表示成员，节点间的连接代表两个成员经常一起出现在俱乐部活动之外的其他场合。文中通过每隔一个月构建一个静态网络(即一个网络快照)的方式，建立起了Zachary空手道俱乐部在1970年~1972年的动态社会关系网络。在动态网络的建立期间，俱乐部主管John A.(节点34)与教练Mr. Hi(节点1)之间的争执而分裂成了2个各自为核心的小俱乐部，最后一次所构建的静态网络中共包含34个节点，78条边。

数据集2：Power网络

Power网络是根据1998年美国西部的高压电线路构建的。网络中的节点代表变压器、变电站和发电机，边表示的高压电传送线路。与数据集1采用相同的思路，文中通过每隔一个月构建一个静态网络(即一个网络快照)的方式，建立起了美国西部高压电线路在1998年的动态网络，最后一次所构建的静态网络中共包含4 941个节点和6 594条边。

本文所提出的动态网络社团检测与演化分析方法由基于Memetic的静态社团检测算法和社团演化分析算法两部分组成，本节就这两个算法的性能分别进行分析。

1) 可行性分析

采用本文所提出的基于Memetic的静态网络社团检测算法，设置种群中个体数目M=30，交叉概率P_c=0.6，变异概率P_m=0.025/Sim(u, v)，l_max=3，iter_max=10 000。对数据集1和数据集2进行社团划分，在达到终止条件前其模块度值的变化曲线分别如图 2a和图 2b所示。

根据图 2中最大模块度值所对应的社团个数，将Zachary空手道俱乐部成员关系网络划分成了4个社团，Power网络划分成了130个社团，其结果分别如图 3a和图 3b所示。

在图 3a中，数据集1被划分成的4个社团分别用不同形状进行了表示，节点越大表示节点的度值越大，基本符合该俱乐部分裂后以节点34和节点1各自为核心构成小俱乐部的实际情况。

在图 3b中，数据集2被划分成的130个社团分别用不同深浅度进行了表示，但其节点的度值差距较大，表明各个节点在整个高压电网络中所承担的输送电量有所差别。这与实际中变电站、变压器和发电机所输送电量有较大差距的情况相符合。

综合图 3a和图 3b的分析结果可以表明：基于Memetic的静态网络社团检测算法具有可行性，社团的划分结果能够满足实际情况的需求。

2) 有效性分析

关于静态网络的社团检测，第一种评价指标是度量社团划分紧密程度的模块度，如定义4。第二种评价指标是统一化互信息(normalized mutual information, NMI)，用来评估真实社团结构与算法发现到社团结构的相似度^[24]，其定义如下：

式中，N矩阵的行对应真实社团，矩阵的列对应算法所发现的社团；N_ij为真实社团i与算法所发现的社团j的重合节点个数；N_i*为第i行元素之和；N_.j代表第j列元素之和；CA表示真实社团个数；CB表示算法所发现的社团个数；A表示真实的社团结构；B表示算法所发现的社团结构。

为验证本文算法的有效性，针对数据集1和数据集2，将本文算法与经典的GN^[25]、FN^[26]和BGLL^[27]算法分别就模块度和NMI值进行了比较，其结果分别如表 2和表 3所示。

通过表 2和表 3可以看出，本文算法在数据集1和数据集2上的模块度和NMI值都高于其他算法，因此该算法发现社团结构的准确度高，且所发现社团的结构比较紧密。

设置社团演化分析算法中社团匹配度τ的取值为0.6 (也可以根据用户偏好取其他的值)，以下实验将对社团演化分析算法的可行性和有效性进行论证。

1) 可行性分析

根据表 3中的算法，对数据集1因俱乐部主管John A.(节点34)与教练Mr. Hi(节点1)之间争执而分裂时社团的演变情况进行分析，其社团演变状态结果如图 4所示。

图 4中每一种线条代表了一个社团的动态演变轨迹。在t=18时，社团1消失，因此该社团的生存周期为17，同理可以得到其他社团的生存周期。在t=19时，社团1刚刚因分裂而消失，两个新的社团产生，而在实际情况中，正是此时该俱乐部因争执分裂成了两个各自为核心的小俱乐部，与客观情况相符。此外，从图 4中还可以发现：在t=34时，社团3所代表的小俱乐部又进行了一次分裂。

2) 有效性分析

本文通过NMI比较了Power网络已知动态社团的数量以及对应的生存周期与挖掘结果之间的差距，并将其与文献[28]中基于张量分解的社团演化分析方法进行了比较，其结果如图 5所示。

实验结果表明，相比基于张量分解的社团演化分析方法，本文所提出的社团演化分析算法能够较好地刻画社团演化，验证了该算法的有效性。

本文提出了一种面向动态网络的社团检测与演化分析方法，其主要特点有：

1) 该方法在时刻上运行基于Memetic的静态社团检测算法，然后在时序上运行社团演化分析算法，最终可以得到社团的动态演变轨迹；

2) 设计了一种具有指向性的变异策略，将变邻域搜索算法作为局部搜索算子，提出了一种基于Memetic的静态社团检测算法，并在Zachary空手道俱乐部网络和Power网络上验证了该算法的可行性和有效性。

3) 通过定义匹配度和社团生存周期，分析不同时刻社团集合的匹配度来发现社团演变事件，提出了一种社团演化分析算法。该算法在Zachary空手道俱乐部网络上进行了演化分析，在Power网络上与基于张量分解的社团演化分析方法进行了对比分析，分别验证了其可行性和有效性。