基于边权重局部扩展的机会网络社区检测方法

侯思权，张振宇，文少杰

（新疆大学 信息科学与工程学院，新疆 乌鲁木齐830046）

0 引 言

社区检测作为复杂网络的一个重要研究课题，已涌现出许多相关算法［1，2］，这些算法可以检测出不相交的社区结构。最近研究发现复杂网络的社区结构是相交的、分层的，许多算法［3－6］设计用来检测这些重叠的、分层的社区结构，重叠社区检测成为了当前复杂网络结构挖掘的前沿热点。

机会网络［7］是一个具有结构动态性、间歇性链接的特殊复杂网络。社区检测具有一些其它网络不具备的难点：节点移动性较强、无法预知社区规模、社区个数不确定、具有重叠社区现象等。目前针对机会网络社区结构的研究多基于复杂网络社区检测原理，包括MCPD［8］、DCDA［9］、NBDE［10］等。文献 ［8］利用节点间最大连通概率 （MCP）作为分裂图的依据，并使用GN 算法得到社区结构，然而在机会网络中，节点有电量和计算能力的限制，并不能得到网络全局拓扑结构。文献 ［9］利用传统复杂网络社区检测理论，简单的根据节点接触信息，把小于某个阈值的边移除，并把网络拓扑结构图简单地转化为无权图，忽略了节点间关系强度信息。文献 ［10］提出节点归属性动态社区检测算法 （NBDE），利用机会网络中邻居节点信息计算节点对社区的归属性，并根据归属性，利用标签传递原理来检测社区。文献 ［11］利用机会网络中随时间演化的边上权重，提出一种可检测时变社区结构的方法。该方法的计算复杂度稍高，考虑到网络节点能量和计算能力限制，在现实应用中实现相对不易。以上方法对机会网络中节点间关系强度信息利用较少，且重叠社区的研究相对较少，同时在机会网络中检测重叠节点，具有很重要的意义，其利用重叠节点作为社区间通信的桥渡节点，这些重叠节点对机会网络中消息转发和路由的可靠性具有较大改善。因此需要提出一种适合机会网络特征的重叠社区检测方法。

为了解决机会网络中重叠社区的检测问题，本文结合节点间关系强度，给出了一个针对机会网络特点的基于边权重局部扩展的社区检测方法 （LWLE），找到局部关系强度值最大且密集的节点集合作为社区，这样得到的社区更符合机会网络的社会属性。

1 基于边权重的局部扩展社区检测方法

1.1 关系强度计算及网络结构建立

关系强度表示节点间链接强弱，节点间相遇间隔时间越短，相遇时间越长，则关系强度值越大，并把其值作为机会网络中节点间边的权重。定义关系强度为

式中：α——控制参数，范围为 ［0－1］，ict——相遇间隔时间，cd——相遇时间。

本文使用文献［12］中提出的滑动窗口方法来建立具有边权重的机会网络结构，每个节点都有一个滑动窗口，它是一个大小为t的时间帧。随着时间步的移动，滑动窗口内容更新，使用式 （1）计算出现在滑动窗口内与邻居节点间的关系强度值，当节点间关系强度大于某阈值时，则节点与邻居节点之间建立边，并把该关系强度值作为边权重。节点保存筛选过的邻居节点集合及权重值。这样可以得到一个具有边权重的动态机会网络结构。该方法建立的网络结构较真实地表现了节点间的社会关系，在该网络结构下使用社区检测算法得出的社区结构更符合实际情况。

1.2 局部扩展方法

研究表明社区是一组关联紧密的节点集合，在机会网络中，表现为局部结构中关联强度最大的一组节点。由于机会网络中节点受到通信范围及能量的限制，节点一般不具备整个网络拓扑结构知识，仅保存了其与邻居节点间的关联信息。因此，本文结合机会网络特点，使用局部扩展社区检测方法来得到重叠社区结构。如图1所示，已知机会网络中节点仅知道邻居节点信息，区域N 为已探知区域，而U 为未知区域，由红色节点区域C向区域U 逐步扩展。在已知的区域 （C＋N），C 占的关系强度比重越大，C就越有可能成为一个社区。如果确定C 为C＋N 区域中具有最大的关系强度比值，那么就认定C 为一个最优局部社区。

因此，使用式 （2）的最大值来确定最大关系强度区域

图1 局部扩展

式中：rs（e）——节点关系强度 （边权重），C——社区，N为邻居节点区域。ΔCS（i）——节点i对C 社区关系强度的贡献。从任一节点出发，根据式 （2），选择具有较大ΔCS（i）值的邻居节点逐一扩展区域C，直到CS 的值达到局部最大，则确定C 为一个社区，继续随机选择下一个未分配社区的节点扩展，当所有节点都分配了社区时，算法终止。

1.3 优化策略及重叠社区检测

由于局部扩展方法对初始节点的选择比较敏感，以上方法存在初始节点选择随机、重复计算等不足，为了更好的得到社区结构，本文使用节点聚集系数［13］对初始节点选择进行优化。节点i的聚集系数计算见式 （4）

式 中：E（i）——节点i的邻居节点间的实际连边数。k（i）——节点i的度。该公式表示i的邻居节点间的连边数与有可能达到的最大连边数的一个比值，c（i）值越大，表明节点i的邻居节点间的联系越紧密。即节点i与其邻居节点更可能成为一个社区的中心。

使用聚集系数较大的节点作为初始种子节点，进行局部扩展，得出的社区划分结果比较合理。

因此其社区检测步骤为：

（1）计算节点聚集系数，根据节点聚集系数对节点进行中心性排名，得到节点集合S。

（2）从S中选择具有最大节点聚集系数且未分配社区的节点作为种子节点，标记为社区C，并从S中移除该节点。遍历获得种子节点的邻居节点集合，并根据式 （3）得到邻居节点的贡献值集合B，选择具有最大贡献值且为正值的邻居节点加入社区C。

（3）扩展社区C 的邻居节点集合 （包含已分配社区的节点），并重新计算每个邻居节点对社区C的贡献值，更新集合B，选择具有最大贡献值的节点加入社区C。

（4）重复步骤 （3），直到社区C 的所有邻居节点对社区C贡献值ΔCS（i）＜＝0，算法停止，得到社区C。

（5）重复步骤 （2），直到所有节点都分配了社区，最终可以得到重叠社区。

LWLE中计算节点聚集系数时间复杂度为O（kn），k为节点度，n为网络节点数。局部扩展社区检测方法中时间复杂度为O（ncs2c），nc为社区规模，sc为社区大小，最坏情况为整个网络为一个社区情况，时间复杂度为O（n2）。

2 仿真结果及分析

为验证LWLE算法在机会网络中社区检测的准确性，本文使用DTN 网络环境模拟器ONE，对算法进行仿真。ONE平台充分拟合了机会网络特点，它将节点移动模型、DTN 路由和可视化的图形界面整合为一体。这样ONE 就非常容易进行扩展，并可以提供大量的结果报告和分析模型［14］。使用ONE作为该算法的模拟平台能够更真实的验证本算法的性能。在仿真中，本文使用基于社区的移动模型，其根据节点间社会关系计算每个社区对节点吸引力，移动节点，模拟0～12h节点运动状况，收集运动接触产生的数据，然后使用LWLE 算法与节点动态归属性算法（NBDE）对收集的数据进行对比分析，得出社区划分结果，计算节点被正确划分的比率。ONE 仿真使用环境参数见表1。

表1 仿真环境参数

基于社区的模型是一种考虑了节点社会性的移动模型，该模型在本质上还是基于移动周期的，但是引入了节点社区的概念，目的是为了更好的模拟现实中节点的社会性，它使用CAVEMAN 模型生成节点间社会关系图作为社区模型的社会关系矩阵输入，如图2所示，该图具有10个节点3个社区，节点间的数字表示节点间的社会关系紧密程度，值越大表明两者的关系越紧密。

从图2 可以看出该拓扑结构具有3 个社区 ｛A，B，C｝、｛D，E，F，G｝、｛H，I，L｝。仿真运行0～12h，在每个时间点分别生成5次数据，分别使用LWLE 与NBDE算法对数据进行社区分析，比较社区划分的平均准确率，比较结果如图3所示。

图2 社会关系

图3 社区检测正确率对比

在本次仿真中可以，随着仿真时间增加，LWLE 正确检测社区的概率也在增加，运行到第4个小时检测正确率已经超过NBDE 算法，当运行到第6 个小时的时候，LWLE算法已经能够正确的检测出社区结果。主要原因是仿真时间越长，所有节点之间接触越多，同一个社区内节点间关系强度值比社区间的关系强度逐步增强，因此LWLE检测出的社区结果正确率越高，而NBDE 算法是基于标签传递的原理，随着运行时间的增加，节点间的接触也越来越多，邻居节点增加，由于该算法并没有区分节点间关系强度大小，并不能够完全正确的得到节点所属社区，只能正确检测部分节点的所属社区。

在该仿真环境下，网络较为稠密时，节点为30 个、4个社区时的LWLE与NBDE社区检测正确率对比情况，如图4所示，随着仿真时间增加，LWLE 检测正确率逐渐增加，到第5个小时时接近100%，而NBDE 算法检测正确率相对上图还有所下降，仅为60%。

为验证本文提出算法对机会网络中重叠社区检测正确率，首先调整社区模型，然后输入一个具有23 个节点，｛Ca，Cb，Cc，Cd｝4 个社区的一个社会关系矩阵，其中Ca，Cb社区有1 个重叠节点，Cb，Cc社区有3 个重叠节点。在ONE平台下模拟节点运动，收集0～12h产生的数据，使用LWLE算法分析结果，如图5所示，重叠社区检测正确率接近90%，仅个别重叠节点未被正确检测。

图4 网络节点稠密时，社区检测正确率对比

图5 重叠社区划分正确率

仿真结果表明，该方法与机会网络耦合度很高，充分利用了机会网络中节点间的关系强度信息，LWLE 能够以较高正确率检测出了重叠的并且关系强度较高的一组节点集合。

3 结束语

本文针对机会网络中社区重叠问题，利用节点间的关系强度值，建立具有边权重的网络拓扑，提出一种基于边权重局部扩展的社区检测算法 （LWLE）。为解决局部扩展方法中的随机选择初始节点、重复计算的问题，给出一种利用节点聚集系数对初始节点选择的局部扩展优化策略。LWLE能够较准确的发现机会网络中的重叠社区结构。然而机会网络中的节点具有较强的移动性，网络结构不稳定，动态重叠社区检测的研究是今后工作中研究方向。

［1］Newman MEJ.Communities，modules and large－scale structure in networks［J］.Nature Physics，2011，8 （1）：25－31.

［2］Raghavan UN，Albert R，Kumara S.Near linear time algorithm to detect community structures in large－scale networks［J］.Physical Review E，2007，76 （3）：036106.

［3］Lancichinetti A，Fortunato S，Kertész J.Detecting the over－lapping and hie－rarchical community structure in complex networks［J］.New Journal of Physics，2009，11 （3）：033015.

［4］Ahn YY，Bagrow JP，Lehmann S.Link communities reveal multi－scale complexity in networks ［J］.Nature，2010，466（7307）：761－764.

［5］Shen H，Cheng X，Cai K，et al.Detect overlapping and hierarchical community structure in networks ［J］.Physica A：Statistical Mechanics and its Applications，2009，388 （8）：1706－1712.

［6］Zhubing L，Jian W，Yuzhou L.An overview on overlapping community detection ［C］／／7th International Conference on Computer Science ＆Education.IEEE，2012：486－490.

［7］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.］

［8］Zhang Y，Han Y，Li J，et al.Community detection using maximum connection probability in opportunistic network［C］／／4th International Conference on Intelligent Systems Modelling ＆Simulation.IEEE，2013 475－480.

［9］Hui P，Yoneki E，Chan SY，et al.Distributed community detection in delay tolerant networks ［C］／／Proceedings of 2nd ACM／IEEE International Workshop on Mobility in the Evolving Internet Architecture.ACM，2007.

［10］WU Dapeng，XIANG Xiaohua，WANG Ruyan，et al.Nodebelongingness dynamic estimate community detect strategy in opportunistic networks ［J］.Computer Engineering And Design，2012，33 （10）：3673－3677 （in Chinese）. ［吴大鹏，向小华，王汝言，等.节点归属性动态估计的机会网络社区检测策略 ［J］.计算机工程与设计，2012，33 （10）：3673－3677.］

［11］Xu K，Yang GH，Li VOK，et al.Detecting dynamic communities in opportunistic networks ［C］／／First International Conference on Ubiquitous and Future Networks.IEEE，2009：159－164.

［12］Lenando H，Zen K，Jambli MN，et al.Forming a social structure in mobile opportunistic networks ［C］／／17th Asia－Pacific Conference on Communications.IEEE，2011：450－455.

［13］LI Kongwen，GU Qing，ZHANG Yao，et al.Local community detecting method based on the clustering coefficient［J］.Computer Science，2010，37 （7）：46－49 （in Chinese）. ［李孔文，顾庆，张尧，等.一种基于聚集系数的局部社团划分算法 ［J］.计算机科学，2010，37 （7）：46－49.］

［14］WANG Zhen，WANG Xinhua，SUI Jinglin.Extending research for ONE simulator of opportunistic network ［J］.Application Research of Computers，2012，29 （1）：272－277 （in Chinese）.［王朕，王新华，隋敬麒.机会网络模拟器ONE及其扩展研究 ［J］.计算机应用研究，2012，29 （1）：272－277.］