面向负载均衡的并行分布式重叠社区质量指标计算的研究

论文摘要

真实世界的网络例如社交网络,存在重叠社区结构。社区结构将网络中的顶点划分为多个不同的组,一个组即是一个社区。当网络中一个顶点可以属于多个社区时,该社区结构即是重叠社区。通过挖掘复杂网络中的重叠社区,我们可以发现网络中隐藏而又有意义的属性和结构。不同的重叠社区发现算法挖掘到的社区结构自然不同,因此使用重叠社区质量指标来衡量相应算法的有效性是非常有必要的。随着大数据时代的到来和数据规模的快速增长,大规模网络中的重叠社区得到巨大的增长。然而,计算指标的高度复杂性对现有的串行算法提出了巨大的挑战,同时集群中节点之间的数据划分对并行分布式算法的性能有关键性的影响。现有的串行算法计算重叠社区指标的性能有待提高,因此本论文设计了一种用于重叠社区质量指标计算的负载均衡的并行分布式算法。本文首先分析了现有的计算两类重叠社区质量指标的算法,发现基于社区标签对计数算法具有更低的时间复杂度,但目前只有串行算法,因此提出了一种基于社区标签对计数并行分布式算法（简称P&D算法）。接着,通过分析指标计算特性发现,本文研究的两类指标均需要计算社区的交集大小,因此本文的P&D算法重复利用中间结果,同时计算出全部两类指标。然后,对现有的数据划分策略进行了分析归纳,并针对重叠社区质量指标计算提出了一种基于负载预估的贪心（Greedy-based）划分策略,以此来均衡每个节点间的负载。最后,本文利用五个真实大规模网络数据集进行了实验,对本文提出的P&D算法和数据划分策略进行验证。实验结果证明,相对于现有的Hash-based和Range-based的数据划分策略,本文提出的基于负载预估的贪心划分策略在内存、通信和CPU负载分布以及总体执行时间上均获得较优的表现。结果验证了本文提出的Greedy-based数据划分策略相比现有的策略,在并行分布式计算重叠社区质量指标上能更好地均衡节点间的负载。同时,P&D算法在执行时间、加速比和可扩展性上相比现有串行算法（包括Clubmark和Mutual3）的性能有更好的表现。结果表明,本文提出的P&D算法比串行算法在执行时间上获得了10.7%89.4%的提升,并实现了1.12到9.43倍的加速。

论文目录

文章来源

类型: 硕士论文

作者: 吴远诗

导师: 冯禹洪

关键词: 重叠社区质量指标,并行分布式计算,负载均衡,数据划分

来源: 深圳大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 深圳大学

分类号: O157.5;TP301.6

总页数: 64

文件大小: 4891K

下载量: 6

相关论文文献

• [1].功能安全硬件指标计算的实践[J]. 传动技术 2019(02)
• [2].刍议Excel办公软件在项目投资指标计算中的应用[J]. 绿色财会 2008(09)
• [3].1GHz系统放大器指标计算[J]. 有线电视技术 2013(04)
• [4].兼顾用户发展规律的负荷密度指标计算方法[J]. 供用电 2017(06)
• [5].关于经济增加值EVA指标计算的对比解读[J]. 农村经济与科技 2017(16)
• [6].管道效率对反平衡法煤耗率指标计算的影响分析[J]. 热力发电 2009(06)
• [7].基于无人机影像的城市规划指标计算[J]. 测绘与空间地理信息 2017(08)
• [8].EVA指标计算中资本成本的确定方法探析[J]. 中国市场 2011(13)
• [9].基于小波变换的信号奇异度指标计算方法[J]. 探测与控制学报 2012(06)
• [10].基于变工况运行的泵能耗指标计算方法[J]. 农业工程学报 2009(03)
• [11].“八大资产净额”项目对财务报表有关指标计算的影响[J]. 科技创业月刊 2008(10)
• [12].三网融合光纤到户技术选型和指标计算[J]. 中国有线电视 2015(02)
• [13].浅谈整车平台通用化率指标计算方法及应用[J]. 汽车实用技术 2020(14)
• [14].浅谈周转率指标计算的几点问题[J]. 中国市场 2019(31)
• [15].财务分析的大历史观:提出与解读[J]. 企业技术开发 2016(04)
• [16].智慧城市评估系统建设研究[J]. 智能建筑与智慧城市 2020(09)
• [17].让督导评估更加科学精准[J]. 当代教育家 2015(11)
• [18].一种用于可靠指标计算的SCE-RI算法[J]. 河南理工大学学报(自然科学版) 2016(01)
• [19].大连地区“被动房”应用学习浅谈[J]. 科技创新与应用 2017(30)
• [20].论工业经济效益综合指数[J]. 现代商贸工业 2011(24)
• [21].基于Excel的投资项目财务动态指标计算[J]. 绿色财会 2009(04)
• [22].基于公交IC卡信息的城市公交满载率指标计算方法[J]. 交通运输研究 2019(05)
• [23].燃气蒸汽联合循环热电联产机组供热比指标计算方法的探究[J]. 上海节能 2018(03)
• [24].2-正n边形的旋转排列计数的轮换指标计算[J]. 贵州师范大学学报(自然科学版) 2015(06)
• [25].2014年1—12月全国铁路主要品类货物送量指标[J]. 铁道货运 2015(02)
• [26].基于电气化铁路的负荷研究分析[J]. 山西科技 2013(04)
• [27].天量囤地揭穿“土地短缺”谎言[J]. 法人 2010(12)
• [28].外贸依存度指标计算方法探讨[J]. 统计科学与实践 2010(12)
• [29].浅析新会计准则下的企业设定受益计划[J]. 财经界(学术版) 2016(14)
• [30].广州市国土资源和规划委员会关于印发广州市规划管理容积率指标计算办法的通知[J]. 广州市人民政府公报 2018(35)

标签：重叠社区质量指标论文;  并行分布式计算论文;  负载均衡论文;  数据划分论文;