基于标签传播的重叠社区发现算法

吴 春 国， 李 艳 振， 李 瑛， 高 瑞， 时 小 虎*

(1.吉林大学 符号计算与知识工程教育部重点实验室， 吉林 长春 130012；2.吉林大学 计算机科学与技术学院， 吉林 长春 130012；3.吉林大学珠海学院 计算机学院， 广东 珠海 519041 )

0 引 言

现实世界中的许多问题都可以简化为复杂网络进行研究.因此，越来越多的研究者热衷于研究复杂网络，挖掘其隐藏价值.复杂网络拥有很多特性，如小世界性(small world)[1]、无标度性(scale-free)[2]和高聚集特性等.此外，复杂网络还呈现出明显的社区结构[3-4].社区结构也可称作网络簇结构.在社区结构中，同一个社区内边数很多，节点之间连接稠密，而跨社区相连的边相对比较稀疏.那些具有相似功能或属性的节点组成相同的社区，而不同的社区相互连接构成完整的复杂网络.相对于整个系统，社区就像人体结构中的一个器官或者组织，为了更好地解释和了解复杂系统功能，需要对社区的结构进行分析和研究.自从Girvan等[3]提出了社区发现的概念以来，复杂网络社区发现的研究成果不断涌现，主要可以分为谱方法、模块度优化方法、层次聚类方法和边预测方法等[5].

在实际生活中，复杂网络中的节点可以同时存在于多个社区中，因此这些社区之间会有重叠部分.在社交网络中，每个个体通常具有多个不同的社区属性，可能同时属于多个社会团体，如家庭、朋友圈、同事圈.同样，社区重叠现象广泛存在于生物分子网络中.比如在基因调控网络或者蛋白质相互作用网络中，单个基因或者蛋白质往往参与多个生物功能表达过程.因此，研究复杂网络的重叠社区或者重叠节点具有非常重要的意义.又比如在网络谣言的传播中，那些处于重叠节点位置的个体对于谣言的扩散传播起了决定性的作用.研究重叠节点的性质有助于深入理解谣言的传播机制.在生物网络中，不同的生物功能之间相互关联，并非完全割裂，重叠节点往往预示着关键信息，对于人类疾病的治疗、农作物抗病性的研究都具有重要意义.

近年来，重叠社区发现算法研究取得了很大进展，典型的算法大致可以分为5类[6]：派系过滤算法、边划分算法、局部扩展与优化算法、模糊发现算法、标签传播算法.Palla等于2005年提出了派系过滤算法的代表方法——CPM(clique percolation method)[7]，其基本思想是复杂网络中多个派系(完全子图)之间相互重叠，构成了复杂网络中的社区.派系过滤算法通过寻找相互连通k-派系的方法确定社区结构.派系过滤算法也可以实现重叠节点的社区发现，因为在派系过滤算法中的单个节点可能属于不同k-派系.边划分算法将复杂网络中的边进行划分，从而对复杂网络中的社区结构进行挖掘.如果一个节点连接在一条边上，而且这条边被划分到多个边聚簇中，则此节点被判定为重叠节点[8-9].局部扩展与优化算法的社区发现过程是利用局部扩展与优化算法完成的.在社区发现的过程中，这种算法使用局部社区或者已发现社区组成种子社区，而节点之间连接的紧密程度往往通过局部密度函数进行度量[10-11].模糊发现算法在每一个节点上计算归属因子向量(belonging factor)[12]，以此来计算社区与社区的联系强度和节点对的联系强度.标签传播算法的主要思想是用标签传播的方式来确定每一个节点所属的社区，这是比较流行的一类算法.Gregory等在非重叠节点社区发现的标签传播算法LPA基础上将每个节点的标签用多个类标签标识，并引入隶属度的概念，提出了COPRA算法进行重叠节点社区发现[13-14].SLPA算法也是一种标签传播的重叠社区发现算法，它通过模拟演讲者-收听者来完成标签传播过程[15].在LPA算法中，复杂网络中的节点不会记住在某一时刻接收到的标签信息.与之不同的是，SLPA算法会保存节点曾经收到的所有标签，为每一个节点设立一个用于存储对应标签概率分布的存储区，其中的存储概率分布表示了当前节点的归属强度.文献[16]介绍了一种完全不一样的标签传播算法SpeakEasy.该算法运行速度快，适合不同种类的网络，但存在的问题是在识别重叠节点过程中可能出现重叠节点比重过大的现象.

本文借鉴SpeakEasy算法的思想，首先通过标签传播算法得到初始的无重叠社区划分，然后通过设计新的节点识别算法确定重叠节点，最后再对社区进行合并，提出OCPLP(overlapping community partitioning based on label propagation)算法.通过在LFR人工数据集、3个标准公开测试集以及真实的大豆基因共表达网络上对本文提出的算法与已有算法进行对比.

1 SpeakEasy算法简介

SpeakEasy与COPRA、SLPA等算法一样，都是以标签传播为基础，通过标签传播把每个节点划分到对应的社区中.不同的是，SpeakEasy同时考虑整个网络的全局标签分布情况与局部标签分布情况，结合了自顶而下策略与自底而上策略对标签进行传播.自顶而下策略主要是依据当前复杂网络中的全局标签分布情况来决定标签的传播，自底而上策略则主要考虑当前节点与邻居节点组成的局部子图中的标签分布信息.

SpeakEasy算法可以分为两个阶段：第1个阶段是非重叠社区划分，首先进行标签传播过程，待标签传播收敛以后，可以提取到一个完整的非重叠社区划分结果，重复此过程Nt次，得到Nt个非重叠划分，从Nt个划分中筛选出一个最优划分.如果不考虑重叠节点的话，此时已经得到了社区划分的结果.第2个阶段是重叠节点识别，即在最优划分基础上识别重叠节点.首先根据得到的Nt个划分结果计算共生矩阵A，A中的元素aij表示节点vi和vj在Nt次划分中被聚为同一个社区的次数.如果最优划分某个社区C之外的某个节点v与C中的节点的共生次数大于给定阈值，则可以认定v为C的重叠节点.定义节点v和社区C的平均权值为

(1)

当Wv C大于给定阈值γ时，认定v为C的重叠节点.

SpeakEasy算法的优势在于较少人工设定参数，适合不同种类的网络图，快速完成拥有大量节点的网络图的处理任务.不足之处是此算法在识别重叠节点时会有重叠节点比重过大的现象.

2 OCPLP算法

SpeakEasy算法存在两个问题.首先，当网络图规模较大且图中重叠节点较多时，两个社区之间会有大量的重合区域.其次，小社区对大社区内的节点吸引力过大，会存在“蛇吞象”现象.为了解决这两个问题，本文分别设计了新的重叠社区发现算法，并在最后增加了社区合并过程，提出了OCPLP算法，具体如下：

(1)随机初始化网络图

设整个网络图G包含n个节点，以每个节点的ID作为社区的标签信息.首先为每个节点i建立大小为Nb的缓冲区，记为bi，用以保存最近Nb次更新的标签.初始化时从该节点的邻居节点中随机抽取Nb次，将选中的邻居节点ID填入缓冲区，如图1所示.

图1 随机初始化网络图

(2)标签传播

①计算标签的全局概率分布，即计算所有标签在图G中全部节点缓冲区中的概率分布：

(2)

其中ni为第i个标签在图G中所有节点缓冲区出现的次数总和.

(3)

③计算每个节点的标签局部特异性，即该节点的邻居节点缓冲区中标签的实际分布与期望分布之差.记第i个标签在第j个节点的局部特异性为sji，则其计算公式为

(4)

④更新节点的缓冲区.对于第j个节点的缓冲区bj，选择最大的sji所对应的标签作为该节点的新增标签，即删除bj中的第1个元素，在队尾插入所选择的标签.

⑤重复②～④，遍历图G中所有节点.

⑥重复①～⑤，直到所有节点的缓冲区收敛.

例如在图1中一共有8个标签a、b、c、d、g、h、i、j，其全局概率分布依次为3/40、5/40、6/40、7/40、7/40、4/40、5/40、3/40.以节点d为例，其邻居节点的缓冲区的标签a、b、c、d、g、h、i、j的实际数量分布为2、2、3、6、2、2、2、1，总数为20.而按照全局概率分布，这8个标签的期望数分别为1.5、2.5、3.0、3.5、3.5、2.0、2.5、1.5.因此8个标签的特异程度分别为0.5、-0.5、0、2.5、-1.5、0、-0.5、-0.5，最大的为标签d的2.5.因此对节点d的缓冲区进行更新时首先删除其第1个位置的d，其余4个位置的c、b、h、g分别前移1位，末尾补充特异性最大的标签d.

(3)抽取社区划分结果

根据上述得到的标签分布结果进行社区划分，具体过程如下：

①统计第j个节点所有邻居缓冲区中的标签数.将数目最多的标签作为该节点的所属社区ID.该社区若已经存在，则将第j个节点划分到此社区中；若不存在，则以该ID新建社区，并添加第j个节点为该社区元素.

②重复①，遍历图中所有节点，假设共建立了k个社区，也就是说得到了一个包含k个社区的划分结果P={C1，C2，…，Ck}.

(4)选择最优划分

(5)

(6)

选择最大评价一致性的划分为最优划分.如果不考虑重叠节点的话，该划分就是最终社区划分的结果.

(5)识别重叠社区节点

计算Nt个划分的共生矩阵A，元素aij表示节点vi和vj在Nt次划分中被聚为同一个社区的次数.定义节点v和社区Ci的平均权值为

(7)

若Wv Ci>γ1，则节点v为社区Ci的重叠节点，γ1为设定的阈值.需要指出的是，式(7)中不仅考虑了社区Ci的规模，而且也考虑了社区Cj的规模，这样就在很大程度上避免了将大量大类节点计入小类的重叠节点，从而导致重叠节点比例过大的问题.识别重叠社区节点算法的伪代码如下：

OCPLP-识别重叠社区节点

： 重叠节点的阈值γ1，共生矩阵A

： 最优划分C，图中全部节点集合G

1： function FindOverlapNodes(γ1，A，G，C)

2： forv∈Gdo

3： forci∈Cdo

5： ifWv Ci>γ1then

6：Ci←Ci∪{v}

7： end if

8： end for

9： end for

10： end function

(6)社区合并

如果两个社区之间重合部分占比达到设定阈值，则合并这两个社区，即

其中γ2为设定的阈值.算法伪代码描述如下：

OCPLP-社区合并算法

： 合并社区的阈值γ2，共生矩阵A

： 最优划分C，图中全部节点集合G

1： function MergeCommunities(γ2，A，C，G)

2： forCi∈Cdo

3： forCj∈CandCj≠Cido

4： if |Ci∩Cj|/|Cj|>γ2then

5： forv∈Cjdo //合并Cj到Ci

ifv∉Cithen

Ci←Ci∪{v}

6： end if

7： end for

8： deleteCj

9： end if

10： end for

11： end for

12： end function

3 实 验

为验证本文算法的有效性，共设计了3个实验.首先利用LFR benchmark算法[17]生成虚拟的重叠网络，在人工数据集上将本文提出的OCPLP 与SLPA[15]、SpeakEasy[16]两种当前主流重叠社区划分算法进行对比.在第2个实验中选择几种常用的公开标准测试集，比较OCPLP与两种比较算法的性能.最后一个实验选择了实际的大豆基因共表达网络，分别使用SpeakEasy和OCPLP算法对基因共表达网络进行重叠社区划分，并且比较两种算法的结果.

3.1 LFR benchmark数据集对比

LFR benchmark引入网络度分布和社区大小分布的指数等参数来生成重叠网络，所生成的网络能够模拟现实网络中的重要性质[17].LFR benchmark中提供了多种参数以控制生成网络的拓扑结构.本文利用LFR benchmark工具生成了3个人工网络图：LFR1、LFR2、LFR3.表1列出了生成3个网络图时所使用的参数，各个参数的定义如下：N为节点数，m为边数，k为平均度，kmax为最大度，μ为混合程度，non为重叠节点数，noc为每个重叠节点从属的社区个数.

表1 生成LFR benchmark网络图的参数

复杂网络重叠社区发现算法的性能常用模块度Q[18]作为评价指标，其定义如下：

(8)

式中：m为网络中总的边数；Oi表示节点i所属社区个数；Nij=1代表节点i和节点j之间存在连边，否则不存在连边；ki为节点i度数；li为节点i属于某个社区的标号；δ(li，lj)=1当且仅当li=lj.

评价复杂网络重叠社区发现算法的性能的另一个常用指标为标准化互信息，对两个划分P(i)和P(j)，其标准化互信息为[11]

(9)

OCPLP与两种比较算法的模块度Q和标准化互信息In的对比结果如表2所示.缓冲区大小对结果整体影响不大，在本文实验中该参数取值为5.从表2可以看出，在人工数据集的两个指标上，OCPLP算法比SLPA、SpeakEasy两种算法表现略好.

表2 LFR benchmark数据集上的对比结果

下面重点考察对重叠节点的识别情况，将识别重叠节点的过程理解为二分类问题，将重叠节点理解为正样本，将非重叠节点理解为负样本，用召回率γr、精确率γp、F1度量3个评估指标来评价OCPLP算法与两种比较算法的优劣.

γr=nT/(nT+nN)

(10)

γp=nT/(nT+nP)

(11)

F1=2×(γr×γp)/(γr+γp)

(12)

其中nT为真阳性样本数，即对正类样本预测正确的样本数；nP为假阳性样本数，即把负类样本预测为正类的样本数；nN为假阴性样本数，即把正类样本预测为负类的样本数.

表3给出了在LFR1、LFR2、LFR3人工数据集上重叠节点识别的比较结果.由表3可以看出，在LFR1上，3种算法在3个指标的综合表现差异不大，其中OCPLP的表现最好.在LFR2和LFR3上，3种算法的表现差异明显，其中SLPA表现最差，而OCPLP的表现明显优于其他两种比较算法.在LFR1、LFR2、LFR3人工数据集上的平均精确率，OCPLP分别比SLPA和SpeakEasy 提高了83%和42%，而平均召回率则分别提高了55%和22%，F1度量分别提高了84%和40%.可以看出，OCPLP算法在这3个指标上全面优于SpeakEasy算法，而SpeakEasy算法又明显强于SLPA算法.

表3 重叠节点识别的对比结果

3.2 公开标准测试集对比

本文选择pol.books[19]、arxiv广义相对论学者合作网络(general relativity and quantum cosmology collaboration network)[20]和netscience[19]3个较为流行的公开数据集进行对比实验.

pol.books是基于亚马逊网站的美国政治类型书籍购买信息而构造的网络，有105个节点，441条边；arxiv广义相对论学者合作网络包括5 242 个节点和28 980条边；netscience是复杂网络学者合作网络，由1 461个节点和2 742条边构成.在3.1节的实验中可以看出SpeakEasy算法明显优于SLPA算法，所以在后面的实验部分只选择SpeakEasy算法与OCPLP算法进行对比.

(a) pol.books

(b) arxiv广义相对论学者合作网络

(c) netscience

图2 典型网络数据集的对比结果

Fig.2 Comparison results on the classical network datasets

图2给出了OCPLP算法和SpeakEasy算法在3个数据集上的对比结果.从图中可以看出，在3个真实数据集上OCPLP算法在不同阈值下的模块度Q都明显高于SpeakEasy算法.其中，在pol.books数据集上平均提高了34.53%，在arxiv广义相对论学者合作网络上平均提高了84.16%，而在netscience网络上平均提高了6.30%.

3.3 大豆基因共表达网络对比实验

为了进一步验证所提算法的有效性，本文利用大豆基因共表达网络构造了社区发现算法的测试算例.实验数据源于GEO数据库GPL4592平台下的6组大豆锈病相关的数据(GSE7108[21]、GSE8432[22]、GSE29740[23]、GSE29741、GSE33410[24]、GSE41724).通过计算基因之间的皮尔森相关系数构建了一个大豆基因共表达网络.该网络包含4 169个基因，21 135条边，每两个基因之间的相似度作为对应边的权重，平均度为10，平均聚类系数为0.56.针对所构建的大豆基因共表达网络，分别采用SpeakEasy算法和OCPLP算法对该网络进行社区划分.

图3 大豆基因共表达网络对比结果

图4 大豆基因共表达网络实验可视化效果

从图3可以看出，OCPLP算法在不同阈值下得到的模块度Q都较高，社区划分结果更好.图4给出了OCPLP算法对大豆基因共表达网络进行社区划分的可视化效果.对社区划分结果做进一步分析有助于研究在锈病环境下大豆的基因共表达现象，并为大豆育种提供帮助.

4 结 语

针对重叠节点社区发现问题，本文通过设计新的重叠社区发现算法，增加社区合并过程，提出了OCPLP算法.为验证所提算法的有效性，分别针对LFR benchmark人工数据集、3个典型标准数据集以及实际的大豆基因共表达网络设计了3个实验，将本文提出的算法与现有算法进行了对比.实验结果表明，本文提出的OCPLP算法性能明显优于对比算法，并极大改善了重叠节点比重过大的问题，使得结果更加符合问题的实际特征，也验证了OCPLP算法的有效性.