节点自适应社会变化的机会网络社区检测算法

陶 洋，倪 强

（重庆邮电大学 通信与信息工程学院，重庆400065）

0 引 言

目前，研究者通过复杂的网络分析提出多个应用于复杂网络的社区检测算法［1－5］，例如利用节点的相似度和定义节点的中心度等节点属性［6－7］来分析社区结构。这些算法可以看成是集中式的社区检测算法，算法中考虑的节点间相似度及中心度的计算均依赖于服务器统一收集节点间联系信息，但实际网络环境中是很难实现的。因此，研究者在充分考虑节点的自组织特性基础上提出由节点本身收集信息的分布式检测算法，主要有：SIMPLE 算法、KCLIQUE算法和模块度算法［8］。文献 ［9］提出的Ker－nighan－Lin算法，类似于K－CLIQUE 算法定义节点能够与所有相邻节点相遇接触，节点间形成一个大小为K 的完全子图，节点视具体情况更新熟悉节点集；文献 ［10］通过对已有社区结构检测算法的研究，提出局部模块化社区结构的概念，在局部社区结构内的节点不需要通过服务器来收集信息。SIMPLE 算法［8］比较其它算法表现出计算复杂度低的优势，因此，本文在SIMPLE 算法基础上提出两种策略来实现局部社区动态检测的过程。

1 问题描述

上面所述的3种分布式社区检测算法都能够检测社区结构，但它们存在一个共同的限制因素：由于节点仅仅维护与其相遇节点间的信息，节点在不同社区间移动时，并不完全熟悉所在局部社区和熟悉节点集内节点的信息。例如，假设有如下场景：用户A 的日常时间大部分聚集在两个社会群体C1／C2中，白天处在工作范围的社会群体中，晚上处在社交朋友的社会群体中。另假设用户B 是用户A的同事，如果每天在工作时间里，用户B 与用户A 都能够相遇，那么可以说用户B 存在于用户A 的局部社区内 （反之亦然）。然而，再假设用户A 下班后与自己身边的朋友一起去健身，用户A 与用户B 之间的接触就没有那么频繁甚至不能相遇，或者说用户B 更换工作去了另一个地区。在这些情况下，以上3种算法都不能够准确检测到此时社区结构已发生的变化。此时，即使用户B 与用户A 不再见面，但用户B（A）仍将留在用户A（B）的局部社区内。 （如图1所示，其中虚线代表用户的移动）。

图1 局部社区动态变化

从以上的示例可以得出，随着现实场景复杂度的增加，节点间的动态交互行为变得更加不可预测，而上述分布式社区检测算法此时不能够准确检测到人类社交活动中因社会场景改变而引起的局部社区的变化。

为了有效检测局部社区的变化，本文提出的DA－CDA算法考虑节点自适应社会场景的变化，从而动态更新局部社区的结构。在后面的仿真验证结果表明，与典型的SIMPLE算法相比，DA－CDA 算法在保持较低计算能力和高性能的同时，在检测社区结构时能够自适应动态的社会变化，体现了DA－CDA 算法性能的优势。

2 节点自适应社会变化的社区检测算法

2.1 基本描述

定义1 （熟悉节点集）某节点V0的熟悉节点集（F0）定义为：与节点V0相遇累计接触时间tcum超过预定阈值tth的节点组成，其公式表示为

定义2 （局部社区）C0：表示节点V0的熟悉节点集内节点的集合与通过算法选取节点的集合所构成的社区。

当两个节点V0和Vi相遇时，它们首先彼此交换局部信息：Ci，Fi，然后决定是否将遇到的节点加入熟悉节点集中 （根据阈值标准），或者加入局部社区内。

定义3 （阈值标准）当两个节点相遇，每个节点计算累积接触时间tcum，如果tcum≥tth时，则将遇到的节点添加到熟悉节点集中 （因此也在局部社区内）。

2.2 SIMPLE算法思想

正如算法的名称一样，在SIMPLE 算法生命周期中节点之间相遇时彼此交换的信息很少。该算法下每个节点维持一个信息列表，如图2所示，其中，信息列表中计时器的值将在下一小节说明。

图2 信息列表

当节点V0和Vi相遇，在相互接触的时间段内，节点会发送给另一节点它的熟悉节点集和局部社区信息，在节点相互离开后，每个节点通过以下两个准则来计算并更新自身节点维持的信息列表。

接收阈值准则：当节点V0和节点Vi相遇累计接触时间没有达到阈值标准，如果节点V0局部社区内的节点与相遇节点Vi的熟悉节点集的共有节点数量大于λ 倍熟悉节点集里节点的数量，则将相遇节点Vi加入到节点V0的局部社区内，其公式为

式中：λ——接收阈值。

合并阈值准则：当节点V0与节点Vi相遇并满足阈值标准或接收阈值准则而加入到节点V0的局部社区内，如果局部社区C0和局部社区Ci内共有的节点数量大于γ 倍C0和Ci内节点取并集后的数量，那么将该两个局部社区合并

式中：γ——合并阈值。

2.3 DA－CDA算法设计

考虑在网络整体数据无法获取的情况下如何准确进行社区检测划分，DA－CDA 算法在基于SIMPLE 算法的思想上，从网络的局部拓扑结构出发，利用节点的自组织特性检测到其所在局部社区，充分考虑网络中节点间相互作用的关系对局部社区实施动态更新，使得节点能够动态自适应社会变化。

基于以上的分析，提出节点动态自适应社会变化的社区检测算法是属于SIMPLE 算法在复杂性和性能之间的折中考虑。DA－CDA 算法的更新策略是通过考虑解决以下问题来实现：

（1）随着节点与熟悉节点相遇间隔时间的老化，熟悉节点集如何更新；

（2）如何删除一些长时间联系不上的节点。

DA－CDA 算法的主要思想是在保持原来SIMPLE 算法中描述节点的基本特征和阈值准则外，同时增加两种新的策略，它能够识别并删除局部社区内一些长期无法联系上的节点并更新熟悉节点集和局部社区。因此，在节点间相遇接触时，将沿用SIMPLE 算法相同的阈值准则，节点之间交换熟悉节点集和局部社区并更新自身节点信息列表，该算法中增加使用以下策略。

2.3.1 熟悉节点集更新策略该策略是定义熟悉节点集中任意节点间相遇接触持续时间的比例保持在一个稳定估计值。如果该估计值低于给定的阈值，那么将决定删除熟悉节点集中的节点。因此，可以将时间分成若干时隙T，节点计算每个时隙内与其熟悉节点集中所有节点相遇接触持续时间的比例定义为：SampleΔT。在下一个时隙到达前，节点根据之前的估计值EstimatedΔT 和新的样本估计值SampleΔT 得出加权平均值从而计算并估计一个新的EstimatedΔT′，由下式（4）定义

式中：α——计算EstimatedΔT 的加权参数。α 值越小则表明在一个时隙内节点间相遇接触的持续时间的比例变化越大；相反，α值越大该比例值将保持在一个稳定范围，表明此时节点不能快速适应局部社区的变化。

最后，某时隙内节点Vi与熟悉节点相遇接触持续时间的比例为EstimatedΔTi，如果下式成立的话，那么节点Vi将被从熟悉节点集中删除

式中：FSoutth——节点Vi保持在局部社区内要求最小的阈值。

2.3.2 局部社区更新策略

该策略是要求所有社区内任意节点都维持一个计时器（LCouttimer），当某个节点进入局部社区内 （如节点Vi进入局部社区C0），它的计时器将被设置为起始状态；当下面情况之一发生时，计时器的值将被更新。

（1）节点V0与节点Vi相遇；

（2）节点V0与另一节点相遇 （如节点Vt），而节点Vi存在节点Vt的局部社区内。

另外，当相应节点的计时器超时，该节点将被从局部社区内删除。如果被删除节点存在局部社区内某节点的熟悉节点集中，那么节点将从熟悉节点集中被其删除，这保证了两种更新策略的一致性。

需要注意的是局部社区更新策略能够保证节点被删除仅仅当局部社区内所有节点都与它长时间没有接触联系，而当局部社区内至少存在一个节点与它存在接触联系，那么该节点必须保留在局部社区内。

3 仿真与分析

本文的仿真工作是为了验证DA－CDA 算法的有效性，并通过与SIMPLE算法进行仿真对比分析，验证其在动态社区结构检测情况下的性能。

3.1 仿真环境设置

本 文 采 用ONE （opportunistic network environment）仿真平台对该算法进行验证，节点移动按照HCMM 移动模型。尽管这是一个特定和简单的场景，也足以验证DACDA 算法在实现社区检测时能够正确识别并适应社会变化的突出性能。

HCMM 移动模型是根据真实人类运动模式而得出统计数据的一个移动模型，每个节点最初与一个特定的社区（即家庭社区）相关联，并且与家庭社区的所有其它成员具有一定的社会关系。其中某些节点还具有保持与家庭社区外的外部社区有联系。对于每个社会关系，特殊的外部社区和该外部社区内的特定节点都是按照均匀分布来选定的。节点的移动模型是由其社会关系确定的，即一个家庭社区的节点向某个特定的社区 （家庭社区或者外部社区）移动的概率与该社区内与其存在社会关系的节点数量成正比。另外，当节点进入一个外部社区后，给定它仍存在于该外部社区内移动的概率为pe，而返回家庭社区的概率为1－pe。因此，HCMM 移动模型是与现实逼真的模拟场景，用户一般包括同一个家庭社区内的成员，同时也包括一些尚未返回家庭社区的外部社区成员。

3.2 仿真结果及分析

仿真的目的是要验证DA－CDA 算法是否能够正确检测社区，同时也能自适应动态的社区变化。仿真持续48h，并且每6h对参数进行重新配置。这意味着在每次重新配置之后，自适应节点都要随机选择加入一个或两个社区。因此，我们主要观察每次在进行重新配置时间间隔内各社区内节点数目的变化。

仿真参数设置见表1。

表1 仿真参数设置

依据SIMPLE算法验证采取设置的较有效的λ、γ 的参数值来验证DA－CDA 算法，在引入两种更新策略的参数后，我们观察在一个固定值的时隙T 内，FSoutth的设置也应该需要考虑社区交往的动态性。在仿真验证中，节点之间都保持着较短时间的接触 （即累积接触时间较短），因此FSoutth值设置不应该超过5%，否则熟悉节点集大部分时间都将保持为空的状态。对于局部社区更新策略中使用的计时器（LCouttimer），必须根据时隙T 相应的顺序来设置相应的值，否则将会导致局部社区错误删除节点。

图3和图4描述的是在两种不同选择下模拟仿真运行的运行结果，其中两幅图中的图 （a）和图 （b）均分别表示SIMPLE算法和DA－CDA 算法下自适应节点检测到的局部社区结构，自适应节点不采用家庭社区内的节点。仿真期间两种模拟运行因自适应节点进入不同社区和社区顺序不同而形成不同结果。柱状图表示在每次进行重新配置的时间间隔结束前局部社区结构的变化，括号内的数字表示在这段时间自适应节点进入社区的序号。

图3 第一种模拟运行下自适应节点检测的社区结构

图4 第二种模拟运行下自适应节点检测的社区结构

从图3 （a）和图4 （a）中可以很清楚的看出SIMPLE算法的局限性。在两种不同模拟运行的情况下，随着模拟时间的增加局部社区变大。在每次完成重新配置间隔时间后，自适应节点都会不断增加新的节点加入局部社区内，同时维护过去所有相遇节点的信息。因此，当局部社区在某个时候达到最大规模54时 （两种不同选择都在24h处），接下来的模拟时间将保持这个最大规模运行。需要特别说明的是，在模拟运行6h到12h之间的一种特殊的情况。比如在图3 （a）中，即使自适应节点只选择加入社区一，但是局部社区内包含社区二的节点数量依然增加。这可以看作是一个过渡阶段，由于每次重新配置的开始阶段仿真严格要求与自适应节点位置相连的原因而造成的影响，是由节点移动模型决定的，如果节点进入其它外部社区，它回到家庭社区的概率为1－pe，而它选择留在该外部社区内的概率为pe。因此，如果后者事件发生的话，它将继续与该外部社区内的其它节点进行接触。这就是在12h时局部社区内包含社区二的节点数量增加的原因。

从图3 （b）和图4 （b）可以看出，DA－CDA 算法能够实现自适应节点不断动态更新局部社区内包含每个社区的节点数量。由于加入更新策略，自适应节点通过保留家庭社区内的节点和更新进入的外部社区内的节点对局部社区进行更新，同时删除那些和局部社区不相关的节点。这些节点要么属于之前加入的社区 （例如，当自适应节点从社区一移动到社区二，那么它将删除所有与社区一相关联的节点，反之亦然）；要么属于刚加入的社区尚未有足够时间接触的节点 （例如，这种情况出现在图3 （b）的30h处，即使在重新配置后进入的外部社区相同且节点数量没有改变，局部社区还是减小了）。需要特别说明的是，在12h到18h阶段，局部社区很明显的变大，是由于在这期间，自适应节点属于进入一个历史上曾进入过的社区内。因此，由于自适应节点与该社区内其它节点相遇接触的累计持续时间已经很接近阈值TTH，从而有很大可能增加更多的节点加入局部社区内。

图5表示在第一种模拟仿真运行情况下，在重新配置间隔时间为6h到12h阶段，自适应节点通过局部社区中包含的社区一和社区二的节点数量的变化来进行对比来检测算法的演变。（需要注意的是：家庭社区内的节点变化不包括在该图中）

图5 第一种模拟运行6h到12h时间内局部社区结构变化

图5 （a）描述的是检测SIMPLE 算法的演变，在开始阶段 （21600s），局部社区仅由社区二中的4个节点组成；在过渡阶段 （21600s－24000s），由于自适应节点与社区二中的节点逐渐相遇接触导致局部社区包含社区二节点的数量曲线上升，当节点间相互接触的社会活动减少并逐渐消失时，曲线将保持不变。与此同时，自适应节点与社区一中的节点之间相互接触机会变大，局部社区包含社区一节点的数量曲线也将上升。

图5 （b）描述的是相同情况下检测DA－CDA 算法的演变。从图中可以看出，社区二的节点数量曲线大概在26500 s之前与图5 （a）类似。但是，由于自适应节点与社区二中相关联的熟悉节点间接触时间间隔已超期，节点将删除接触时间间隔已超期的熟悉节点并更新自身的信息列表。大约在30000s左右时局部社区包含社区二节点的数量曲线下降到零。相反，从32000s时间点开始，由于自适应节点与社区一中的节点相互接触的机会比较频繁使得局部社区包含社区一节点的数量曲线上升。最后，在配置间隔的时间结束时，自适应节点所在的局部社区仅由社区一中的节点组成 （当然也包括自适应节点家庭社区内的节点）。

从以上仿真验证分析结果可以看出，由于不能很好的自适应社会变化，SIMPLE 算法的性能较低；而DA－CDA算法则能够达到更高的性能。第二种模拟仿真运行情况与第一种类似，考虑到本文的空间故将其省略。

4 结束语

目前已有研究中包括很多的社区检测算法，但是很少有算法能有效处理局部社区的动态变化。因此，本文提出一种节点动态自适应社会变化的机会网络社区检测算法。通过仿真验证，DA－CDA 算法在保持较低计算能力要求的同时，较之SIMPLE算法由于能够保证每个用户都能够了解整个局部社区内用户的动态变化而体现出更高的性能，将是一种更好执行检测社区的解决方案。然而，本文提出DA－CDA 算法的准确度也与很多因素有关，如节点的密集程度和局部社区结构的随机性等，而这些因素都会影响算法的整体性能，本文所提算法有待进一步优化。DA－CDA算法能够动态检测社区结构，这将有利于提高机会网络中消息传递的成功率，尤其是对时间敏感型的消息，在后续的工作中将作为重点的研究。

［1］Pelusi L，Passarella A，Conti M.Opportunistic networking：data forwarding in disconnected mobile ad hoc networks［C］／／IEEE Communication Magazine，2006：134－141.

［2］XIONG Yongping，SUN Limin，NIU Jianwei，et al.Opportunistic networks［J］.Journal of Software，2009，20 （1）：124－137 （in Chinese）.［熊永平，孙利民，牛建伟，等.机会网络 ［J］.软件学报，2009，20 （1）：124－137.］

［3］PAN Hui，Jon Crowcroft，Eiko Yoneki.BUBBLE Rap：Social－based forwarding in delay tolerant networks ［C］／／IEEE Transactions on Mobile Computing，2011：1576－1589.

［4］Bum Soon Jang，Timoth Mann，Yoonsuck Choe.Effects of varying the delay distribution in random，scale－free，and smallworld networks ［C］／／Future Information Technology and Management Engineering，Texas A＆M University.USA：IEEE，2008：316－321.

［5］WANG Dan，JING Yuanwei，YAN Minxiu.Effect of network structure on packet delivery in small－world network ［C］／／International Conference on Communication Software and Networks.China：IEEE，2009：399－403.

［6］LUO Qi.A new community structure detection method based on structural similarity ［C］／／International Conference on Computational Intelligence and Security，IEEE， 2011：1260－1262.

［7］CHEN Qiong，WU Tingting.A method for local community detection by finding maximal－degree nodes［C］／／International Conference on Machine Learning and Cybernetics，IEEE，2010：8－13.

［8］Hui P，Yoneki E，Chan SY，et al.Distributed community detection in delay tolerant networks ［C］／／Proceedings of MobiArch，2007.

［9］ZHAO Fengxia，XIE Fuding.Detecting community in complex networks using K－means cluster algorithm ［J］.Application Research of Computers，2009，26 （6）：2041－2049 （in Chinese）.［赵凤霞，谢福鼎.基于K－means聚类算法的复杂网络社团发现新方法［J］.计算机应用研究，2009，26 （6）：2041－2049.］

［10］Clauset A.Finding local community structures in networks［C］／／Physical Review E Stat，2005.