Community Detection Algorithm Based on Density Peak Clustering and Label Propagation
-
摘要: 社区发现的目标是发现复杂网络的结构、行为和组织形式。标签传播算法是一种快速有效的社区发现算法，然而在初始的标签传播算法中，节点的结构信息和特征信息没有得到充分利用，且存在标签传播过程不稳定的问题。针对上述问题，文章提出了一种基于改进的密度峰值聚类算法和标签传播算法的有向加权复杂网络社区发现算法(DPC-LPA)。该算法首先根据节点的结构和特征对其进行加权，充分利用了结构信息和特征信息；然后，采用改进的密度峰值聚类算法来寻找网络的社区中心，并据此构建初始社区，提高了社区划分的质量；其次，基于节点相似度和节点权重，合理确定标签传播的更新顺序，并通过衡量节点间标签传播的强度来完成标签传播，解决了标签传播算法不稳定的问题。最后，在CiteSeer、Cora、WebKB和SCHOLAT真实数据集上，将DPC-LPA算法与DCN、WCF-LPA、CLPE算法进行对比实验。实验结果证明了DPC-LPA算法的可行性和有效性：从模块度来看，利用DPC-LPA算法划分的社区具有更加显著的社区结构；从调整兰德系数来看，DPC-LPA算法的社区划分质量更稳定；从运行时间来看，DPC-LPA算法具有较高的效率。Abstract: The goal of community detection is to discover the structure, behavior and organization of complex networks. Label propagation algorithm is a fast and effective community detection algorithm. However, in the classic label propagation algorithm, the structural and feature information of the node is not fully utilized, and the label pro-pagation process is unstable. To address the above problems, a community detection algorithm DPC-LPA based on improved density peak clustering algorithm and label propagation algorithm in directed weighted complex network is proposed. The algorithm firstly weights the nodes according to their structure and features, which makes full use of the structural and feature information. Then it uses an improved density peak clustering algorithm to find the community center of the network and constructs the initial community accordingly, which improves the quality of community division. And then, based on node similarity and node weights, the update order of label propagation is reasonably determined, and the strength of label propagation between nodes is measured to complete label propagation, which solves the problem of unstable label propagation algorithm. Finally, on CiteSeer, Cora, WebKB, and SCHOLAT real-world datasets, the DPC-LPA algorithm is compared with DCN, WCF-LPA, and CLPE algorithms. The experimental results prove the feasibility and effectiveness of the DPC-LPA algorithm: in terms of modu-larity, the communities divided by the DPC-LPA algorithm have a more significant community structure; in terms of Adjusted Rand Index, the community division quality of the DPC-LPA algorithm is more stable; in terms of running time, the DPC-LPA algorithm has higher efficiency.
-
Keywords:
- community detection /
- label propagation /
- density peak /
- node weighting /
- complex networks
-
复杂网络是指具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络。从拓扑的角度而言，复杂网络中的社区是一组内部连接相对紧密、外部连接相对稀疏的节点[1]。从相似度的角度而言，同一社区中的节点更相似，不同社区中的节点之间则存在显著差异[2]。社区形成的连接关系称为社区结构[3]，社区结构清楚地显示了网络中社区之间的差异和联系，挖掘网络中的社区结构是网络科学中的一个基本问题[4]。社区发现是用来检测网络中的社区结构的方法，帮助人们正确识别网络中的社区、洞察网络的结构组织、掌握网络中节点之间的关系，同时还可以促进许多智能服务的发展，如挖掘社交网络信息进行趋势预测[5]和基于社区划分进行推荐[6], 是近年来研究的热点课题之一。
如今，复杂网络规模迅速增长，对社区发现算法速度的要求更高[7]。因此，有效的社区发现方法应具有更低的时间复杂度。标签传播算法是一种快速有效的社区发现算法，不仅在线性时间内运行，而且具有良好的社区划分性能[8-9]。初始的标签传播算法[9]的具体步骤如下：首先，为每一个节点初始化一个单独的标签；然后，以随机顺序更新节点的标签，令节点与其邻居节点中出现频率最高的标签一致，如果节点的所有邻居节点的标签出现的频率一致，则随机选择一个标签，这个步骤称为标签传播；最后，迭代标签传播步骤直至每个节点的标签不再变化，同一标签的节点归属于同一个社区，得到社区划分结果。然而，初始的标签传播算法存在下述3个问题：(1)标签初始化和标签传播过程是随机的；(2)每次迭代结果不稳定；(3)可能会出现所有节点归属于一个社区的情况。为解决以上问题，学者们提出了一系列扩展方法，主要研究内容有：(1)改进标签传播的初始化过程，不再在初始化阶段为每一个节点赋予一个独特的标签，而是为预先提取的特殊结构扩展而成的初始社区赋予初始标签。例如：预先提取种子节点[10-11]、边[12]、团[13]和基本模式[14]等特殊结构，随后通过纳入邻居节点对特殊结构进行拓展，形成了初始社区，再将属于同一初始社区的节点赋予相同的标签，从而完成标签初始化的过程，提高社区划分的速度和质量。(2)改进标签传播的节点顺序，不再在每次迭代中以随机的顺序处理节点，而是采用非随机的排序方法来提高社区划分的稳定性：先将节点划分为不同的节点组，例如核心节点和边界节点[15]、已分配和未分配的节点[16]等；再按照非随机的顺序进行标签传播。(3)在现实世界中，社区结构通常是以重叠的方式存在，因此，通过改进初始的标签传播算法的思想，使标签传播算法能够解决重叠社区发现问题，不再只允许一个节点属于一个社区，而是允许社区有交叉，一个节点可能属于多个社区。如应用标签传播算法的重叠社区发现算法COPRA[8]、SLPA[17]和DLPA[18]等。
社区发现是依据节点间关系，将关系紧密的节点划分为社区的方法；聚类是根据样本间的相似性将样本聚簇的方法。社区发现也被称为图聚类，部分学者将聚类算法应用在社区发现中，例如基于K-Means的社区发现算法[19]、基于谱聚类的社区发现算法[20]和基于密度聚类的社区发现算法[21]。初始的密度峰值聚类算法[22]是一种基于密度的聚类算法，该算法为数据中每个样本定义了局部密度ρ和相对距离δ，并根据ρ和δ自动选择聚类中心，具有较好的自适应性。由于初始的密度峰值算法只适用于传统的属性数据集，而复杂网络是一种拓扑图结构，因此，一些学者基于网络拓扑结构对密度峰值聚类算法进行改进，使其在社区发现中发挥更好的效果[23]。
基于密度峰值聚类算法良好的自适应性和标签传播算法较低的时间复杂度，部分学者将密度峰值聚类算法和标签传播算法结合应用于社区发现。如：2017年，ZHANG等[24]提出了结合节点权值紧性函数和标签传播算法的社区发现算法(WCF-LPA)，该算法是一种基于节点权重的标签传播策略，用于大规模复杂网络中的社区发现；2018年，DING等[25]提出了基于中心和邻居的社区发现算法(DCN)，该算法基于密度峰值聚类算法的思想，使用切比雪夫不等式自动选择社区中心，且不需要调整不同网络的参数；2020年，为了检测复杂网络，JIANG等[26]提出了基于中心节点的链路预测策略的社区发现算法(CLPE)，该算法首先使用基于检测中心节点的链路预测策略来增强网络的社区结构，然后使用社区扩展策略来检测网络中的所有社区。这些算法都保持了初始的标签传播算法的时间复杂度低的优点，但没有考虑真实网络中节点所具有的属性特征，因此不能提高真实复杂网络中社区划分的质量。
为解决上述问题，本文改进了初始的密度峰值聚类算法[22]和初始的标签传播算法[9]，提出了一种基于这2种改进算法的有向加权复杂网络社区发现算法(DPC-LPA)。该算法将结构信息和特征信息相结合，从而构造节点权重，节点权重大的节点将在标签初始化和标签传播过程中具有优先地位，以有效提高标签传播的准确性；改进了密度峰值聚类算法中局部密度的计算方法，以便更快地找到社区中心，提高标签初始化的效率；引入了节点相似度和节点权重，改进了标签传播过程，以提高标签传播算法的稳定性和可靠性。最后，分别在CiteSeer、Cora、WebKB和SCHOLAT真实数据集上，将DPC-LPA算法与WCF-LPA[24]、DCN[25]、CLPE[26]算法进行对比实验。
1. DPC-LPA算法
为解决初始的标签传播算法随机性较强和稳定性较差的问题，本文提出了一种在有向加权的复杂网络上基于密度峰值聚类算法和标签传播算法的社区发现算法(DPC-LPA)：首先，将节点的结构信息和特征信息进行量化，结合量化后的2种属性对节点进行加权，使得有影响力的节点和其他节点在权重上有显著的差距，为后续改进密度峰值聚类算法和标签传播算法进行数据预处理；其次，改进密度峰值聚类算法中的局部密度和相对距离的计算方法，再通过切比雪夫不等式快速得到社区中心，将与社区中心直接相连的节点赋予同一个初始标签，完成了标签初始化；最后，结合节点相似度和节点权重，改进了标签传播的顺序和概率，使得权重更高的节点更容易将自己的标签传播给其他节点，完成标签传播过程后即可得到社区划分结果。DPC-LPA算法的具体步骤如图 1所示。
1.1 数据预处理
ARAL和WALKER[27]提出：非常有影响力的节点不容易受到影响，这样的节点更容易在社区中成为中心，同时，有影响力的节点具有更强的传播标签的能力，但从其他节点接受标签的能力相对较弱。因此，本文通过量化节点的结构信息和特征信息，结合上述2种量化后的属性得到节点权重，并以此确定有影响力的节点。
对于节点的结构信息，一般认为与其他节点发生更多交互的节点更具有影响力。PageRank算法[28]是一种基于随机游走模型来探索网络中节点影响力的算法，其基本假设是，指向网络中节点的边越多，该节点就越重要。因此，本文使用PageRank算法来量化有向网络中节点的结构信息。节点i的PageRank值[28]定义如下：
PageRank(i)=(1−α)1N+α∑j→iPageRank(j)OutDegree(j), (1) 其中，N为网络中的节点数，OutDegree(j)为节点j的出度，节点j为指向节点i的节点，α∈[0, 1]为阻尼因子。依据前人实验经验[29]，本文设定α=0.85，以使算法的收敛速度最快。
对节点的特征信息进行量化需用文本表示方法，常见的文本表示方法有LDA模型[30]、Word2Vec算法[31]和TF-IDF算法[32]。由于实验数据集中节点的特征信息仅由专业性强且生僻字少的单个词语构成，LDA模型、Word2Vec算法和TF-IDF算法均可以取得良好的效果，但LDA模型需要指定主题数量，Word2Vec算法需要对模型进行训练，而TF-IDF算法仅需要计算TF-IDF值，因此，本文选用TF-IDF算法对节点的特征信息进行量化，以提高DPC-LPA算法的速度和稳健性。TF-IDF算法中使用的词频-逆文本频率TF-IDF(Term Frequency-Inverse Document Frequency)[32]可以评估一个单词在一份文本中的重要程度，其中：TF(Term Frequency)表示一个词语在目标文章中出现的频率，一个词语的TF大，表明这个词语是目标文章的关键词；IDF(Inverse Document Frequency) 是一个词语普遍重要性的度量，该词语在所有文章中出现的频率越低，词语的IDF越大，表明这个词语越独特。节点的特征w的TF-IDF的计算公式如下：
(TF−IDF)w=TFw∗IDFw 。 (2) 设S为节点的全部特征的集合，某节点的某一特征w的TF值的计算公式如下：
TFw=num(w)num(S), (3) 其中，num(w)为特征w在该节点的所有特征中出现的次数，num(S)为全部特征的个数。特征w的IDF的计算公式如下：
IDFw=lg|N||{j:tw∈dj}|+1, (4) 其中，|N|为节点总数，|{j: tw∈dj}|为包含特征w的节点总数。
节点i的特征信息量化为F(i)，计算公式如下：
F(i)=∑(TF−IDF)i,w|I|, (5) 其中，Σ (TF-IDF)i, w为节点i的所有特征w的TF-IDF值，|I|为节点i的特征数量。
结合量化后的节点的结构信息和特征信息，得到节点i的权重NW(i)：
NW(i)= PageRank (i)∗F(i)。 (6) 1.2 标签初始化
初始的标签传播算法在初始化过程中会随机为每个节点分配一个唯一的标签，这样的做法没有充分利用节点的结构信息和特征信息，忽略了节点之间的差异，降低了标签传播算法的效率。因此，本文充分利用节点的结构和特征中所包含的信息，对密度峰值聚类算法进行改进，以此来选择社区中心并构建初始社区，完成标签初始化。
在密度峰值聚类算法中，局部密度[22]是距离目标节点一定距离内的节点数量。复杂网络中节点的距离根据节点间的边进行定义，如果2个节点直接相连，则意味着2个节点之间存在位置关系。一个节点的邻居节点的数量可以反映该节点的结构信息，因此，可以使用节点的度和邻居节点的度来反映节点的局部密度，计算公式如下：
ρ=d(i)+∑j∈N(i)d(j), (7) 其中，d(i)为节点i的度。
如果只使用节点的度和邻居节点的度来计算目标节点的局部密度，则仅考虑了目标节点的结构信息而没有考虑其特征属性，因此，局部密度ρ的计算公式可改进为：
ρ=d(i)∗NW(i)+∑j∈N(i)d(j)∗NW(j), (8) 其中，NW(i)为节点i的权重。
如果直接使用邻居节点的局部密度来计算目标节点的局部密度，则一些节点可能因邻居节点权重较大而获得过多的密度，这将导致局部密度的区别性降低。然而，本文期望中心节点的局部密度与非中心节点的密度显著不同，以有助于准确选择社区中心。因此，引入邻居节点密度衰减系数ζi，令ζi与节点i对局部密度的贡献成比例，以避免权重较大的邻居节点对权重较小的节点的局部密度产生较大影响。从而，将式(8)改进为：
ρ=d(i)∗NW(i)+ζi∑j∈N(i)d(j)∗NW(j), (9) 其中，ζi=d(i)∗NW(i)d(i)∗NW(i)+∑j∈N(i)d(j)∗NW(j)。
在得到局部密度后，进行相对距离的计算。从目标节点到其他局部密度更大的节点的最短距离称为相对距离[22]。因此，首先需要确定如何计算节点之间的距离。在复杂网络中，普遍认为2个节点越相似，它们就越接近。Jaccard指数[33]通常用于描述这种相似性，节点vi和节点vj之间的Jaccard指数Sij的计算公式如下：
Sij=|τ(i)∩τ(j)||τ(i)∪τ(j)|, (10) 其中，τ(i)=N(i)∪vi为节点vi与其所有邻居节点的并集。
节点之间的距离随着节点之间相似性的增大而减小，节点vi和节点vj之间的距离dist(vi, vj)的计算公式定义如下：
dist(vi,vj)=1−Sij。 (11) 节点i的相对距离δi的计算公式[22]如下：
δi={maxNj(dist(vi,vj))(ρi=maxNkρk),maxNj:ρj>ρi(dist(vi,vj))(ρi≠maxNkρk), (12) 其中，N为节点i的邻居节点集合，j, k∈N。当节点i具有其所有邻居节点中最大的局部密度时，节点i的相对距离δi为节点i与距离节点i最远的节点j之间的距离；当节点i不具有其所有邻居节点中最大的局部密度时，节点i的相对距离为节点i与局部密度大于节点i且距离节点i最远的节点j之间的距离。
由式(9)、(12)可知，社区中心节点和其他节点的局部密度、相对距离存在显著差距，即社区中心通常具有非常大的局部密度ρi和相对距离δi。因此，为便于对不同节点的ρi和δi进行综合比较，密度峰值聚类算法[22]中设置了一个决策值γi (γi=ρi*δi)：若节点i具有网络的所有节点中较大的γi，则节点i是一个社区中心。同时，为了提高计算效率和精度，对ρi和δi进行最大最小归一化：
ρ∗i=ρi−ρminρmax−ρmin, (13) δ∗i=δi−δminδmax−δmin, (14) 其中，ρmin、ρmax分别为所有节点中最小的、最大的局部密度，δmin、δmax分别为所有节点中最小的、最大的相对距离。从而得到γi*：
γ∗i=ρ∗i∗δ∗i。 (15) 然而，中心节点与其他节点之间的γi*值的边界往往难以确定，DCN算法中使用切比雪夫不等式来解决这个问题。本文依据DCN算法中的方法来确定中心节点与非中心节点之间γi*值的边界，即满足以下关系的节点将被视为中心节点：
γ>E(γ∗i)+θ×σ(γ∗i), (16) 其中，E(γi*)、σ(γi*)分别为γi*的期望、标准差。参考DCN算法，在DPC-LPA算法中设置θ=2，通过不断计算并记录符合不等式(16)的节点为中心节点，从而自动识别所有社区中心。
识别社区中心后，需要将社区中心的标签信息传播到其他节点。通常情况下，社区中心的数量很少，而网络中标签信息太少会降低标签传输的效率，因此，社区中心的标签会被分配给其邻居节点。如果一个节点同时连接到多个社区中心或没有连接到社区中心，则无法获取任何标签。将社区中心的标签分配给相邻节点的步骤丰富了网络中的标签信息，提高了标签传播的效率。
1.3 标签传播
初始的标签传播算法通过不断在相邻节点中选择具有最大标签频率的标签来更新自身，如果每个候选标签具有相同的频率，则算法将随机选择一个标签来更新自身，直到标签收敛后，标签相同的节点归属同一社区，得到最终的社区划分结果。这样的标签传播过程具有很强的随机性，因此获得的社区划分结果不稳定。为了得到稳定的社区划分结果，本文对标签传播过程进行了改进。
由于在有向网络中，节点倾向于接受有影响力的节点的标签，而节点权重是衡量节点影响力的标准，因此，本文根据节点权重来排列节点的标签传播顺序。
确定了标签传播顺序后，对于将要更新标签的节点i，初始的标签传播算法会选择节点i的邻居节点中数量最多的标签，节点i的标签li为：
li=argmaxl∑j∈N(i)κ(lj,l), (17) 其中，κ(lj, l)∈{0，1}。若lj=l，则κ(lj, l)=1；若lj≠l，则κ(lj, l)=0。
然而，当每个候选标签的出现频率一致时，初始的标签传播算法将会随机选择一个标签，这导致了每一次运行的结果经常不一致，因此需要进一步考虑标签和节点之间的关系。所选标签的社区成员应与该节点具有更大的相似性，可以通过计算候选标签与节点之间的相似性Sij，将更相似的标签传播到节点上。此外，权重更大的节点具有更强的标签传播能力。节点i将会选择与其更相似且由更大权重的节点传播而来的标签，因此，本文将式(17)改进如下：
li=argmaxl∑i∈N(i)κ(lj,l)∗Sij∗NW(vj), (18) 其中，Sij为节点相似度，NW(vj)为节点权重。
2. 实验结果与分析
在几个大型真实复杂网络上，将DPC-LPA算法分别与结合节点权值紧性函数和标签传播算法的社区发现算法(WCF-LPA)、基于中心和邻居的社区发现算法(DCN)和基于中心节点的链路预测策略的社区发现算法(CLPE)进行了对比实验。其中，WCF-LPA算法是一种基于节点权重的标签传播算法，其先通过网络拓扑信息找到核心节点，再根据核心节点集之间的节点和节点度的相似度对网络中的节点赋予权重，最后通过计算节点及其邻居社区之间的权值紧性函数来更新标签并完成社区划分；DCN算法采用密度峰值聚类算法的思想检测社区中心，使用切比雪夫不等式自动选择社区中心，最后通过标签传播算法来完成社区划分；CLPE算法是一种基于链路预测的社区发现算法，使用密度峰值聚类算法选择社区中心，通过链路预测来改变中心节点和相邻节点之间的连通性，中心节点的标签以与标签传播类似的方式分布到其他节点，将相同标签的节点归属于同一社区，从而完成社区划分。
2.1 数据集
实验中使用的数据集为CiteSeer[34]、Cora[35]、WebKB[36]和SCHOLAT真实数据集，其中WebKB真实数据集包括Cornell、Texas、Washington、Wisconsin数据集，SCHOLAT真实数据集包括SCHOLAT Social Network[37]和Anomaly Detection on Attributed Network[38] 2个数据集。4个真实网络的网络特征见表 1。
表 1 4个真实网络的网络特征Table 1. Network characteristics of four real networks数据集 节点/个 边/条 特征/个 CiteSeer 3 327 4 732 3 703 Cora 2 708 5 429 1 433 WebKB Cornell 183 295 1 703 Texas 183 309 1 703 Washington 252 446 1 703 Wisconsin 251 499 1 703 SCHOLAT SCHOLATSocialNetwork 16 007 202 248 16 007 Anomaly Detection on Attributed Network 2 022 2 500 500 2.2 评估指标
采用模块度[1]和调整兰德指数(ARI)[39]2个度量指标来评估算法的性能。
模块度通常用于评估复杂社交网络分区是否具有显著的社区结构，其定义如下：
Q=12m∑ij(Aij−d(i)d(j)2m)κ(li,lj), (19) 其中，Q为模块度，m为边的数目，d(i)为节点vi的度，Aij为G(V, E)的邻接矩阵中的元素；li、lj分别为节点vi、vj标记的社区标签，κ(li, lj)∈{0, 1}。若li=lj，则κ(li, lj)=1，即节点vi和节点vj在同一社区中；若li≠lj，则κ(li, lj)=0，即节点vi和节点vj不在同一社区中。模块度越大，表示社区划分质量越高。
ARI通常用于描述实验社区划分结果和真实社区划分结果之间的差异。假设真实网络中存在R个社区，表示为U={U1, U2, …, UR}。实验结果中网络被划分为P个社区，表示为V={V1, V2, …, VP}。ARI的计算公式如下：
ARI =2(P00P11−P01P10)(P00+P01)(P01+P11)+(P00+P10)(P10+P11), (20) 其中，P00表示在U和V中不属于同一社区的节点对数量；P11表示在U与V中属于同一小区的节点对数量；P10表示在U中不属于相同社区，但在V中属于相同社区的节点对数量；P01表示在V中不属于相同社区，但在U中属于相同社区的节点对数量。
2.3 对比实验
2.3.1 社区划分质量对比
由4个算法对不同网络进行社区发现的模块度(表 2)及其可视化实验结果(图 2)可知：(1)在CiteSeer和Texas数据集上，WCF-LPA算法的模块度略高于DPC-LPA算法的，但DPC-LPA算法在Cora、Cornell、Washington、Wisconsin数据集上的模块度分别比WCF-LPA算法的高19.8%、17.8%、11.2%、10.8%，说明DPC-LPA算法的社区划分结果具有更显著的社区结构；(2)在SCHOLAT真实数据集上，DPC-LPA算法的模块度明显高于其他3种社区发现方法的，主要原因为：SCHOLAT真实数据集提供了更多有意义的节点特征信息，而DPC-LPA算法充分利用了节点的拓扑信息和特征信息，更加善于挖掘网络的社区中心，可得到更为显著的社区结构，尤其是在大规模的特征丰富的真实网络中可以得到较好的社区划分结果。综上可知：在检测社区结构方面，DPC-LPA算法优于DCN、WCF-LPA、CLPE算法，在大多数实验数据集上的社区划分质量更高。
表 2 4个算法在不同真实数据集上的模块度Table 2. The Q values of four algorithms on different real-world datasets算法 CiteSeer Cora WebKB SCHOLAT Cornell Texas Washington Wisconsin SCHOLAT Social Network Anomaly Detection on Attributed Network DCN 0.341 6 0.137 6 0.020 7 0.013 6 0.027 2 0.032 1 0.072 9 0.054 9 WCF-LPA 0.706 7 0.615 5 0.500 6 0.422 7 0.344 8 0.406 9 0.277 2 0.057 1 CLPE 0.260 5 0.325 8 0.203 9 0.072 4 0.162 1 0.155 3 0.462 3 0.210 2 DPC-LPA 0.676 8 0.737 6 0.589 9 0.413 6 0.383 6 0.452 6 0.599 9 0.350 6 ![]()
图 2 4个算法在各数据集上的模块度实验结果可视化Figure 2. The visualization of Q values of four algorithms on the datasets由各算法对不同网络进行社区发现的调整兰德系数(表 3)及其可视化实验结果(图 3)可知：DCN、CLPE算法在Washington、Cora、Cornell、Wisconsin数据集上的ARI值略高于DPC-LPA算法的，但DCN、CLPE算法的ARI值在不同数据集上的波动较大，而DPC-LPA算法在不同数据集上的ARI值较稳定，说明相较于DCN、WCF-LPA、CLPE算法，DPC-LPA算法更为稳定地划分了有效社区。
表 3 4个算法在不同真实数据集上的调整兰德系数Table 3. The ARI values of four algorithms on different real-world datasets算法 CiteSeer Cora WebKB SCHOLAT Cornell Texas Washington Wisconsin SCHOLAT Social Network Anomaly Detection on Attributed Network DCN 0.026 9 0.082 0 0.169 6 0.133 4 0.104 6 0.165 0 — — WCF-LPA 0.083 9 0.070 4 0.111 9 0.115 9 0.068 4 0.192 6 — — CLPE 0.138 5 0.159 1 0.155 9 0.092 5 0.051 8 0.185 2 — — DPC-LPA 0.154 1 0.137 3 0.154 1 0.166 4 0.079 5 0.184 5 — — 注：在SCHOLAT真实数据集中没有给定划分好的社区，无法计算ARI。“—”表示数值不存在。 ![]()
图 3 4个算法在各数据集上的调整兰德系数实验结果可视化Figure 3. The visualization of ARI values of four algorithms on the datasets2.3.2 算法效率对比
按照数据集中节点和边的数量，将CiteSeer、Cora、WebKB和SCHOLAT真实数据集划分为小规模数据集、中规模数据集和大规模数据集。其中，节点和边的数量在500以内的数据集为小规模数据集，包括WebKB中的Cornell、Texas、Washington、Wisconsin数据集；节点和边的数量在2 000~4 000之间的数据集为中规模数据集，包括CiteSeer、Cora、Anomaly Detection on Attributed Network数据集，节点和边的数量均在10 000以上的数据集为大规模数据集，即SCHOLAT Social Network数据集。
在不同规模的数据集上测试了4个算法的运行时间，由实验结果(表 4，图 4至图 6)可知：(1)DPC-LPA算法的运行时间远低于CLPE算法的，这是因为CLPE算法中通过链接预测来补全网络结构的步骤需要大量的计算量。(2)DPC-LPA算法的运行时间多于DCN、WCF-LPA算法的，究其原因为：①DPC-LPA算法通过网络的结构信息和特征信息传播标签，而DCN、WCF-LPA算法仅通过网络的结构信息传播标签，运行速度更快；②DPC-LPA算法新增了计算节点权重的步骤，相应增加了运行时间。(3)在中规模数据集中，随着数据集节点、边和特征数量的增加，DPC-LPA算法的运行时间与相应数据集上运行时间最少的算法的差距有所缩小。如DPC-LPA算法在节点、边和特征数量较少的Anomaly Detection on Attributed Network数据集上的运行时间与在该数据集上运行时间最短的算法(WCF-LPA算法)的差距为1 146 ms，而在节点、边和特征数量较多的CiteSeer数据集上的运行时间与在该数据集上运行时间最短的算法(DCN算法)的差距为957 ms，差距缩小了189 ms。究其原因为：DPC-LPA算法不需要多次迭代，降低了算法的计算消耗，从而提高了算法在中规模数据集上的效率。
表 4 4个算法在不同真实数据集上的运行时间Table 4. The runtimes of four algorithms on different real-world datasetsms 算法 CiteSeer Cora WebKB SCHOLAT Cornell Texas Washington Wisconsin SCHOLAT Social Network Anomaly Detection on Attributed Network DCN 127 116 9 6 9 7 6 652 141 WCF-LPA 296 184 11 6 10 16 4 583 135 CLPE 4 666 2 067 34 37 37 46 337 956 2 245 DPC-LPA 1 084 1 008 25 27 26 38 173 558 1 281 ![]()
图 4 4个算法在各小规模数据集上的运行时间结果可视化Figure 4. The visualization of runtimes of four algorithms on the small scale datasets![]()
图 5 4个算法在各中规模数据集上的运行时间结果可视化Figure 5. The visualization of runtimes of four algorithms on the middle scale datasets![]()
图 6 4个算法在大规模数据集(SCHOLAT Social Network)上的运行时间结果可视化Figure 6. The visualization of runtimes of four algorithms on the large scale dataset(SCHOLAT Social Network)综上可知，DPC-LPA算法的运行时间虽然略多于DCN、WCF-LPA算法的运行时间，但远低于CLPE算法的运行时间，可见DPC-LPA算法的运行时间是在可接受范围之内的。
3. 小结
为了克服初始的标签传播算法的随机性和不稳定性，本文提出了一种在复杂有向加权网络上基于的密度峰值聚类和标签传播的社区发现算法(DPC-LPA)。该算法首先根据网络中节点的结构和特征对节点进行加权；然后, 通过改进密度峰值聚类算法中的局部密度和相对距离算法，提高了社区中心节点和其他节点的区分能力，更好地找到社区中心；最后, 依据节点的全局影响力大小来衡量用户间信息传播的强弱，并定义标签的传播概率，通过标签传播来完成社区划分的任务。对比实验表明DPC-LPA算法是可行有效的：DPC-LPA算法提高了社区划分准确性；在多数真实数据集上，DPC-LPA算法具有较好且较为稳定的社区划分结果，尤其是在特征丰富的大型复杂网络中，能够有效检测网络中存在的社区结构；DPC-LPA算法的运行时间在可接受范围内。
然而，DPC-LPA算法仍具有局限性，如该算法中仍然存在会影响性能的参数问题，如何进一步提高寻找社区中心的性能和降低参数对性能的影响还需要进一步的研究。另外，在真实世界的网络中，节点与节点之间的联系紧密程度也影响到社区中心的选择和社区划分的质量。因此，在未来的研究中，可考虑对边进行加权，改进标签初始化和标签传播过程，以提升社区划分的质量。
-
![]()
图 2 4个算法在各数据集上的模块度实验结果可视化
Figure 2. The visualization of Q values of four algorithms on the datasets
![]()
图 3 4个算法在各数据集上的调整兰德系数实验结果可视化
Figure 3. The visualization of ARI values of four algorithms on the datasets
![]()
图 4 4个算法在各小规模数据集上的运行时间结果可视化
Figure 4. The visualization of runtimes of four algorithms on the small scale datasets
![]()
图 5 4个算法在各中规模数据集上的运行时间结果可视化
Figure 5. The visualization of runtimes of four algorithms on the middle scale datasets
![]()
图 6 4个算法在大规模数据集(SCHOLAT Social Network)上的运行时间结果可视化
Figure 6. The visualization of runtimes of four algorithms on the large scale dataset(SCHOLAT Social Network)
表 1 4个真实网络的网络特征
Table 1 Network characteristics of four real networks
数据集 节点/个 边/条 特征/个 CiteSeer 3 327 4 732 3 703 Cora 2 708 5 429 1 433 WebKB Cornell 183 295 1 703 Texas 183 309 1 703 Washington 252 446 1 703 Wisconsin 251 499 1 703 SCHOLAT SCHOLATSocialNetwork 16 007 202 248 16 007 Anomaly Detection on Attributed Network 2 022 2 500 500 
下载: 导出CSV
表 2 4个算法在不同真实数据集上的模块度
Table 2 The Q values of four algorithms on different real-world datasets
算法 CiteSeer Cora WebKB SCHOLAT Cornell Texas Washington Wisconsin SCHOLAT Social Network Anomaly Detection on Attributed Network DCN 0.341 6 0.137 6 0.020 7 0.013 6 0.027 2 0.032 1 0.072 9 0.054 9 WCF-LPA 0.706 7 0.615 5 0.500 6 0.422 7 0.344 8 0.406 9 0.277 2 0.057 1 CLPE 0.260 5 0.325 8 0.203 9 0.072 4 0.162 1 0.155 3 0.462 3 0.210 2 DPC-LPA 0.676 8 0.737 6 0.589 9 0.413 6 0.383 6 0.452 6 0.599 9 0.350 6
下载: 导出CSV
表 3 4个算法在不同真实数据集上的调整兰德系数
Table 3 The ARI values of four algorithms on different real-world datasets
算法 CiteSeer Cora WebKB SCHOLAT Cornell Texas Washington Wisconsin SCHOLAT Social Network Anomaly Detection on Attributed Network DCN 0.026 9 0.082 0 0.169 6 0.133 4 0.104 6 0.165 0 — — WCF-LPA 0.083 9 0.070 4 0.111 9 0.115 9 0.068 4 0.192 6 — — CLPE 0.138 5 0.159 1 0.155 9 0.092 5 0.051 8 0.185 2 — — DPC-LPA 0.154 1 0.137 3 0.154 1 0.166 4 0.079 5 0.184 5 — — 注：在SCHOLAT真实数据集中没有给定划分好的社区，无法计算ARI。“—”表示数值不存在。
下载: 导出CSV
表 4 4个算法在不同真实数据集上的运行时间
Table 4 The runtimes of four algorithms on different real-world datasets
ms 算法 CiteSeer Cora WebKB SCHOLAT Cornell Texas Washington Wisconsin SCHOLAT Social Network Anomaly Detection on Attributed Network DCN 127 116 9 6 9 7 6 652 141 WCF-LPA 296 184 11 6 10 16 4 583 135 CLPE 4 666 2 067 34 37 37 46 337 956 2 245 DPC-LPA 1 084 1 008 25 27 26 38 173 558 1 281
下载: 导出CSV
-
[1] NEWMAN M, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113/1-16.
[2] FENG Y F, CHEN H M, LI T R, et al. A novel community detection method based on whale optimization algorithm with evolutionary population[J]. Applied Intelligence, 2020, 50(2): 2503-2522.
[3] GUO K, HE L, CHEN Y Z, et al. A local community detection algorithm based on internal force between nodes[J]. Applied Intelligence, 2020, 50(2): 328-340. doi: 10.1007/s10489-019-01541-1
[4] HUANG X, CHENG H, YU J X. Dense community detection in multi-valued attributed networks[J]. Information Sciences, 2015, 314: 77-99. doi: 10.1016/j.ins.2015.03.075
[5] LI H J, ZHAN B, LI A, et al. Fast and accurate mining the community structure: integrating center locating and membership optimization[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(9): 2349-2362.
[6] 贺超波, 沈玉利, 余建辉, 等. 基于学术社区的科技论文推荐方法[J]. 华南师范大学学报(自然科学版), 2012, 44(3): 55-58. doi: 10.6054/j.jscnun.2012.06.012 HE C B, SHEN Y L, YU J H, et al. Method for scientific paper recommendation based on academic community[J]. Journal of South China Normal University (Natural Science Edition), 2012, 44(3): 55-58. doi: 10.6054/j.jscnun.2012.06.012
[7] TANG Z K, TANG Y, LI C Y, et al. A fast local community detection algorithm in complex networks[J]. World Wide Web, 2021(6): 1929-1955.
[8] GREGORY S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2009, 12(10): 2011-2024.
[9] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3): 036106/1-11.
[10] SHANG R H, ZHANG W T, JIAO L C. Circularly searching core nodes based label propagation algorithm for community detection[J]. International Journal of Pattern Reco- gnition and Artificial Intelligence, 2016, 30(8): 1659024/1-22.
[11] LIU S C, ZHU F X, LIU H J, et al. A core leader based label propagation algorithm for community detection[J]. China Communications, 2016, 13(12): 97-106. doi: 10.1109/CC.2016.7897535
[12] LIU W, JIANG X P, PELLEGRINI M, et al. Discovering communities in complex networks by edge label propagation[J]. Scientific Reports, 2016, 6(1): 1-10. doi: 10.1038/s41598-016-0001-8
[13] LI C Y, TANG Y, TANG Z K, et al. Motif-based embedding label propagation algorithm for community detection[J]. International Journal of Intelligent Systems, 2022, 37(3): 1880-1902. doi: 10.1002/int.22759
[14] TANG Z K, LI C Y, TANG Y. An efficient method based on label propagation for overlapping community detection[C]//Proceedings of 2021 IEEE 24th International Conference on Computer Supported Cooperative Work in Design. New York: IEEE, 2021: 168-173.
[15] GUI Q, DENG R, XUE P F, et al. A community discovery algorithm based on boundary nodes and label propagation[J]. Pattern Recognition Letters, 2018, 109: 103-109. doi: 10.1016/j.patrec.2017.12.018
[16] ZHOU K, MARTIN A, PAN Q, et al. SELP: Semi-supervised evidential label propagation algorithm for graph data clustering[J]. International Journal of Approximate Reasoning, 2018, 92: 139-154. doi: 10.1016/j.ijar.2017.09.008
[17] XIE J, SZYMANSKI B K, LIU X. SLPA: uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//Proceedings of the 2011 IEEE 11th International Conference on Data Mining Workshops. Piscataway: IEEE, 2011: 344-349.
[18] SUN H L, HUANG J B, TIAN Y Q, et al. Detecting overlapping communities in networks via dominant label propa-gation[J]. Chinese Physics B, 2015, 24(1): 555-563.
[19] LEI Y, ZHOU Y, SHI J. Overlapping communities detection of social network based on hybrid C-means clustering algorithm[J]. Sustainable Cities and Society, 2019, 47: 101436/1-8.
[20] 张晓琴, 安晓丹, 曹付元. 基于谱聚类的二分网络社区发现算法[J]. 计算机科学, 2019, 46(4): 216-221. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201904034.htm ZHANG X Q, AN X D, CAO F Y. Detecting community from bipartite network based on spectral clustering[J]. Computer Science, 2019, 46(4): 216-221. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201904034.htm
[21] 郭昆, 彭胜波, 陈羽中, 等. 基于密度聚类的增量动态社区发现算法[J]. 模式识别与人工智能, 2018, 31(11): 965-978. doi: 10.16451/j.cnki.issn1003-6059.201811001 GUO K, PENG S B, CHEN Y Z, et al. Incremental dyanamic community detection algorithm based on density clustering[J]. Pattern Recognition and Aritificial Intelligence, 2018, 31(11): 965-978. doi: 10.16451/j.cnki.issn1003-6059.201811001
[22] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344: 1492-1496. doi: 10.1126/science.1242072
[23] BAI X Y, YANG P L, SHI X H. An overlapping community detection algorithm based on density peaks[J]. Neurocomputing, 2017, 226: 7-15. doi: 10.1016/j.neucom.2016.11.019
[24] ZHANG W T, ZHANG R, SHANG R H, et al. Weighted compactness function based label propagation algorithm for community detection[J]. Physica A: Statistical Mechanics and its Applications, 2018, 492: 767-780. doi: 10.1016/j.physa.2017.11.006
[25] DING J J, HE X X, YUAN J Q, et al. Community detection by propagating the label of center[J]. Physica A: Statistical Mechanics and its Applications, 2018, 503: 675-686. doi: 10.1016/j.physa.2018.02.174
[26] JIANG H, LIU Z J, LIU C L, et al. Community detection in complex networks with an ambiguous structure using central node based link prediction[J]. Knowledge-Based Systems, 2020, 195(12): 105626/1-13.
[27] ARAL S, WALKER D. Identifying influential and susceptible members of social networks[J]. Science, 2012, 337: 337-341. doi: 10.1126/science.1215842
[28] AVRACHENKOV K, HOFSTAD R V D, SOKOL M. Personalized PageRank with node-dependent restart[C]//Algorithms and Models for the Web Graph. Cham: Sprin-ger, 2014: 23-33.
[29] PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the web[R]. [S. l. : s. n.], 1999.
[30] ZHANG X C, YU L F, ZHANG Y H. Multi-feature fusion for short text similarity calculation base on LDA[J]. Computer Science, 2018, 45(9): 266-270.
[31] LUO J, WANG Q L, LI Y. Word clustering based on word2vec and semantic similarity[C]//Proceedings of 2014 33th IEEE Control Conference. Nanjing: IEEE, 2014: 517-521.
[32] 黄承慧, 印鉴, 侯昉. 一种结合词项语义信息和TF-IDF方法的文本相似度量方法[J]. 计算机学报, 2011, 34(5): 856-864. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201105010.htm HUANG C H, YIN J, HOU F. A text similarity measurement combining word semantic information with TF-IDF method[J]. Chinese Journal of Computers, 2011, 34(5): 856-864. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201105010.htm
[33] CHENG Q, ZHONG L, HUANG J C, et al. Community detection in hypernetwork via Density-Ordered Tree partition[J]. Applied Mathematics & Computation, 2016, 276: 384-393.
[34] GILES C L, BOLLACKER K D, LAWRENCE S. CiteSeer: An automatic citation indexing system[C]//Proceedings of the Third ACM Conference on Digital Libraries. New York: ACM, 1998: 89-98.
[35] MCCALLUM A K, NIGAM K, RENNIE J, et al. Automating the construction of internet portals with machine learning[J]. Information Retrieval, 2000, 3: 127-163. doi: 10.1023/A:1009953814988
[36] CRAVEN M, DIPASQUO D, FREITAG D, et al. Learning to construct knowledge bases from the World Wide Web[J]. Artificial Intelligence, 2000, 118(1/2): 69-113.
[37] XU Q, QIU L J, LIN R H, et al. An improved community detection algorithm via fusing topology and attribute information[C]//Proceedings of 2021 IEEE 24th International Conference on Computer Supported Cooperative Work in Design. New York: IEEE, 2021: 1069-1074.
[38] HUANG L, ZHU Y, GAO Y F, et al. Hybrid-order ano- maly detection on attributed networks[J/OL]. IEEE Transactions on Knowledge and Data Engineering, (2021-10-06)[2022-09-23]. https://ieeexplore.ieee.org/document/9560054.
[39] HUBERT L, ARABIE P. Comparing partitions[J]. Journal of Classification, 1985, 2(1): 193-218. doi: 10.1007/BF01908075
-
期刊类型引用(0)
其他类型引用(2)
计量
- 文章访问数: 186
- HTML全文浏览量: 65
- PDF下载量: 120
- 被引次数: 2
