ISSN 
-
在信息和网络技术快速发展的背景下，动态网络受到越来越多的关注，例如信息交互网络、社交网络、生物网络等[1-3]。目前关于动态网络的研究主要集中在动态社团挖掘、动态子图挖掘和时序边的预测等[4]。而动态网络演化分析方法的研究，无论是在生物信息领域还是在社会和科技领域都处于初级阶段，常采用以下两类方法：1)演变社团检测；2)通过识别社团演变的关键事件来发现社团演变模式[5]。演变社团检测的主要方法是增量聚类和进化聚类，目前已有较多研究[6-9]，而如何设计高效的社团演变模式挖掘算法成为制约动态网络演化分析的瓶颈[4]。
针对上述问题，本文采用基于事件的动态网络分析架构，提出了一种面向动态网络的社团检测与演化分析方法，该方法将动态网络的时序动态性和时刻静态性用时间序列的方式进行表示，在时刻上运行基于Memetic的静态社团检测算法，在时序上运行社团演化分析算法，最终可以得到社团的动态演变轨迹，能够应用于实际动态网络的演化分析。
-
动态网络研究中涉及到很多与静态网络类似的概念与问题，本节首先对文中通用的概念与问题给出形式化的定义，符号说明如表 1所示。
表 1 符号说明
符号名称 含义 G 整个动态图 $ {g^{(t)}} $ t时刻的网络快照 $ C_i^{(t)} $ $ {g^{(t)}} $中的第i个社团 $ V({g^{(t)}}) $或$ V(C_i^{(t)}) $ $ {g^{(t)}} $或$ C_i^{(t)} $的顶点集 $ E({g^{(t)}}) $或$ E(C_i^{(t)}) $ $ {g^{(t)}} $或$ C_i^{(t)} $的边集 $ {\rm{ad}}{{\rm{j}}^{(t)}}( \cdot ) $ $ {g^{(t)}} $中顶点或社团的邻接顶点 $ n(V({g^{(t)}})) $ $ {g^{(t)}} $中顶点的总数 τ 社团之间的匹配度 定义 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)} $，结构相似度定义为：
$$ \text{Sim}(C_{i}^{(t)},C_{j}^{(t)})=\frac{\left| \text{ad}{{\text{j}}^{(t)}}(C_{i}^{(t)})\cap \text{ad}{{\text{j}}^{(t)}}(C_{j}^{(t)}) \right|}{\sqrt{\left| \text{ad}{{\text{j}}^{(t)}}(C_{i}^{(t)}) \right|\left| \text{ad}{{\text{j}}^{(t)}}(C_{j}^{(t)}) \right|}} $$ (1) 采用具有指向性的变异策略可以尽量保留社团间结构相似度较小的个体，变异社团间结构相似度较大的个体，使变异朝社团内部点和外部点联系稀疏的方向进行，进而快速收敛到最优个体。
3) 适应度函数
本文适应度函数使用基于相似度的模块度函数，使得网络中社团内部节点对的相似度要高于分属于不同社团的节点对相似度，其定义如下。
定义 4[15] 模块度。对于t时刻的网络快照g(t)，若个体x所对应的社团集合为$ {C^{(t)}}\left| x \right. = $$ \{ C_1^{(t)}, C_2^{(t)}, \cdots, C_p^{(t)}\} $，则其模块度函数被定义为：
$$ Q({C^{(t)}}\left| x \right.) = \sum\limits_{i = 1}^p {\left[{\frac{{IS_i^{(t)}}}{{T{S^{(t)}}}}-{{\left( {\frac{{DS_i^{(t)}}}{{T{S^{(t)}}}}} \right)}^2}} \right]} $$ (2) 式中，$ \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算法中，可以在社团划分过程中通过动态地改变邻域结构来拓展搜索范围，从而使搜索过程跳出局部最优向全局最优靠近。
邻域结构集Nl(x)(l=1, 2, …, lmax)的构造是VNS算法最核心的部分。本文设计了3种邻域结构，具体形式如下：
① 交换/N1(x)
随机选择第i个个体的任意两节点vm和$ {v_n}(m \ne n) $；交换vm和vn所属社团。
② 多点交换/N2(x)
随机选择第i个个体的任意两节点vm和$ {v_n}(m \ne n) $；交换vm和vn所属社团；重复以上两个步骤至少两次。
③ 复合交换/N3(x)
随机选择第i个个体的任意两节点vm和vn$ (m \ne n) $；随机选择第i个个体中任意两个序列p和q，$ p \ne q \ne m \ne n $；将vm所属社团置于p序列，将vn所属社团置于q序列。
仿真实验发现，调用VNS算法时，按照先N1(x)交换，再多点交换，最后复合交换的顺序(即l单调递增)，算法性能表现最好，因此本文仿真实验按此顺序使用这3种离散邻域结构。以下是VNS算法的详细步骤。
输入：初始个体x*、lmax
输出：局部最优个体
构造离散邻域结构集Nl(x)；
for l=1: lmax 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)、交叉概率、变异概率、最大迭代次数itermax
输出：t时刻的社团结构
随机初始化M个个体；
for iter=1: itermax 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)} $之间的匹配度定义为：
$$ \text{Mat}(C_{i}^{(t)},C_{j}^{(t+1)})=V\text{Sim}(C_{i}^{(t)},C_{j}^{(t+1)})\times E\text{Sim}(C_{i}^{(t)},C_{j}^{(t+1)}) $$ (3) 式中，
$$ \begin{array}{l} V{\rm{{\rm{Sim}}}}(C_i^{(t)}, C_j^{(t + 1)}) = \frac{{\left| {V(C_i^{(t)}) \cap V(C_j^{(t + 1)})} \right|}}{{\sqrt {\left| {V(C_i^{(t)})} \right|\left| {V(C_j^{(t + 1)})} \right|} }}\\ E{\rm{Sim}}(C_i^{(t)}, C_j^{(t + 1)}) = \frac{{\left| {E(C_i^{(t)}) \cap E(C_j^{(t + 1)})} \right|}}{{\sqrt {\left| {E(C_i^{(t)})} \right|\left| {E(C_j^{(t + 1)})} \right|} }} \end{array} $$ 分别表示$ 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| $，其中：
$$ {\rm{lifetime}}(C_i^{(t)}) = \left\{ {C_{i1}^{(1)}, C_{i2}^{(2)}, \cdots, C_{in}^{(T)}} \right\}, \forall t = 0, 1, \cdots, T -1 $$ 表示社团$ 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，交叉概率Pc=0.6，变异概率Pm=0.025/Sim(u, v)，lmax=3，itermax=10 000。对数据集1和数据集2进行社团划分，在达到终止条件前其模块度值的变化曲线分别如图 2a和图 2b所示。
图 2 模块度值变化曲线
根据图 2中最大模块度值所对应的社团个数，将Zachary空手道俱乐部成员关系网络划分成了4个社团，Power网络划分成了130个社团，其结果分别如图 3a和图 3b所示。
图 3 社团划分结果
在图 3a中，数据集1被划分成的4个社团分别用不同形状进行了表示，节点越大表示节点的度值越大，基本符合该俱乐部分裂后以节点34和节点1各自为核心构成小俱乐部的实际情况。
在图 3b中，数据集2被划分成的130个社团分别用不同深浅度进行了表示，但其节点的度值差距较大，表明各个节点在整个高压电网络中所承担的输送电量有所差别。这与实际中变电站、变压器和发电机所输送电量有较大差距的情况相符合。
综合图 3a和图 3b的分析结果可以表明：基于Memetic的静态网络社团检测算法具有可行性，社团的划分结果能够满足实际情况的需求。
2) 有效性分析
关于静态网络的社团检测，第一种评价指标是度量社团划分紧密程度的模块度，如定义4。第二种评价指标是统一化互信息(normalized mutual information, NMI)，用来评估真实社团结构与算法发现到社团结构的相似度[24]，其定义如下：
$$ I(A,B)=\frac{-2\sum\limits_{i=1}^{\text{CA}}{\sum\limits_{j=1}^{\text{CB}}{{{N}_{ij}}\log ({{N}_{ij}}N/{{N}_{i\centerdot }}{{N}_{\centerdot j}}\ )}}}{\sum\limits_{i=1}^{\text{CA}}{{{N}_{i}}\log ({{N}_{i\centerdot }}/N\ )+\sum\limits_{j=1}^{\text{CB}}{{{N}_{\centerdot j}}\log ({{N}_{\centerdot j}}/N\ )}}} $$ (4) 式中，N矩阵的行对应真实社团，矩阵的列对应算法所发现的社团；Nij为真实社团i与算法所发现的社团j的重合节点个数；Ni*为第i行元素之和；N.j代表第j列元素之和；CA表示真实社团个数；CB表示算法所发现的社团个数；A表示真实的社团结构；B表示算法所发现的社团结构。
为验证本文算法的有效性，针对数据集1和数据集2，将本文算法与经典的GN[25]、FN[26]和BGLL[27]算法分别就模块度和NMI值进行了比较，其结果分别如表 2和表 3所示。
表 2 本文算法与其他算法的模块度值比较
算法 数据集 Zachary Power GN 0.401 0.613 FN 0.380 0.606 BGLL 0.418 0.622 本文算法 0.421 0.623 表 3 本文算法与其他算法的NMI值比较
算法 数据集 Zachary Power GN 0.58 0.91 FN 0.69 0.86 BGLL 0.59 0.90 本文算法 0.71 0.92 通过表 2和表 3可以看出，本文算法在数据集1和数据集2上的模块度和NMI值都高于其他算法，因此该算法发现社团结构的准确度高，且所发现社团的结构比较紧密。
-
设置社团演化分析算法中社团匹配度τ的取值为0.6 (也可以根据用户偏好取其他的值)，以下实验将对社团演化分析算法的可行性和有效性进行论证。
1) 可行性分析
根据表 3中的算法，对数据集1因俱乐部主管John A.(节点34)与教练Mr. Hi(节点1)之间争执而分裂时社团的演变情况进行分析，其社团演变状态结果如图 4所示。
图 4 Zachary空手道俱乐部成员关系网络演化分析
图 4中每一种线条代表了一个社团的动态演变轨迹。在t=18时，社团1消失，因此该社团的生存周期为17，同理可以得到其他社团的生存周期。在t=19时，社团1刚刚因分裂而消失，两个新的社团产生，而在实际情况中，正是此时该俱乐部因争执分裂成了两个各自为核心的小俱乐部，与客观情况相符。此外，从图 4中还可以发现：在t=34时，社团3所代表的小俱乐部又进行了一次分裂。
2) 有效性分析
本文通过NMI比较了Power网络已知动态社团的数量以及对应的生存周期与挖掘结果之间的差距，并将其与文献[28]中基于张量分解的社团演化分析方法进行了比较，其结果如图 5所示。
图 5 算法比较
实验结果表明，相比基于张量分解的社团演化分析方法，本文所提出的社团演化分析算法能够较好地刻画社团演化，验证了该算法的有效性。
-
本文提出了一种面向动态网络的社团检测与演化分析方法，其主要特点有：
1) 该方法在时刻上运行基于Memetic的静态社团检测算法，然后在时序上运行社团演化分析算法，最终可以得到社团的动态演变轨迹；
2) 设计了一种具有指向性的变异策略，将变邻域搜索算法作为局部搜索算子，提出了一种基于Memetic的静态社团检测算法，并在Zachary空手道俱乐部网络和Power网络上验证了该算法的可行性和有效性。
3) 通过定义匹配度和社团生存周期，分析不同时刻社团集合的匹配度来发现社团演变事件，提出了一种社团演化分析算法。该算法在Zachary空手道俱乐部网络上进行了演化分析，在Power网络上与基于张量分解的社团演化分析方法进行了对比分析，分别验证了其可行性和有效性。
New Community Detection and Evolution Analysis Method for Dynamic Networks
-
摘要: 针对制约动态网络演化分析方法发展的社团演变模式挖掘问题，设计了基于指向性变异策略和变邻域搜索算法的静态社团检测算法与基于匹配度和社团生存周期的社团演化分析算法，并采用在时刻上运行静态社团检测算法、在时序上运行社团演化分析算法的策略，提出了一种面向动态网络的社团检测与演化分析方法。并用Zachary空手道俱乐部网络和Power网络验证了该方法的可行性和有效性。Abstract: Aiming at the mining problem for evolutionary community patterns, which restricts the development of evolution analysis methods for dynamic network, this paper designs a static community detection algorithm based on a kind of directed mutation strategy and variable neighborhood search algorithm, and a community evolution analysis algorithm based on compatibility and community {\rm{lifetime}}. Through adopting a strategy that runs static community detection algorithm on the moment and community evolution analysis algorithm on the sequential, a new community detection and evolution analysis method for dynamic network is proposed. In the experiment, the feasibility and effectiveness of the proposed method are verified by Zachary karate club network and power network.
-
Key words:
- community detection /
- community {\rm{lifetime}} /
- dynamic network /
- evolution analysis
-
表 1 符号说明
符号名称 含义 G 整个动态图 $ {g^{(t)}} $ t时刻的网络快照 $ C_i^{(t)} $ $ {g^{(t)}} $中的第i个社团 $ V({g^{(t)}}) $或$ V(C_i^{(t)}) $ $ {g^{(t)}} $或$ C_i^{(t)} $的顶点集 $ E({g^{(t)}}) $或$ E(C_i^{(t)}) $ $ {g^{(t)}} $或$ C_i^{(t)} $的边集 $ {\rm{ad}}{{\rm{j}}^{(t)}}( \cdot ) $ $ {g^{(t)}} $中顶点或社团的邻接顶点 $ n(V({g^{(t)}})) $ $ {g^{(t)}} $中顶点的总数 τ 社团之间的匹配度 
下载: 导出CSV
表 2 本文算法与其他算法的模块度值比较
算法 数据集 Zachary Power GN 0.401 0.613 FN 0.380 0.606 BGLL 0.418 0.622 本文算法 0.421 0.623
下载: 导出CSV
表 3 本文算法与其他算法的NMI值比较
算法 数据集 Zachary Power GN 0.58 0.91 FN 0.69 0.86 BGLL 0.59 0.90 本文算法 0.71 0.92
下载: 导出CSV
-
[1] FORTUNATO S. Community detection in graphs[J]. Physics Report, 2010, 486(3-5):75-174. doi: 10.1016/j.physrep.2009.11.002 [2] SPILIOPOULOU M. Evolution in social networks:a survey[J]. Social Network Data Analytics, 2011, 978(3):149-175. doi: 10.1007/978-1-4419-8462-3_6 [3] FRASER H B. Modularity and evolutionary constraint on proteins[J]. Nature Genetics, 2005, 37(4):351-352. doi: 10.1038/ng1530 [4] 高琳, 杨建业, 覃桂敏.动态网络模式挖掘方法及其应用[J].软件学报, 2013, 24(9):2042-2061. http://d.wanfangdata.com.cn/Periodical/rjxb201309004 GAO Lin, YANG Jian-ye, QIN Gui-min. Methods for pattern mining in dynamic networks and applications[J]. Journal of Software, 2013, 24(9):2042-2061. http://d.wanfangdata.com.cn/Periodical/rjxb201309004 [5] 刘瑶, 王瑞锦, 刘峤.动态社会网络的社团结构发现与分析[J].电子科技大学学报, 2014, 43(5):725-729. http://manu50.magtech.com.cn/dzkjdx/CN/abstract/abstract482.shtml LIU Yao, WANG Rui-jin, LIU Qiao, et al. Community detecting and analyzing in dynamic social networks[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(5):725-729. http://manu50.magtech.com.cn/dzkjdx/CN/abstract/abstract482.shtml [6] CHAKRABARTI D, KUMAR R, TOMKINS A. Evolutionary clustering[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Philadelphia: ACM, 2006. [7] TANTIPATHANANANDH C, BERGER-WOLF T, KEMPE D. A framework for community identification in dynamic social networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose: ACM, 2007. [8] LIN Y R, CHI Y, ZHU S, et al. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks[C]//Proceedings of the 17th International Conference on World Wide Web. Beijing: ACM, 2008. [9] KIM M S, HAN J. A particle-and-density based evolutionary clustering method for dynamic networks[J]. Proceedings of the VLDB Endowment, 2009, 2(1):622-633. doi: 10.14778/1687627 [10] 吴斌, 王柏, 杨胜琦.基于事件的社会网络演化分析框架[J].软件学报, 2011, 22(7):1488-1502. http://www.oalib.com/paper/5072788 WU Bin, WANG Bai, YANG Sheng-qi. Framework for tracking the event-based evolution in social networks[J]. Journal of Software, 2011, 22(7):1488-1502. http://www.oalib.com/paper/5072788 [11] 杨淑莹, 张桦.群体智能与仿生计算-Matlab技术实现[M].北京:电子工业出版社, 2012. YANG Shu-ying, ZHANG Hua. Swarm intelligence and bionic calculation-technical implementation for Matlab[M]. Beijing:Publish House of Electronic Industry, 2012. [12] TASGIN M, HERDAGDELEN A, BINGOL H. Community detection in complex networks using genetic algorithms[EB/OL]. (2012-12-15). http://arxiv.org/abs/0711.0491. [13] PIZZUTI C. GA-NET: a genetic algorithm for community detection in social networks[C]//Proceedings of the 10th International Conference on Parallel Problem Solving from Nature. Dortmund: Springer, 2008: 1081-1090. [14] GONG M, FU Bao, JIAO L, et al. Memetic:Algorithm for community detection in networks[J]. Physical Review E, 2011, 84(5):56-101. https://www.ncbi.nlm.nih.gov/pubmed/22181467 [15] FENG Z, XU X. A novel similarity-based modularity function for graph partitioning[J]. Data Warehousing and Knowledge Discovery, 2007(46-54):385-396. doi: 10.1007%2F978-3-540-74553-2_36 [16] JARBOUI B, DERBEL H. Variable neighborhood search for location routing[J]. Computers and Operations Research, 2013, 40:47-57. doi: 10.1016/j.cor.2012.05.009 [17] 范成礼, 邢清华, 范海雄.带审敛因子的变邻域粒子群算法[J].控制与决策, 2014, 29(4):696-700. http://industry.wanfangdata.com.cn/hk/Detail/Periodical?id=Periodical_kzyjc201404020 FAN Cheng-li, XING Qing-hua, FAN Hai-xiong. The particle swarm optimization and variable neighborhood search algorithm with convergence criterions[J]. Control and Decision, 2014, 29(4):696-700. http://industry.wanfangdata.com.cn/hk/Detail/Periodical?id=Periodical_kzyjc201404020 [18] CHEN Y Y, CHENG C Y. A hybrid approach based on the variable neighborhood search and particle swarm optimization for parallel machine scheduling problems-A case study for solar cell industry[J]. Int J Production Economics, 2013, 141:66-78. doi: 10.1016/j.ijpe.2012.06.013 [19] PALLA G, BARABASI A L, VICSEK T. Quantifying social group evolution[J]. Nature, 2007, 446(7136):664-667. doi: 10.1038/nature05670 [20] PALLA G, DENENYI I. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043):814-818. doi: 10.1038/nature03607 [21] GREENE D, DOYLE D, CUNNINGHAM P. Tracking the evolution of communities in dynamic social networks[C]//Proceedings of the Int'l Conf on Advances in Social Networks Analysis and Mining. Denmark: ASONAM, 2010: 176-183. [22] BERGER W T Y, SAIA J. A framework for analysis of dynamic social networks[C]//Proceedings of the 12th ACM SIGKDD International Conference on Konwledge Discovery and Data Mining. USA: ACM, 2006: 523-528. [23] 邓琨, 张健沛, 杨静.利用改进遗传算法进行复杂网络社团发现[J].哈尔滨工程大学学报, 2013, 34(11):1439-1444. https://www.wenkuxiazai.com/doc/c67cebef65ce050876321358.html DENG Kun, ZHANG Jian-pei, YANG Jing. Community detection in complex networks using an improved genetic algorithm[J]. Journal of Harbin Engineering University, 2013, 34(11):1439-1444. https://www.wenkuxiazai.com/doc/c67cebef65ce050876321358.html [24] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. National Academy of Science, 2002, 9(12):7821-7826. http://arxiv.org/abs/condmat/0112110/ [25] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):066133. doi: 10.1103/PhysRevE.69.066133 [26] BLONBEL V D, GUILLAUME J, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics Theory & Experiment, 2008(10):155-168. http://www.academia.edu/.../Fast_unfolding_of_communities_in_large_networks [27] 王柏. 社会网络中社团发现及网络演化分析[D]. 北京: 北京邮电大学, 2014. WANG Bai. Research on community detecting and evolution analysis in social network[D]. Beijing: Beijing University of Posts and Telecommunications, 2014. -
点击查看大图
图(5) / 表(3)
计量
- 文章访问数: 5759
- HTML全文浏览量: 1213
- PDF下载量: 176
- 被引次数: 0
