开放科学（资源服务）标志码（OSID）：

0 概述

在现实世界中，许多事物之间的关系可用复杂网络表示。复杂网络又分为重叠社区和非重叠社区，若节点只属于一个社区，称该社区为非重叠社区；反之则称为重叠社区。目前的研究主要集中在非重叠社区检测，而真实社交网络中的社区通常是互相重叠的^[1]，例如个体可能会同时属于学校和社区，且其在网络中也可能会同时存在于多个兴趣小组中。因此，重叠社区的研究对于复杂网络的结构分析具有重要意义^[2]。

近年来，研究者发现，重叠社区与现实世界网络的实际社区结构较为贴近，更具有研究意义，一些优秀的思想和方法被相继提出。2004年，NEWMAN等提出经典的基于分裂思想的社团检测算法^[3]。2005年，PALLA等提出基于派系过滤思想的重叠社区发现算法^[4]。之后，研究者围绕派系过滤提出了多种不同的方法，如FARKAS等提出针对加权网络的社区划分算法^[5]，KUMPULA等提出快速的派系过滤算法^[6]。2007年，RAGHAVAN等提出了著名的标签传播算法^[7]。其后，研究者又提出了一些新的基于标签传播的改进算法，如SHANG等提出了一种基于循环搜索核心节点并根据节点的相似度进行标签传播的方法^[8]，文献[9-10]提出了基于节点重要性进行社区检测的标签传播方法，WANG等提出了一种改进随机策略^[11]，提高了标签传播算法的稳定性，但这些算法都只是解决了非重叠社区的划分问题。为了将标签传播算法应用到重叠社区检测中，STEVE等提出了基于标签隶属度的重叠社区检测算法^[12]（Community Overlap Propagation Algorithm，COPRA），XIE等提出了一种基于speaker和listener的标签传播算法^[13]，SUN等提出了一种基于优势标记传播的网络重叠社区检测算法^[14]，MA等在COPRA的基础上提出了一种采用PageRank和节点聚类系数的标签传播重叠社区检测算法^[15]。这些算法都保持了标签传播算法可应用于大规模复杂网络重叠社区检测的优点，然而，并没有解决LPA随机性强、准确性差的问题，不能有效提高社区划分质量。

本文提出一种基于节点引力和鱼记忆的社区检测算法。通过节点质量计算节点信息熵，并将信息熵融入k-shell算法中进行节点排序，同时根据节点与标签间的引力，使用鱼记忆节点标签存储策略实现标签更新，从而解决标签传播随机性造成社区划分不稳定的问题，提高社区检测的准确性。

1 基于节点引力与鱼记忆的标签传播算法

当前的标签传播算法有近似线性的时间复杂度，但稳定性较差，即多次运行算法的社区发现结果差异很大。有效解决节点更新的随机性及标签选择的不确定性，可以增强社区检测的稳定性，提高社区检测质量。本文提出的算法通过节点间的相互关系和节点标签间的吸引力，解决节点排序与标签传播更新两个重要步骤的随机性与不确定性问题。

1.1 相关定义

设定图$ G=\left(V, E\right) $为复杂网络，$ V=\left({v}_{1}, {v}_{2}, \cdots , {v}_{n}\right) $为图的节点集，$ E $表示图的边集，本文仅对无向图结构进行研究。各节点在图$ G $中的度用$ {k}_{i} $表示，如图 1所示，则$ V=\left({v}_{1}, {v}_{2}, \cdots , {v}_{9}\right) $，节点$ {v}_{1} $的度$ k=3 $。

定义1    如果图G中的节点$ u $满足：

$ N\left({v}_{i}\right)=\left\{{u}_{i}\left|\left({u}_{i}, v\right)\in E\wedge {u}_{i}\in V\right.\right\} $

(1)

则称$ N\left({v}_{i}\right) $为$ {v}_{i} $的邻居节点集，$ {u}_{i} $为$ {v}_{i} $的邻居节点。在简单结构图G中，有$ N\left({v}_{1}\right)=\left\{{v}_{2}, {v}_{4}, v{}_{8}\right\} $。

定义2（节点质量）   对于$ G=\left(V, E\right) $，节点质量表示节点在图中各点的质量大小，即重要程度。

一个节点可能是潜在的社区中心，即该节点具有以下特征：它与更多的邻居节点连接，并且这些邻居节点紧密地相互连接。一个节点与其邻居节点连接得越紧密，这个节点与其邻居节点形成的三角形就越多，这意味着如果一个节点具有较大的度，并且与其邻居节点形成更多的三角形，那么该节点质量越好，成为社区中心的可能性越大。因此，本文采用三角形数量及节点的度来表示节点质量，定义为：

$ {Q}_{i}=\frac{1}{2}\left(1+\frac{\left({T}_{i}+{k}_{i}\right)-\underset{l\in V}{\mathrm{m}\mathrm{i}\mathrm{n}}\left({T}_{l}+{k}_{l}\right)}{\underset{j\in V}{\mathrm{m}\mathrm{a}\mathrm{x}}\;\mathrm{m}\mathrm{a}\mathrm{x}\left({T}_{j}+{k}_{j}\right)-\underset{l\in V}{\mathrm{m}\mathrm{i}\mathrm{n}}\left({T}_{l}-{k}_{l}\right)}\right) $

(2)

其中：$ {T}_{i} $表示节点$ i $所属三角形的数量。

定义3（节点信息熵）  节点信息熵表示节点获取邻居节点信息时消耗的能量，定义为：

$ {E}_{i}=-\sum\limits_{j\in \Gamma \left(i\right)}{Q}_{j}\cdot \mathrm{l}\mathrm{n}{Q}_{j} $

(3)

信息熵由节点质量计算得到，用以表示该节点质量的强弱，即节点在图中的中心度。

定义4（节点相似度）  节点相似度反映了两个相邻节点之间的连接强度。

常用的相似度计算方法是用Katz函数^[16]进行相似度度量，然而它不能有效区分两个节点之间的程度差异对节点相似性的影响。此外，该算法计算复杂度很高。受Jaccard函数^[17]的启发，本文提出一个基于Jaccard函数的相似性函数，如式（4）所示：

$ {S}_{ij}=\left\{\begin{array}{l}\frac{\left|{N}_{i}\bigcap {N}_{j}\right|}{\left|{N}_{i}\bigcup {N}_{j}\right|}, i\mathrm{、}j相连且有公共邻居节点\\ \frac{\alpha }{k（i）+k（j）}\sum\limits_{t, r\in {D}_{ij}, t\ne r}{S}_{tr}, i\mathrm{、}j相连且没有公共邻居节点\\ 0\text{，}i\mathrm{、}j不相连或i=j\end{array}\right. $

(4)

其中：$ \alpha $为相似度系数，$ \alpha =0.2~1 $；$ {S}_{tr} $为节点$ t\mathrm{、}r $之间的节点相似度；$ {D}_{ij} $为节点$ i $到$ j $最优路径上的所有节点。

定义5（节点引力）   节点$ j $对$ i $的引力大小定义为：

$ {G}_{j}\left(i\right)=\frac{{E}_{i}{E}_{j}}{{\beta }_{ij}} $

(5)

$ \beta =\frac{\underset{t\in N\left(i\right)}{\mathrm{m}\mathrm{a}\mathrm{x}}S(t, i)}{{S}_{ij}} $

(6)

在标签传播过程中，不同邻居节点间的引力大小是不同的，也就导致不同节点间的信息影响程度不同。本文用节点的信息熵$ E $及相似度$ S $来表示节点引力，并通过节点引力计算节点对不同节点标签的引力大小，使得节点更新变得更加合理。$ E $越大，$ S $越大，节点对标签的引力就越大。

定义6（节点记忆）  模拟鱼的记忆存储特征，构建一个节点记忆集合：

$ \left\{\begin{array}{l}{M}_{i}={M}_{i}^{\mathrm{\text{'}}}\bigcup {M}_{i}^{″}\\ {M}_{i}^{\text{'}}=\left\{{l}_{d}^{m-2n}, \cdots , {l}_{d}^{m-2}, {l}_{d}^{m}\right\}\\ {M}_{i}^{″}=\left\{{l}_{d}^{m-(2n+1)}, \cdots , {l}_{d}^{m-3}, {l}_{d}^{m-1}\right\}\end{array}\right. $

(7)

其中：$ {l}_{d} $为每一次迭代节点$ i $中的支配标签；$ m $为当前迭代次数。在标签传播中，复杂网络节点极易造成标签震荡（即两个标签交替支配节点），使得网络形成二分图结构，严重时会导致无法检测出社团。根据鱼记忆特征，每个记忆存储保存最近$ n $次迭代的记忆，$ {M}_{i} $出现$ n $次记忆相同时，则视为节点标签出现记忆振荡，需要做进一步处理。鱼记忆的存储策略既解决了标签振荡，可保持算法的准确性，又减少了计算成本及内存的损耗。

1.2 标签更新策略

本文借鉴文献[12]的设计思想，使用$ g\left(c, u\right) $来表示节点$ u $对标签的引力。引力足够大时才能将标签吸引到节点，迭代结束时，通过引力大小来生成节点的标签集，从而检测到重叠社区。

为了降低标签传播的复杂性，只传播具有最大归属系数的优势标签^[14]，同时避免随机更新节点标签带来的社区检测不稳定性，将节点熵融入k-shell算法^[18]对节点进行排序，节点标签将根据排序进行标签更新。笔者认为，节点k值越高、信息熵越大，节点成为潜在社区中心的概率越大。因此，按升序对节点进行排序，可以使潜在社区中心的标签传播得足够远，以占据社区中心，然后社区可以获得与其他社区边界区域中的节点，从而检测到更准确的社区结构。

在每一次迭代的开始，首先更新标签及节点间引力大小，具体更新策略如下：

1）根据节点的k值，对节点$ u\in V $进行分壳处理，将相同k值的节点分在同一壳内。

2）计算各节点信息熵，在每一k壳中进行升序排序，然后进行总体升序排序。

3）对于节点，在迭代开始更新标签时，节点只接收各邻居节点引力最大的标签，并形成邻居节点标签集：

$ {L}_{i}=\left\{{l}_{j\to i}\left|j\in N\left(i\right)\right.\right\} $

(8)

其中：$ {l}_{j\to i}=({c}_{j}, {g}_{j}) $；$ {c}_{j} $为节点$ j $中受节点$ i $引力最强的标签；$ {g}_{j} $为该标签受节点$ i $引力的大小。根据节点排序获取邻居节点的支配标签集$ {L}_{i} $（若是第一次迭代则获取初始标签），能够保证所获取标签对节点的支配性，降低标签的随机性。

4）基于$ G $和$ {L}_{i} $计算并更新节点$ i $对标签$ {c}_{j} $的引力大小：

$ \widehat{g}=\frac{\sum\limits_{{l}_{j\to i}\in {L}_{i}, j\in N\left(i\right), {c}_{j}=c}g\left({c}_{j}, j\right)\cdot {G}_{j}\left(i\right)}{\sum\limits_{{l}_{j\to i}\in {L}_{i}, j\in N\left(i\right)}g\left({c}_{j}, j\right)\cdot {G}_{j}\left(i\right)}, \sum \widehat{g}\left(c, j\right)=1 $

(9)

更新$ {\widehat{L}}_{i}=\left\{{\widehat{l}}_{n\to i}\left|n\in N\left(c\right)\right.\right\} $。其中：$ {\widehat{l}}_{n\to i}=({c}_{n}, {\widehat{g}}_{n}) $，$ n $为$ {\widehat{L}}_{i} $中标签的个数，根据节点间引力大小、标签集中的标签个数和各标签引力大小，计算并更新节点$ i $的标签集及节点$ i $对各标签引力的大小。将节点间引力关系映射到节点与标签间的引力关系中，将标签对源节点的引力关系与源节点对节点$ i $的引力关系相结合，从而计算出标签在节点$ i $所受到的引力大小，提高算法的准确性。

5）删除$ {\widehat{g}}_{n}\le \frac{1}{n} $的节点，更新节点对各标签的引力：

$ {\widehat{\widehat{g}}}_{m}=\frac{{\widehat{g}}_{m}}{\sum\limits_{j\in {N}^{\mathrm{\text{'}}}\left(c\right)}{\widehat{g}}_{j}}, \sum \widehat{\widehat{g}}\left(c, j\right)=1 $

(10)

更新$ {\widehat{\widehat{L}}}_{i}=\left\{{\widehat{\widehat{l}}}_{m\to i}\left|m\in {N}^{\text{'}}\left(c\right)\right.\right\} $，$ {\widehat{\widehat{l}}}_{m\to i}=({c}_{m}, {\widehat{\widehat{g}}}_{m}) $。其中：$ m $为$ {\widehat{\widehat{L}}}_{i} $中标签的个数；$ {\widehat{\widehat{L}}}_{i} $为该节点迭代最后的标签集。对第4）步中计算的标签引力小于阈值的标签进行删减，剩余的标签引力按比例更新进行下一次迭代，这样每一代都能获得邻居节点的最优标签，保证了每一次更新的稳定性。

6）将节点新的标签集以$ {\widehat{\widehat{g}}}_{m} $大小进行升序排序，更新为$ {L}_{i} $，并将$ {L}_{i} $中$ {\widehat{\widehat{g}}}_{m} $值最大的标签作为主导标签$ {l}_{d} $，即传播支配标签。在确定各节点主导标签时，如果节点的标签集中各标签引力相同，并且其中一个是记忆存储中的标签，则选择该主导标签作为当前迭代的主导标签，否则选择其中节点信息熵最大的节点标签作为主导标签。

7）将$ {l}_{d} $存储在标签记忆$ {M}_{i} $中，更新$ {M}_{i} $，当$ {M}_{i} $内出现标签记忆波纹，即该节点标签只保存为$ {l}_{d} $将不再改变，且节点引力$ {g}_{\mathrm{d}}\left(c, j\right)=1 $。

CDA-GM算法伪代码如算法1所示。

算法1    CDA-GM

输入   网络$ G=\left(V, E\right) $，最大迭代次数maxIter

输出   节点$ u\left(u\in V\right) $的标签集$ {L}_{\mathrm{u}} $

1.for $ \mathrm{u}, \mathrm{u}\in \mathrm{V} $：

2.$ \mathrm{Q}\left(\mathrm{i}\right)\leftarrow $根据式（2）计算

3.$ {\mathrm{E}}_{\mathrm{i}}\leftarrow $根据式（3）计算

4.$ {\mathrm{S}}_{\mathrm{i}\mathrm{j}}\leftarrow $根据式（4）计算

5.$ {\mathrm{G}}_{\mathrm{j}}\left(\mathrm{i}\right)\leftarrow $根据式（5）计算

6.end for

7.根据k值的大小进行k-shell排序，各k-shell内的节点由$ {\mathrm{E}}_{\mathrm{i}} $进行壳内排序

8.$ \mathrm{t}=0 $

9.for $ \mathrm{u}, \mathrm{u}\in \mathrm{V} $：

10.$ \mathrm{L}\leftarrow \left\{\left({\mathrm{c}}_{\mathrm{u}}, 1\right)\right\} $，$ {\mathrm{l}}_{\mathrm{d}}=\left({\mathrm{c}}_{\mathrm{u}}, 1\right) $

11.将各节点$ {\mathrm{l}}_{\mathrm{d}} $存入$ \mathrm{N}{\mathrm{M}}_{\mathrm{i}} $

12.while$ \mathrm{t} < \mathrm{m}\mathrm{a}\mathrm{x}\mathrm{I}\mathrm{t}\mathrm{e}\mathrm{r} $：

13.for $ \mathrm{u} $：

14.$ {\mathrm{L}}_{\mathrm{i}}\leftarrow $根据式（8）~式（10）更新

15.更新$ {\mathrm{M}}_{\mathrm{i}} $

16.if $ {\mathrm{M}}_{\mathrm{i}} $中出现标签振荡

17.then $ {\mathrm{L}}_{\mathrm{i}}=\left\{{\mathrm{l}}_{\mathrm{d}}\right\} $

18.end if

19.end for

20.$ \mathrm{t}\leftarrow \mathrm{t}+1 $

21.end while

22.Output G

CDA-GM算法的简单图应用如图 2所示。

首先根据式（3）计算出的$ {E}_{i} $进行排序，初始化标签及标签引力$ g=1 $，更新顺序为$ 2\to 6\to 1\to 3\to 5\to $ $ 7\to 8\to 9\to 4 $，然后依据CDA-GM的更新策略进行节点更新。

1.3 时间复杂度分析

一个具有n个节点的图结构，在CDA-GM的第一阶段，时间复杂度分析如下：

1）$ {E}_{i} $的时间复杂度：节点度数和三角形数量的时间复杂度分别为$ {\rm O}\left(k\right) $和$ {\rm O}\left({k}^{2}\right) $，即计算$ {E}_{i} $的时间复杂度为$ {\rm O}\left(n\left({k}^{2}+k\right)m\right) $，$ m $为相连节点数。

2）$ {S}_{ij} $的时间复杂度近似为$ {\rm O}\left(knm+kn\right) $。

3）利用$ {E}_{i} $进行排序的时间复杂度约为$ {\rm O}\left(2n\right) $。

在CDA-GM的第二阶段，标签迭代更新T次的时间复杂度为$ {\rm O}\left(knT\right) $。因此，算法总的时间复杂度为$ {\rm O}\left(n({k}^{2}+k)m+kn\left(m+1\right)+2n+knT\right) $。对于大型网络$ n\gg m\gg k, T $，总时间复杂度为$ {\rm O}\left(nm+\alpha n\right) $，其中，$ \alpha $为常数。由上述可知，CDA-GM各阶段时间复杂度都趋近于线性，更适用于稀疏大规模网络。

2 实验结果与分析

为验证CDA-GM算法的性能，本文在真实数据集和人工数据集上进行社区检测实验，并与其他算法的社区检测结果进行对比。

人工数据集由LFR人工基准发生器^[19]生成，采用标准化互信息（NMI）指标^[20]进行对比评价。真实网络大多情况下是不知其社区划分的，因此，采用当前主流的拓展模块度EQ^[21]函数进行评价。

为更直观地验证CDA-GM的实现效果，分别选取COPRA^[12]、SPLA^[13]、DLPA^[14]、COPRAPC^[15]算法进行对比。将COPRA、SLPA、DLPA的参数分别设置为$ v=2~9 $，$ r=0.1~0.5 $，$ \mathrm{i}\mathrm{n}=1~8 $，使得各算法在指定的参数范围内获得最优评价指标。算法各运行20次，并取最大值的平均值进行对比，减小算法随机性对结果的影响。

2.1 实验数据集 2.1.1 LFR基准网络

LFR基准网络由LANCICHINETTI等^[19]提出，具有真实世界的网络特性，且社区可调模块度呈幂律分布。LFR各参数意义如表 1所示，其中混合参数$ \mu $是衡量算法稳定性的重要指标，表示社区的模糊度，$ \mu $的值越大，则表示网络连边越多，社区结构越不清晰，社区检测的难度越大。重叠社区的LFR基准网络参数设置如表 2所示。

2.1.2 真实世界网络

实验用到的真实数据集有小数据集Karate、Dolphins和Football，以及大数据集Facebook、Ca-HepPh和Email-Enron。其中：小数据集来自于http://www-personal.umich.edu/~mejn/netdata/；大数据集来自于http://snap.stanford.edu/data/。具体数据参数如表 3所示。

2.2 评价指标 2.2.1 标准化互信息

标准化互信息（Normalized Mutual Information，NMI）指标^[20]用于评价已知网络结构的社区检测。因为NMI被用于比较各算法所获取的社区划分与基准网络社区结构间的相似程度，所以只能被用于已知社区结构的网络。NMI指标定义如下：

$ {N}_{\mathrm{N}\mathrm{M}\mathrm{I}}\left(A, B\right)=\frac{-2\sum\limits_{i=1}^{{C}_{A}}\sum\limits_{j=1}^{{C}_{B}}{M}_{ij}\mathrm{l}\mathrm{b}\left(\frac{{M}_{ij}N}{{M}_{i·}{M}_{·j}}\right)}{\sum\limits_{i=1}^{{C}_{A}}{M}_{i·}\mathrm{l}\mathrm{b}\left(\frac{{M}_{i·}}{N}\right)+\sum\limits_{j=1}^{{C}_{B}}{M}_{·j}\mathrm{l}\mathrm{b}\left(\frac{{M}_{·j}}{N}\right)} $

(11)

其中，$ A $、$ B $分别是原有网络社区结构以及算法检测结果；$ {M}_{i·} $表示网络$ A $中第$ i $社区的节点数量；$ {M}_{·j} $为网络$ B $中第$ j $社区的节点数；$ {M}_{ij} $表示两个网络之间的接近程度。NMI在$ \left[\mathrm{0, 1}\right] $之间的值越高，代表算法检测出的社区结构越好。

2.2.2 社区模块度

对于未知社区结构的真实网络，算法划分结果往往采用社区模块度（即Q指标）^[22]作为划分社区结构质量的评价指标。与文献[22]提出的模块度指标不同，因为本文研究的对象是重叠社区，所以采用的是重叠模块度$ {Q}^{\mathrm{E}} $指标^[21]，定义如下：

$ {Q}^{\mathrm{E}}=\frac{1}{2m}\sum\limits_{i}\sum\limits_{x, y\in {C}_{i}}\frac{1}{{O}_{x}{O}_{y}}\left[{A}_{xy}-\frac{{k}_{x}{k}_{y}}{2m}\right] $

(12)

其中：$ m $为网络边数总和；$ {C}_{i} $为最终网络结构的第$ i $社区；各节点$ x $、$ y $的归属社区数为$ {O}_{x} $、$ {O}_{y} $；$ {A}_{xy} $为$ x $、$ y $节点间的邻居矩阵元素。

2.3 算法参数分析 2.3.1 相似度参数分析

本文分别在LFR1与真实世界网络上进行对相似度参数$ \alpha $的实验分析，CDA-GM基于相似度参数不同值在LFR人工网络中的NMI值如图 3所示，真实世界网络中相似度参数的取值如图 4所示。

由图 3、图 4可以看出：当$ \alpha =0.8 $时，CDA-GM的表现明显优于其他参数取值；当网络结构变模糊时，$ \alpha =0.8 $仍能保持一个较好的稳定性及准确性；$ \alpha =1 $虽然也能在结构模糊时保持一定的稳定性，但准确性上却差了一些。

2.3.2 记忆存储参数分析

为分析记忆存储参数，将相似度参数设为0.8，在人工网络LFR1中对是否引入鱼记忆存储及记忆存储个数进行实验对比分析。CDA-GM引入鱼记忆存储方法前后及不同记忆存储个数在LFR1人工网络中的性能表现如图 5所示。

在图 5中，$ n=0 $为没有引入鱼记忆存储策略的CDA-GM算法。可以看出：当$ n=0 $和$ n=2 $时，社区划分结果始终不如$ n > 2 $的社区划分结果，且在网络结构越模糊时表现越明显；当$ n=2 $时，各节点只保存两次迭代，而标签交替出现两次的情况易发生，导致节点的标签多样性严重下降，干扰了检测准确性，社区划分结果反而下降；当$ n > 2 $时，NMI值明显大于没有引入记忆存储的NMI值，说明引入$ n > 2 $的记忆存储后社区划分结果更贴近原有的社区划分，将网络信息进行了更为完整准确的保存。同时由图 5可以看出：$ n > 3 $与$ n=3 $的社区划分结果基本相同。因此，在保证算法计算复杂度及内存占用耗费较低的前提下，本文选择$ n=3 $，即将存储次数为3的标签记忆引入CDA-GM中。

2.4 LFR人工网络实验结果分析

CDA-GM及其他4种比较算法在基准网络LFR1、LFR2和LFR3中的NMI评价结果如图 6所示。

在图 6（a）中，调整$ \mu $值大小，其余参数固定。可以看出：当$ \mu =0.7 $时，其他算法已经基本检测不出社区结果，CDA-GM的NMI值依然能保持在0.2以上，且当$ \mu < 0.7 $时，CDA-GM也始终能获得比其他算法更好的NMI值，说明CDA-GM在模糊图上的社区划分能力更强。

在图 6（b）中，调整$ {O}_{m} $值大小，其余参数固定。可以看出：在不同$ {O}_{m} $值下，CDA-GM具有良好适应性。由于CDA-GM的标签引力设置，节点最多只能拥有3个标签，因此，当$ {O}_{m}\ge 4 $时，CDA-GM的NMI值下降较快。但相比于其他算法，CDA-GM仍能保持一个较优的NMI值，说明在结构复杂的网络中，CDA-GM仍能获得较好的社区划分结果。

在图 6（c）中，调整$ {O}_{n} $的值，控制其他参数不变。可以看出：随着$ {O}_{n} $值增大，社区检测的难度逐渐增大。当$ {O}_{n}={3}_{}500 $时，除了SLPA能保持一个较好的适应性，CDA-GM仍能拥有最高的NMI值，即使是在较多重叠节点的网络中，CDA-GM仍能获得较好的社区划分结果。

本文选取LFR3中$ {O}_{n}={2}_{}000 $的基准网络，将各算法在较复杂网络上进行社区检测稳定性对比，结果如图 7所示。可以看出：CDA-GM的稳定性明显优于COPRA、SLPA和DLPA；COPRAPC的稳定性较好，但极值相差较大。

图 8显示了各算法在LFR4人工网络上的时间耗费。可以看出：DLPA所用的时长最短，SLPA与COPRA相当，这是因为DLPA的时间复杂度为$ \mathrm{{\rm O}}\left(Tm\right) $，其中$ m $是网络中的边数；而COPRA与SLPA的时间复杂度分别为$ {\rm O}\left(vn\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}\right(vm/n\left)\right) $、$ {\rm O}\left(Tn\right) $，其中，$ T $为迭代次数，$ v $为社区数量。图 8中因LFR4网络结构较为简单，当社区规模增大时，边的数量相比于节点数较小，DLPA算法时间耗费也就较小。而COPRAPC的时间复杂度为$ \mathrm{{\rm O}}\left(\right(m+n)/c) $，其中，$ c $为聚类系数，CDA-GM与COPRAPC的时间耗费相比于基线方法略高，但与其他4种算法相比，CDA-GM获得了较好的准确度和稳定性，这表明CDA-GM在保持一个接近线性时间复杂度的前提下，大幅提高了标签传播算法的社区检测能力。

算法划分的社区与原有社区的相似程度，也经常用于辅助评价社区检测结果。表 4为各算法在LFR1上获取的社区数量，其中，$ {N}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}} $为数据集中的原有网络数量。可以看出，CDA-GM能够获得较好的社区划分结果，与原有社区较为接近，而COPRA、COPRAPC在$ \mu =0.4 $时，已经无法检测社区。

2.5 真实世界网络实验结果分析

将5种算法分别应用到真实世界数据中，对比经过20次重复实验取得的平均值$ {Q}_{\mathrm{a}}^{\mathrm{E}} $以及标准差值$ {Q}_{\mathrm{s}}^{\mathrm{E}} $，如表 5、表 6所示，其中，最优值以粗体显示，COPRA、SLPA及DLPA算法调整参数取最优结果。

可以看出，CDA-GM在所用真实网络中获得的$ {Q}_{\mathrm{a}}^{E} $值优于对比算法。在较小规模网络中CDA-GM表现较好，且标准差也都保持在较小的范围内，这说明CDA-GM在小规模数据集上能够在保持准确性的前提下尽可能获取最优的社区划分。在大规模网络中，CDA-GM重叠模块度平均值、标准差值明显优于对比算法，这说明CDA-GM既能获得良好清晰的社区划分结果，又能保持算法的稳定性。

3 结束语

为提高社区检测的准确性和稳定性，本文提出一种基于节点引力与鱼记忆的社区检测算法CDA-GM。使用融入节点信息熵的k-shell排序策略，同时利用节点间的引力选择标签。在此基础上，引入鱼记忆的节点标签存储策略避免出现标签震荡。实验结果表明，该算法在LFR人工基准网络和真实世界网络中能获得较好且稳定的NMI值和社区模块度，检测性能优于COPRA、SLPA、DLPA和COPRAPC算法。在后续研究中，拟将本文算法结合时间参数应用到动态的社区检测中，进一步提高算法的实用性。