大图结构特征对划分效果的影响
来源：计算机应用杂志2018年第1期北京时间：
作者：罗晓霞, 司丰玮, 罗香玉
单位：西安科技大学 计算机科学与技术学院, 西安 710054
摘要：针对大图结构特征如何影响划分效果这一问题，提出一种通过顶点度分布特征来描述大图结构特征的方法。首先，基于真实的图数据产生若干顶点数和边数相同、但结构特征不同的仿真数据集，通过实验计算真实图与仿真图之间的相似度，证明该方法对描述真实大图结构特征的有效性。然后，通过Hash和点对交换划分算法，验证图结构特征与划分效果之间的关系。当点对交换划分算法执行到5万次时，划分一个有6301个顶点和20777条边的真实图其交叉边数比Hash划分算法降低了54.32%，划分仿真图数据集中结构特征差异明显的两个图时，交叉边数分别为6233和316。实验结果表明，点对交换划分算法能够减少交叉边数，图的顶点度分布差异越大，划分后交叉边数越少，划分效果越好，因此大图结构特征影响其划分效果，这为建立图的结构特征与划分效果之间的关系模型研究奠定了基础。
关键词：大图分布式处理,大图划分,图结构特征,负载均衡,交叉边
基金资助：国家自然科学基金资助项目（41472234）；陕西省教育厅专项科学研究计划项目（15JK1468）；西安科技大学培育基金资助项目（201633）。
