基于边传播概率的重叠社区发现算法

王刚

摘要：随着互联网技术的高速发展，大量的web社区网站和社交软件如雨后春笋般涌现出来并逐渐地被人们接受。例如根据博客、微博等平台中的海量用户群体，可以构建了一个节点数目庞大、节点连接关系复杂的社交网络。发现这类社交网络中的社区结构正是如今发展迅速的网络数据挖掘研究领域的热点之一。社区划分的核心思想是将具有相似度高、连接紧凑的节点聚集到同一个社区中，从而形成若干个社区组成的网络结构[1]。该文针对传统的重叠标签传播算法COPRA，提出了一种基于边传播概率的标签传播算法（Edge Propagation Probability-COPRA ）。实验证明，算法改进使得社区划分的结果更加稳定和准确。

关键词：社区发现；标签传播；边传播概率；社交网络；COPRA

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）21-0057-03

1 引言

随着互联网技术与智能硬件技术的高速发展，越来越多的人在社交平台中分享生活、结交朋友以及获取信息，构建了一个节点数目庞大、连接关系复杂的社交网络。因此挖掘社交网络中的社区结构具有很大的现实意义，通过挖掘用户的社区属性，了解用户的兴趣爱好和需求，可向用户群体有针对性地精准推送信息，从而使社交网络增值[2]。社区发现是挖掘社交网络中节点关系的重要分支，其中对重叠社区结构的研究更是社区发现的重点和难点。

由于目前社交网络的节点规模越来越庞大，大部分传统的社区发现算法不能快速地对这类网络进行社区挖掘。其次，现实网络中社区之间很有可能存在着重叠部分[3]。基于这两点，本文选取時间复杂度近似线性的重叠标签传播算法COPRA作为研究的出发点。在2009年，Gregory在LPA算法的基础上进行扩展，提出了用于发现重叠社区结构的COPRA算法（Community Overlap PRopagation Algorithm） [4]。传统的标签传播算法约束了每个节点只能具有唯一的一个标签，为了能够运用标签传播策略挖掘重叠社区结构，Gregory在COPRA算法中引入了归属系数（Belonging Coefficient）的概念，用一组[（c，b）]构成的集合来表示每个节点的社区归属情况，[c]表示社区标识，[b]表示节点[x]隶属于社区[c]的归属系数，[b]的取值范围是[[0，1]]。

COPRA算法的执行时间近似为线性，具有较高的执行效率，能够处理大规模网络的社区发现问题。然而，COPRA算法在迭代更新节点标签的过程中存在不确定性和随机性，导致其结果准确性和稳定性常常不能达到预期。

（1）标签更新阶段，随机对节点进行排序，无考虑节点的重要性对节点更新的影响，可能导致重要性较小的节点反过来影响一些重要性较大的节点，使得传播过程产生“逆流”现象，虽然可以在之后的迭代中修正，但是使得算法迭代次数无意义的增加。

（2）标签选择阶段，在节点的标签更新过程中，当遇到候选标签集合中标签的归属系数都小于阈值且存在多个标签的归属系数相等的情况时，会采用随机策略选择其中一个标签作为该节点的标签，而这也正是标签传播算法不稳定的因素之一。

考虑到这两个问题，本文改进了重叠社区发现算法COPRA，提出了一种基于边传播概率的改进标签传播算法EPP-COPRA。首先，提出了一个新的节点重要性度量方法——熵中心，以该度量标准构造节点更新顺序，避免不必要的标签更新和“逆流”现象；其次，根据节点之间的标签接收能力，结合节点重要性提出了一个边影响度量方法；最后，引入节点之间的相似度提出边传播概率，通过边传播概率降低标签选择的随机性，从而提高算法的准确性、加快算法的收敛。

2 基于边传播概率的标签传播算法EPP-COPRA

2.1 节点重要性度量

节点度作为传统的节点重要性度量方法之一，其基本思想是以邻居节点的数量来衡量节点的重要性。节点的度越大，表明节点重要性越强，即说明该节点的传播能力越强。然而，仅仅通过相邻节点的数量来评价节点的传播能力是有所欠缺的。本文认为，在评价节点的传播能力时，应该考虑到节点的邻居节点的度，即如果节点的邻居同样具有较大的度，则该节点的传播能力较强。考虑到这一点，本文假设一个节点的邻居的度数都很大且均匀，那么节点具有较高的传播能力。因此本文基于信息论的基本概念提出了一种基于拓扑信息来检测网络中节点中心性的度量——熵中心（Entropy Centrality）。

在公式（7）中，网络中节点[vk]最大二阶邻居节点的总度数为[maxvk∈V（d2k）]。因此，依据熵中心由大到小地排序节点更新顺序[US]（Update Sequence），能够极大地减少算法不必要的标签更新操作，且避免标签“逆流”的现象。

2.2 边影响度量

标签传播过程中，若节点之间有连边，则可以直接接受对方标签的影响。然而，在现实网络中节点之间的影响并不是如此简单，每个节点都存在着传播标签和接受标签两种能力。一般情况下，我们认为影响力较大的节点具有的标签传播能力也相应的较强。Aral等人[5]的研究表明影响力大的节点不容易接受影响。因此本文提出了边影响的概念，在网络[G]中，节点[vj]对节点[vi]的影响度量（Influence Measure）的计算公式（8）为：

2.4 算法的传播过程

预先设定参数[k]，参数[k]表示网络中每个节点能够隶属的最大社区数目。算法的执行过程如下：

1）标签初始化。初始化网络中每个节点[x]，将节点的[id]设置为节点的社区标识[c]，即[b0（c，x）=1]。同时设置迭代次数[t=1]。

之后删除集合中系数小于[1k]的社区标识；若所有的社区标识[c]的归属系数都小[1k]，则保留集合中归属系数最大的社区标识[c]。更新完成后，再次归一化归属系数集合。

3）判断迭代终止条件。若连续两次迭代结果中每个社区标识对应的节点数目不在变化，则算法终止迭代；否则[t=t+1]，进入下一轮迭代，重复步骤3）的操作。

4）算法终止，输出结果。遍历所有节点的社区标识，将含有相同社区标识[c]的节点归类到社区[c]，由于存在部分较小社区是较大社区的子集，因此对社区做去重、合并处理。

3 算法改进性能比较

3.1 社区结构评价指标

其中，[N]为网络中节点的总数，[CA]、[CB]分别为社区划分结果[A]、[B]中社区的数目，[M]为一个混淆矩阵，矩阵的行对应着划分结果[A]中的社区，列对应着结果[B]中的社区。在矩阵中，[Cij]元素表示为即属于划分结果[A]中社区[i]又属于划分结果[B]中社区[j]的节点的数目。[Ci]为第[i]行元素的和，[Ci]为第[j]列元素的和。标准互信息的值反映了两个社区划分结果的相似程度，取值范围是[0，1]。NMI的值越大，划分结果[A]和划分结果[B]的结构越相似。所以，标准互信息体现了算法的稳定性，实验使用标准互信息来对比衡量算法的稳定性。

3.2 算法比较

根据文献[7]可知此规模的网络的归属社区[k]值选取在6-10是比较稳定的、较好的值。本文实验中，EPP-COPRA与COPRA算法的值选取一样[k]=8，进行算法比较。本文使用LFR算法根据社区的大小和边密度产生四个不同类型的中等规模的网络。四种网絡分别为：A：稀疏网络小社区；B：稠密网络大社区。

如图1所示，本文提出的算法EPP-COPRA在混合参数[μ]为不同值时，得到的NMI值都要比基础算法COPRA优良，NMI值平均高出0.2。而在[μ]<0.3时，与CFinder算法不相上下，而在[μ]>0.3时，EPP-COPRA算法比CFinder算法有显著的提高。与LFM算法相比较，在[μ]>0.3时，EPP-COPRA算法得到的划分结果稍微好些，而在[μ]<0.3和[μ]>0.7时，EPP-COPRA算法得到的划分结果要好很多。综上，在稀疏小社区的网络中，本文提出的算法EPP-COPRA比其他算法整体上有明显提高。

在稠密网络大社区上运行各个算法后所得结果如图2所示。算法EPP-COPRA与算法COPRA在，[μ]<0.4时，效果基本相同，几乎没什么提高，但是在[μ]>0.4时EPP-COPRA下降的会慢些，效果要好40%多，具有一定的优势。CFinder算法在此网络中社区划分效果不佳，而LFM算法表现优良。

综合四个不同参数的LFR网络中结果来看，本文能够得出以下结论：EPP-COPRA算法在稠密网络小社区中效果好，在不同[μ]值下，结果表现很稳定，波动不大，与其他算法相比，性能表现良好；EPP-COPRA算法与基础算法COPRA比较，有很明显的提升，且综合来看，明显优于其他三个算法。

4 结束语

本文针对传统的重叠社区发现算法COPRA的不足，提出了一种基于边传播概率的改进标签传播算法EPP-COPRA。本文以熵中心作为节点重要性度量，并排序节点的更新顺序；结合边影响度量与节点相似性计算边传播概率。通过以上改进，有效地避免标签传播过程中不必要的标签更新、“逆流”现象以及标签传播选择阶段的随机性，极大地提升了算法的准确性和稳定性。

参考文献：

[1] 郭世泽， 陆哲明. 复杂网络基础理论[M]. 北京：科学出版社，2012：25-27.

[2] Nieto S. The light in their eyes： Creating multicultural learning communities[M]. New York： Teachers College Press. 2015.

[3] 汪小帆， 李翔，陈关荣. 复杂网络理论及其应用[M]. 北京：清华大学出版社， 2006.

[4] Gregory S. Finding overlapping communities in networks by label propagatio[J]. New Journal of Physics， 2010， 12（10）： 103018.

[5] Aral S， Walker D. Identifying influential and susceptible members of social networks[J]. Science. 2012， 337（6092）：337.

[6] Danon L， Diazguilera A， Duch J， et al. Comparing community structure identification[J]. Journal of Statistical Mechanics Theory & Experiment. 2005， 2005（09）：09008.

[7] Gregory S. Finding overlapping communities in networks by label propagatio[J]. New Journal of Physics， 2010， 12（10）： 103018.

【通联编辑：代影】