动态分布式社团检测算法 - 经济 - 管理财经 -

时间：2017-02-14 10:31:19来源：网络收集Tags:     ()

胡桐1，2，3，漆随平1，2，3

（1. 山东省海洋环境监测技术重点实验室，山东 青岛 266001；2. 山东省科学院海洋仪器仪表研究所，山东 青岛 266001；3. 国家海洋监测设备工程技术研究中心，山东 青岛 266001）

摘 要： 针对手持设备网络，提出动态分布式社团检测算法。首先利用节点相遇历史数据计算累积相遇持续时间与相遇次数均值，并作为动态阈值确定节点朋友集合，然后构建本地关系图，最后对本地关系图进行多社团检测。仿真结果表明该算法能够反映节点间关系的变化，更适用于动态变化的移动容迟网络环境。

关键词： 手持设备网络；社团检测；数据转发

中图分类号：TP301.6 文献标志码：A DOI：10.3969/j.issn.1674-9146.2015.03.068

手持设备组成的移动容迟网络环境（Pocket Switched Networks）中，网络节点随着人的移动而移动，并且采用“存储—携带—转发”方式进行通信[1-2]。人与人之间存在社团结构（Community），属于同一社团的节点之间相遇概率远大于属于不同社团节点之间的相遇概率。相对于不断变化的网络拓扑，人的社团关系更加稳定，利用社团结构进行消息转发能有效提高消息传输成功率，社团结构检测因此成为这类数据转发算法的重要组成部分。

移动容迟网络中任何节点均无法获得网络全局信息，只能采用分布式方式获得局部拓扑与部分相遇节点信息。文献[3]提出3种分布式社团检测算法（SIMPLE算法，k-CLIQUE算法和MODULARITY算法），但均须预先指定节点累计相遇持续时间（Accumulated Contact Duration）阈值。文献[4]提出SHARC算法，但节点间通信代价高。另外，上述算法均只能进行单社团检测，而实际上各节点可能同时具有多个不同的社团结构。

针上海癫痫医院对已有算法的缺点，本文提出动态分布式社团检测算法。该算法首先利用节点自身记录的相遇历史数据计算累积相遇持续时间与相遇次数（Contact Times）的均值，并作为动态阈值确定各节点的朋友集合并构建本地关系图(Local Contact Graph)，然后对各节点的本地关系图进行多社团检测。本文利用基于实验数据的仿真将该算法同k-CLIQUE算法进行了比较。结果表明，动态分布式社团检测算法能够反映节点间关系的变化，更适用于动态变化的移动容迟网络环境。

1 算法设计

笔者提出的动态分布式社团检测算法包含朋友集合的动态阈值计算、节点关系图的构建与更新和基于关系图的多社团检测3个主要部分。

1.1 朋友集合的动态阈值计算

文献[5]对手持设备网络中移动节点的相遇规律进行了分析，得出了单个节点与其他节点的相遇次数服从指数截断的幂律分布(Power law with exponential cutoff)的结论。通常，彼此间相遇次数较多并且相遇持续时间较长的节点属于同一社团的概率较大[3]。本文提出利用一定时间内各节点与其他节点的累积相遇持续时间、相遇次数的均值作为阈值，将累积相遇持续时间、相遇次数分别大于各自阈值的节点加入到朋友集合中。

1.2 节点关系图的构建与更新

本地关系图的本质是一个两跳的自我中心网络（Ego Network），见图1。图的中心为各网络节点，图中第一跳节点（即与中心直接相连的节点）为该节点的朋友节点，而图中第二跳节点为各朋友节点的朋友节点。在关系图中，每条边表示所连接的2个节点互为朋友关系。

本地关系图的构建过程即网络中各节点首先将各自朋友集合中的节点加入到本地关系图中，再与朋友节点相遇时互相交换各自的朋友集合，同时将朋友的朋友加入到自己的本地关系图，并根据节点间的关系在互为朋友的节点之间建立一条边。

1.3 基于关系图的多社团检测

多社团结构的检测能够有效避免消息转发过程中不必要的消息复制从而降低通信代价。本文利用文献[6]中提出的FOCS算法对本地关系图中存在的多社团结构进行检测。该算法大致分为2个步骤，首先检测图中所有可能的社团，然后对其中的某些社团进行合并。

2 仿真实验

利用基于实验数日照看癫痫病好的医院有哪些据的仿真对动态分布式社团检测算法进行验证，并与k-CLIQUE算法进行比较。

2.1 仿真环境

本文使用The ONE（Opportunistic Network Environment）模拟器进行基于实验数据的仿真，仿真过程使用的数据是由MIT Reality Mining数据集中选择的时间跨度为30天的节点相遇记录[7]。相关参数的设置为：对于k-CLIQUE算法，本文在仿真过程中设置参数k的值为5，即团中节点数为5且相邻的团具有4个相同节点，而相遇持续时间的阈值设置为多个不同的值。对于动态分布式社团检测算法，时间窗口的长度设为5天，滑动距离设为1天。FOCS算法的参数β取值为0.6。

2.2 结果分析

1）与朋友节点的累积相遇持续时间的比例。笔者对比了各节点与其朋友节点的累积相遇持续时间占与所有相遇节点的累积相遇持续时间之和的比例。该值反映了网络中各节点在当前时间窗口与其朋友节点之间联系的紧密程度（见图2）。本文提出的动态分布式社团检测算法由于采用了动态阈值，具有较高的比值并且较为稳定。而k-CLIQUE算法，由于采用了固定阈值，不能够适应节点关系的变化，存在明显波动且不能及时对当前朋友节点集合进行更新。

2）与朋友节点的相遇次数的比例。除相遇持续时间外，相遇次数也能够反映节点之间联系的紧密程度。笔者对比了各节点与朋友节点的相遇次数占与所有相遇节点的相遇次数之和的比例，结果见图3。类似于相遇持续时间的对比结果，本文提出的动态分布式社团检测算法具有较高的相遇次数的比值，并且相对较为稳定。而对于k-CLIQUE算法，相遇次数的比值同样存在明显波动，不能有效地检测出节点之间相遇频率的变化。

3）朋友节点所占比例。本文还对比了不同算法中朋友节点所占的比例，结果见第70页图4，从第70页图4可以看出，在不同算法中各节点的朋友节点占所有相遇节点的比例均比较低（小于20%）。相对于各节点所遇到的全部节点，其朋友节点只占其中的一小部分。本文提出的动态分布式社团检测算法具有相对较高的朋友节点比例且较为稳定。而k-CLIQUE算法在不同阈值条件下均出现了较大的波动。结合上文对累积相遇持续时间与相遇次数的对比结果可以看出，固定阈值不能反映节点间联系紧密程度的变化。

在基于社会网络的消息转发过程中，消息通常借助朋友节点进行转发。对于网络中的某个节点，若其朋友节点的比例降低，表明了在当前时间窗口中与该节点联系较为紧密的节点已经发生变化。若该节点等待与之前的朋友节点相遇并转发消息，将错过大量通信机会，导致消息传输成功率的降低，传输时延增大。综上所述，文章提出的动态分布式社团检测算法由于能够适应节点间关系的变化，更加适用于动态变化的移动容迟网络环境。

3 结束语

本文针对手持设备网络中的社团检测问题，提出动态分布式社团检测算法。该算法利用各节点相遇历史数据对一定时间内该节点与其他节点的累积相遇持续时间与相遇次数的均值进行计算，并作为动态阈值确定各节点的朋友集合。各节点在相遇时交换各自的朋友集合信息用于构建本地关系图，根据本地关系图进行多社团检测。基于实验数据的仿真结果表明：动态分布式社团检测算法能反映节点间关系的变化，并且能够进行多社团检测，更适用于动态变化的移动容迟网络环境。

参考文献：

[1] Su J, Scott J, Hui P, et al. Haggle: Seamless net working for mobile applications[C]. Proceedings of the 2007 UbiComp,2007: 391-408.

[2] Hui P, Chaintreau A, Gass R, et al. Pocket switched net- works and human mobility in con ference environments[C]. Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, 2005: 244-251.

[3] Hui P, Yoneki E, Chan S, et al. Distributed community de- tection in delay tolerant networks[C]. Pro ceedings of the 2nd ACM/IEEE international workshop on Mobility in the e- volving internet architecture, 2007: 1-8.

[4] Herbiet G-H, Bouvry P. SHARC: Community-based parti-tioning for mobile ad hoc networks using neighborhood si- milarity[C]. Proceedings of the 2010 IEEE International Sym posium on World of Wireless Mobile and Multimedia Net- works (WoWMoM 2010), 2010:1-9, .

[5] Hu T, Wenning B-L, Grg C, et al. Statistical Analysis of Contact Patterns between Human-carried Mobile Devices [C]. Proceedings of the 4th International Conference on Mo- bile Networks and Management (MONAMI 2012), 2012: 244-257.

[6] Nguyen N P, Dinh T N, Tokala S, et al. Overlapping com- munities in dynamic networks: their detection and mobile applications[C]. Proceedings of the 17th annual international conference on Mobile computing and networking (Mobi- Com ´11), 2011: 85-96.

[7] Ker?nen A, Ott J, Krkkinen T. The ONE simulator for DTN protocol evaluation[C]. Proceedings of the 2nd International Conference on Simulation Tools and Techniques(Simutools ´09), 2009: 1-10.

（责任编辑 王雯）