基于分布式系统的网络社区探测研究与实现

发布时间：2020-08-03 08:48

【摘要】：近年来,随着在线社交网络的流行及智能移动终端设备的普及,越来越多的人将在线社交作为一种重要的生活方式,在线社交网络的数据量也愈发庞大。社区探测作为社交网络研究的一个重要方向,在研究网络结构特点、分析用户关系、探索消息传播方式及掌握舆论动向方面有重要意义。由于单机的硬件配置升级存在边际效应,以及一些传统的社区探测算法在处理超大数据时的限制,使得分布式计算模型成为处理大型社交网络数据的一个优秀解决方案。现有的分布式网络社区探测算法,在实现大型网络数据的社区探测的同时,会产生社区质量下降的问题,还有一部分算法稳定性不强,对数据节点重新排序编号会大幅影响计算结果的质量。本文在研究现有的分布式社区探测算法的基础上,提出了一种基于标签传播分区的优化分布式Louvain算法-LPPDLA算法,并将算法应用于社区探测系统。本文的主要工作为以下几点:(1)分析分布式社区探测的需求和现有分布式社区探测算法,提出三点改进:1、使用VF算法简化图数据的节点分布,缩短运行时间以优化社区探测计算效率;2、将大小约束的标签传播算法应用于图分区,提高算法稳定性;3、以虚节点增强分区之间的关联关系,并制定节点跨分区移动规则。(2)将Louvain算法结合以上三个改进,在MapReduce分布式计算模型上提出LPPDLA算法。并使用LPPDLA算法对公共数据进行社区探测计算,以验证算法的有效性及评估计算获得的社区质量。(3)设计并实现一个社区探测系统,以可视化界面提供网络数据采集功能,图文件读取功能,可以使用LPPDLA算法对网络图数据进行分布式社区探测,并以展示探测结果。通过实验对比分析,本论文提出的LPPDLA算法可以在较短时间内准确地对大型图数据进行社区探测,并且可以有效降低分布式社区探测的质量衰减问题,使社区质量达到原始Louvain算法同等水平。
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP393.09
【图文】：

网络图,标签,节点,内部边

该节点的标签更新为这个最大的标签，同时随机地断开连接，完成一次标签的传逡逑播。随着标签的传播，密集连接的节点会迅速的形成一个相同标签的组合体（如逡逑图２－１所示）。在标签传播的初期，网络图中可能会形成多个这种集合体（称为逡逑共识小组），他们的标签将作为影响力较大标签向外辐射，以获得更多的节点加逡逑１０逡逑

社区,节点,虚节点,模块度

由此得出的跨分区移动规则为：当本分区内的节点因为模块度增加而需要向逡逑虚节点所在的社区移动时，需要额外对比该节点与虚节点的度。若该节点的度小逡逑于虚节点的度，则将节点移动至虚节点所在的社区；否则不移动。如图３－４的（ｂ）逡逑所示，节点ｉ与节点ｊ分别处于两个分区中，互为对方分区的虚节点。假设节点逡逑ｉ的度小于节点ｊ的度，贝``计算中，节点ｉ会移动至节点ｊ所在的社区，而节点逡逑ｊ保持不动，这样就避免了社区互换问题。逡逑另一个跨区间移动产生的问题是描述滞后现象。如图３－５所示，节点ｉ属于逡逑分Ｋ邋Ｃ，节点ｊ与节点ｋ属于另一个分区Ｄ。分区Ｄ在执行本地移动的过程中节逡逑点ｊ邋Ｗ模块度增加而移动到丫节点ｋ所在的社区中，而节点Ｃ因为消总的滞后性，逡逑不知道节点ｊ已经发生移动

节点,社区,虚节点,模块度

社区互换问题的解决方案即为节点在分区间的移动增加一个限制条件，使得逡逑只有一方的节点产生移动，这样就能保证两个节点聚集到同一个社区中。本文以逡逑节点的度作为评判标准，节点的度为节点直连的所有边的权重之和，度大的节点逡逑相对其周边节点更具有中心性，因此向度更大的节点移动更为合理。逡逑由此得出的跨分区移动规则为：当本分区内的节点因为模块度增加而需要向逡逑虚节点所在的社区移动时，需要额外对比该节点与虚节点的度。若该节点的度小逡逑于虚节点的度，则将节点移动至虚节点所在的社区；否则不移动。如图３－４的（ｂ）逡逑所示，节点ｉ与节点ｊ分别处于两个分区中，互为对方分区的虚节点。假设节点逡逑ｉ的度小于节点ｊ的度，贝``计算中，节点ｉ会移动至节点ｊ所在的社区，而节点逡逑ｊ保持不动，这样就避免了社区互换问题。逡逑另一个跨区间移动产生的问题是描述滞后现象。如图３－５所示，节点ｉ属于逡逑分Ｋ邋Ｃ，节点ｊ与节点ｋ属于另一个分区Ｄ。分区Ｄ在执行本地移动的过程中节逡逑点ｊ邋Ｗ模块度增加而移动到丫节点ｋ所在的社区中，而节点Ｃ因为消总的滞后性，逡逑不知道节点ｊ已经发生移动，所以扔按照原先的情况进行计兑。到收缩阶段时，逡逑节点ｉ进入分丨ＸＤ中，因为节点ｊ放弃了原先的社区，导致广节点ｉ仍旧是－个逡逑独立社区的取独节点，而没有和节点ｊ及节点ｋ聚合在一起。逡逑

【参考文献】