大图结构特征对划分效果的影响

• 作者: 司丰玮 罗晓霞 罗香玉
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 大图分布式处理 大图划分 图结构特征 负载均衡 交叉边
• 年，卷（期）: 2018,（1）
• 所属期刊栏目: 2017年全国开放式分布与并行计算学术年会(DPCS 2017)论文
• 页码范围: 1-5
• 页数: 5页
• 分类号: TP393.027
• 字数: 5050字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2017071967

摘要

针对大图结构特征如何影响划分效果这一问题,提出一种通过顶点度分布特征来描述大图结构特征的方法.首先,基于真实的图数据产生若干顶点数和边数相同、但结构特征不同的仿真数据集,通过实验计算真实图与仿真图之间的相似度,证明该方法对描述真实大图结构特征的有效性.然后,通过Hash和点对交换划分算法,验证图结构特征与划分效果之间的关系.当点对交换划分算法执行到5万次时,划分一个有6301个顶点和20777条边的真实图其交叉边数比Hash划分算法降低了54.32％,划分仿真图数据集中结构特征差异明显的两个图时,交叉边数分别为6233和316.实验结果表明,点对交换划分算法能够减少交叉边数,图的顶点度分布差异越大,划分后交叉边数越少,划分效果越好,因此大图结构特征影响其划分效果,这为建立图的结构特征与划分效果之间的关系模型研究奠定了基础.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	罗晓霞	西安科技大学计算机科学与技术学院	30	180	8.0	11.0
2	罗香玉	西安科技大学计算机科学与技术学院	13	16	2.0	3.0
3	司丰玮	西安科技大学计算机科学与技术学院	1	1	1.0	1.0