基于三级邻居影响力分析的重叠社区发现算法

林 穗，陈仕双，姜文超,+，熊 梦，贺忠堂

(1.广东工业大学 计算机学院，广东 广州 510006； 2.东莞中国科学院云计算产业技术创新与育成中心 技术预研部，广东 东莞 523808)

0 引 言

复杂网络[1,2]是对现实世界各类实体及其彼此之间关联的抽象。现实世界中复杂关联实体构成的社区实体之间往往存在着重叠和交集，由许多个社区网络构成一个复杂网络。

重叠社区发现有多种方法，例如基于派系过滤CPM[3,4]的重叠社区发现算法，该算法将社区看作整个复杂网络中的一个全连通子图；Lancichinetti等[5]提出了基于拓展函数和局部优化的重叠社区发现算法LFM，该算法给每个节点设定一个F值列表，并每次迭代删除F值小于0的节点；王斌等[6]提出基于边图的重叠社区发现算法，该算法根据计算各边的相似度实现社区划分和发现重叠社区。基于标签传播的社区发现算法有Gregory等[7]提出的COPRA，该算法分配给每个节点一个初始标签，不断通过标签传播迭代直至节点标签稳定；Xie等[8]提出SLPA算法，该算法为每个节点每次迭代增加一个标签，再通过阈值r进行筛选标签；Lu等[9]提出LPANNI算法，该算法在标签传播基础上根据邻居节点影响力计算新的标签隶属度。

然而，目前重叠社区发现算法仍然存在准确度不高和效率低下等问题，例如CPM算法的时间复杂度较高；COPRA算法划分的社区质量不高且不稳定；SLPA算法的空间复杂度较高。针对以上问题，本文提出一种基于三级邻居节点影响力度量TIM[10]的重叠社区发现算法OCDITN(overlapping community discovery algorithm based on three-level neighbor node influence analysis)，并分别使用基于人工模拟生成的大规模网络图数据集和来自真实世界的网络数据集对OCDITN算法进行测试，与SLPA、LPANNI、COPRA算法相比，OCDITN算法划分的社区更稳定，质量更好，效率也更高。

1 OCDITN算法

1.1 基于三级邻居的影响力度量

初始一个社区网络G=(V,E,Pu,v)，V和E分别代表社区网络中的节点数据集与边的数据集，Pu,v表示节点u对节点v的激活概率；M23表示在社区网络中将一个节点的传播影响力逐渐变小的2级、3级邻居节点视为一个集合，当节点的2级邻居处于激活状态，则M23中的3级邻居的就可能被激活为激活状态，此时M23被激活的概率如式(1)所示

(1)

对于随意节点u，其1级邻居节点数量与M23整体邻居节点数量相比，很多情况下M23一个整体的节点数量可能是1级邻居节点数量的若干倍。如图1所示，对于节点u而言，1级、2级、3级邻居节点，分别标记为V、W、X，其中M23代表着标记为W，X的节点为一个整体，并且可从图1看出，M23的节点数量与标记为V的节点数量之间的比值是3。

图1 节点u的邻居节点示例

由图1可以看出，节点u对2级、3级邻居节点的影响显然大于其对1级邻居的影响，这与节点随着传播层级的深入，其影响逐级衰减的特性相矛盾，因此需要通过加强1级邻居节点的传播影响力，来调整节点u对M23整体影响力与1级邻居节点影响力之间的比重。根据指数函数y=ex具有当x大于0，则y大于1的特性来加强1级邻居节点的传播影响力，引入参数θ调整影响差距，得到TIM节点影响力度量计算公式如式(2)所示

(2)

其中，Pu,v表示节点u对v的激活概率，参数θ可调整影响差距，本文实验参数θ取值为1000， |M23| 表示节点u的2级、3级邻居节点数量。

1.2 OCDITN算法标签更新

COPRA算法是Gregory等提出的一种基于标签传播的重叠社区发现算法，该算法主要步骤是：首先初始化每个节点的初始ID；然后节点再根据邻居所在社区的分布来决定自己的社区，这个过程称为节点的社区隶属划分过程，可用节点隶属度来表示；最后依据社区内部的节点数目或者标签数量经过两次迭代是否保持不变，来决定是否停止执行。节点隶属度计算方式如式(3)所示

(3)

其中，N(u) 代表节点u的邻居节点集；bt(c,u) 为迭代次数t次时的节点u对于社区c的隶属度。

在COPRA基础上，OCDITN算法在节点标签更新阶段重新优化并定义了节点与其邻居的相似度计算模型如式(4)所示

(4)

其中，T(u) 表示为数组中节点u的TIM值，代表节点u的影响力；节点u与邻居节点v之间共同节点的数量，记为NS(u,s)； 节点u的度，记为k(u)。 当Ov(u) 值越小时，则表示节点u与邻居节点v之间的关联越微弱，邻居节点对节点的影响越小。在选择节点更新标签时按节点影响力进行降序排序，将此序列记为SQ作为更新节点标签的序列，并依次更新节点，从而解决COPRA算法随机选择节点更新标签所带来的社区低质量性和不稳定性。参考COPRA算法中的节点隶属度bt(c,u)， 实现重叠社区的发现。在选择节点更新之后的标签更新过程中，邻居节点传播给节点u的主标签序列，用LSN表示，如式(5)所示

LSN={ls(c1,b1),ls(c2,b2),…,ls(cv,bv)}

(5)

其中，邻居节点v的主标签，记为ls(cv,bv)； 节点v从属社区cv的隶属度，记为bv；其中节点v属于由节点u的邻居节点所构成的序列之中。

借鉴LPANNI算法中计算标签隶属度的方法，计算更新节点标签的隶属度模型如式(6)所示

(6)

通过式(6)计算得到节点新的标签隶属度序列，记为LS′N， 删除LS′N序列中标签隶属度小于阈值p的标签，其中p=1/LN，LN(label number)表示节点u的标签集合的大小，从而重新得到标签序列LS″N。

采用LPANNI算法中标签序列归一化模型如式(7)所示，整理过后的节点标签序列LS″N， 再次得到新的标签序列LSN

(7)

在经过标签归一化模型处理后的节点标签序列LSu中，节点u选择最大标签隶属度的标签作为主标签。

1.3 OCDITN算法

OCDITN算法首先初始化每个节点标签为自身ID，并基于3级邻居计算每个节点影响力TIM值，根据节点影响力按降序进行排序，进而确定更新节点标签的顺序；其次，标签更新策略中利用节点与其邻居之间的相似度确定邻居节点标签序列LSN；最后，通过计算节点标签的隶属度来实现重叠社区的鉴别与发现，算法流程具体如下。

输入：无向无权网络G=(V,E,Pu,v)， 计算节点TIM值时的参数θ设为1000，Pu,v值设为0.5，标签传播过程的最大迭代次数T。

输出：节点u的标签集合LSu。

(1)初始化每个节点的标签ID为自身编号，标签的隶属度为1；

(2)通过式(2)计算每个节点影响力TIM值；并且依据TIM值降序对所有的节点进行排序，得到节点更新序列SQ；

(3)通过式(4)计算每个节点与其邻居节点之间的相似度；

当迭代次数t小于最大迭代次数T时，节点更新序列SQ中各节点的标签更新不断循环第(4)步到第(8)步，直到达到最大迭代次数T终止；

(4)通过式(3)计算每个邻居节点的节点隶属度，并将其所有的主标签bt(c,u) 传播给节点u，从而得到节点u标签集合LSN；

(5)通过式(6)重新计算节点的标签隶属度，重新得到节点标签集合LS′N；

(6)通过丢弃LS′N集合中标签隶属度小于阈值p的标签，重新得到标签集合LS″N；

(7)通过式(7)进行节点归一化得到新的节点标签集合LSu；

(8)在标签集合LSu中选择最大隶属度的标签作为节点u的最终主标签；

(9)输出标签集合LSu，其中含有多个标签的节点为重叠节点，重叠节点构成重叠社区。

2 实验分析

为验证OCDITN算法的有效性，本文基于人工模拟生成网络和真实网络两类数据集进行算法测试。对于人工合成网络，采用标准化互信息NMI[11]指标来衡量发现重叠社区与真实网络的重叠社区之间的相似度，NMI指标定义如式(8)所示

(8)

其中，在真实复杂网络中，社区网络结构的集合，记为X；用于实验测试来发现重叠社区的人工合成网络集合，记为Y；H(X|Y) 为社区X在社区Y上的条件熵，表示社区X与社区Y的差异程度。NMI指标的取值范围为[0,1]，NMI指标越趋向于0，说明该算法发现的重叠社区与真实网络的重叠社区差异越大。反之，NMI指标越趋向于1，说明该算法发现的重叠社区与真实网络的重叠社区差异越小，发现的重叠社区质量越高。

对于真实网络数据集，因为其社区分布真值是模糊的，可以使用模块度函数作为评价标准。为了方便测试各算法的实验效果，分别采用扩展模块度函数EQ[12]和Nicosia等提出的重叠模块度指标Qov[13]两种模块度评价函数作为算法实验测试评价标准。

2.1 真实数据集实验结果与分析

真实社会网络是对社会网络的真实结构截取的一部分子集，由于真实反映了实际网络结构和数据特性，因此真实网络数据分析结果对于网络社区发现算法有效性具有直接参考意义。本文在几个真实复杂网络数据集上对OCDITN算法进行测试并与SLPA、LPANNI、COPRA算法进行对比。实验数据集包括海豚社会网络(dolphin social network)、空手道俱乐部网络(Karate network)、美国政治之书网络(polbooks network)、博客网络(blogs network)、悲惨世界关系网络(lesmis network)、信任网络(PGP network)、互联网快照网络(internet network)，真实社会网络数据集见表1。

表1 真实社会网络数据集

表2和表3分别为OCDITN、SLPA、LPANNI和COPRA算法在各个数据集上测试的EQ值和Qov值。由表2可知，在对Dolphins、Karate、Polbooks、Blogs、Lesmis、PGP、Internet这7种网络数据集测试中，OCDITN算法的EQ值均高于SLPA、LPANNI、COPRA算法，说明具有较好的重叠社区划分效果。

表2 各算法计算EQ值实验结果

由表3可知，OCDITN算法对Karate、Blogs、PGP这3种网络数据的Qov值仅略低于COPRA算法外，其余数据集Qov值都优于SLPA、LPANNI、COPRA算法。OCDITN算法对Lesmis网络的EQ值最高，划分效果最好，对Karate网络数据的Qov值最低，划分效果最差。

2.2 模拟数据集实验结果与分析

LFR基准网络[14]是目前复杂网络社区发现算法研究中经典高效的人工模拟网络数据集，常用于发现重叠社区实验测试，拥有真实世界网络的重要属性。LFR基准网络主要包括以下参数：社区结构内部节点的数量，记为N；社区结构内部节点的平均度数，记为K；社区结构内部节点中的最大度数，记为maxk；最小社区结构中所包含节点的数目，记为minc；最大社区结构所包含节点的数目，记为maxc；社区结构之间所重叠节点的数目，记为on；重叠节点所隶属社区的数目，记为om；社区结构之间的混合程度，记为mu，表示着社区结构内部节点数目与社区结构外部节点所连接的比值，mu值越大社区之间的混合程度越高，社区结构划分越模糊，LFR 基准网络参数见表4。

表3 各算法计算Qov值的实验结果

表4 4种不同的LFR 基准网络参数

OCDITN、SLPA、LPANNI和COPRA算法在4组LFR网络数据中的实验结果如图2～图5所示。其中横坐标为混杂系数mu，纵坐标为社区发现质量NMI。由图2～图5可知，随着混杂系数的增大，OCDITN、SLPA、LPANNI和COPRA算法的NMI值降低，社区发现的质量也降低。

图2 N1网络的NMI值

如图2所示，N1网络的NMI值除了在mu=0.4时LPANNI算法的NMI值比OCDITN算法大以外，其余mu值参数下OCDITN算法的NMI值最大，说明OCDITN比其它算法更有效。

由N2网络测试结果可知，OCDITN算法比SLPA算法仅仅略好一点，两个算法之间效果很接近，如图3所示。

图3 N2网络的NMI值

如图4所示，以从N3网络的测试结果可知，OCDITN算法优于SLPA、LPANNI、COPRA算法，特别是在mu=0.4时，OCDITN算法效果优于SLPA、LPANNI、COPRA算法。

图4 N3网络的NMI值

从N4网络测试结果可以看出，4个算法效果都很接近，OCDITN算法依然略优于SLPA、LPANNI、COPRA算法，如图5所示。

图5 N4网络的NMI值

3 结束语

本文提出一种基于三级邻居节点影响力的重叠社区发现算法OCDITN。该算法结合最新的节点影响力度量算法对节点重要性进行排序。实验测试分别基于人工网络和真实世界网络进行测试，结果表明OCDITN算法能够有效检测出重叠社区，且其重叠社区发现质量更高。

复杂网络重叠社区发现问题相当复杂，尤其是在动态实时环境下，社区演变会对社区发现质量形成较大影响。针对复杂网络动态特性，挖掘发现其本质特征，并在动态环境下实时确定社区及其演变规律，这将是未来研究的重点。