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

doi:10.11772/j.issn.1001-9081.2017071967

计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 1-5.DOI: 10.11772/j.issn.1001-9081.2017071967

• 2017年全国开放式分布与并行计算学术年会(DPCS 2017)论文 • 下一篇

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

罗晓霞, 司丰玮, 罗香玉

西安科技大学计算机科学与技术学院, 西安 710054

收稿日期:2017-08-11 修回日期:2017-08-23 出版日期:2018-01-10 发布日期:2018-01-22
通讯作者: 罗香玉
作者简介:罗晓霞(1964-),女,陕西扶风人,教授,主要研究方向:大数据与云计算、软件工程、分布式计算;司丰玮(1992-),男,甘肃兰州人,硕士研究生,CCF会员,主要研究方向:分布式存储、图的划分算法;罗香玉(1984-),女,河北宁晋人,讲师,博士,CCF会员,主要研究方向:分布式存储、大数据。
基金资助:
国家自然科学基金资助项目（41472234）；陕西省教育厅专项科学研究计划项目（15JK1468）；西安科技大学培育基金资助项目（201633）。

Effects of large-scale graph structural feature on partitioning quality

LUO Xiaoxia, SI Fengwei, LUO Xiangyu

College of Computer Science and Technology, Xi'an University of Science and Technology, Xi'an Shaanxi 710054, China

Received:2017-08-11 Revised:2017-08-23 Online:2018-01-10 Published:2018-01-22
Supported by:
This work is partially supported by the National Natural Science Foundation of China (41472234), the Scientific Research Program of Shaanxi Provincial Education Department (15JK1468), the Xi'an University of Science and Technology Foundation for Fostering Talents (201633).

摘要/Abstract

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

关键词: 大图分布式处理, 大图划分, 图结构特征, 负载均衡, 交叉边

Abstract: Focusing on how the large-scale graphs' structural features affect the partitioning quality, through the structural features of vertex degree, a method of describing large-scale graphs' structural features was proposed. Firstly, based on the real graph data, a several simulation datasets with the same numbers of vertices and edges but different structural features were generated. Through the similarity between the real graph and the simulation graph calculated by the proposed algorithm, the validity of the method for describing the structural features of the real large-scale graphs was verified. Secondly, the relationship between the structural features of the graph and the quality of partitioning was verified by the Hash algorithm and point-to-point exchange algorithm. When the point-to-point algorithm was performed for 50000 times, the number of crossed edges of a real graph with 6301 vertexes and 20777 edges was reduced by 54.32% compared with the Hash partitioning algorithm. When the two graphs with entirely different structural features in the simulation data were partitioned, the number of crossed edges were 6233 and 316 respectively. The experimental results show that the point-to-point algorithm can reduce the number of crossed edges. The larger the difference of the vertex degree distribution and the smaller the number of crossed edges are, the better the partitioning quality is. Therefore, the structural features of large graphs affect the partitioning effect, which lays the foundation for the model investigation of the relationship between structural features and partitioning quality.

Key words: distributed processing of large-scale graph, partitioning of large-scale graph, graph structural feature, load balance, crossed edge

中图分类号:

TP393.027

罗晓霞, 司丰玮, 罗香玉. 大图结构特征对划分效果的影响[J]. 计算机应用, 2018, 38(1): 1-5.

LUO Xiaoxia, SI Fengwei, LUO Xiangyu. Effects of large-scale graph structural feature on partitioning quality[J]. Journal of Computer Applications, 2018, 38(1): 1-5.

参考文献

[1] JOHANNES F M. Partitioning of VLSI circuits and systems[C]//DAC'96:Proceedings of the 33rd Annual Design Automation Conference. New York:ACM, 1996:83-87.
[2] MEYERHENKE H, SANDERS P, SCHULZ C. Parallel graph partitioning for complex networks[C]//Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium. Piscataway, NJ:IEEE, 2015:1055-1064.
[3] KARYPIS G, KUMAR V. Parallel multilevel k-way partitioning scheme for irregular graphs[J]. Journal of Parallel & Distributed Computing, 1999, 41(2):278-300.
[4] HENDRICKSON B, LELAND R. An improved spectral graph partitioning algorithm for mapping parallel computations[J]. SIAM Journal on Scientific Computing, 1995, 16(2):452-469.
[5] VAQUERO L, CUADRADO F, LOGOTHETIS D, et al. Adaptive partitioning for large-scale dynamic graphs[C]//ICDCS 2014:Proceedings of the 2014 IEEE 34th International Conference on Distributed Computing Systems. Piscataway, NJ:IEEE, 2014:144-153.
[6] HUANG J, ABADI D J. Leopard:lightweight edge-oriented partitioning and replication for dynamic graphs[J]. Proceedings of the VLDB Endowment, 2016, 9(7):540-551.
[7] MAYER C, TARIQ M A, LI C, et al. GrapH:heterogeneity-aware graph computation with adaptive partitioning[C]//ICDCS 2016:Proceedings of the 36th IEEE International Conference on Distributed Computing Systems. Piscataway, NJ:IEEE, 2016:118-128.
[8] GAREY M R, JOHNSON D S, STOCKMEYER L. Some simplified NP-complete graph problems[J]. Theoretical Computer Science, 1976, 1(3):237-267.
[9] 郑丽丽.图划分算法综述[J].科技信息,2014(4):145-145.(ZHEN L L. A survey of graph partitioning algorithms[J]. Science and Technology Information, 2014(4):145-145.)
[10] BARNARD S T, SIMON H D. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems[J]. Concurrency and Computation Practice and Experience, 2010, 6(2):101-117.
[11] KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 49(2):291-307.
[12] FIDUCCIA C M, MATTHEYSES R M. A linear-time heuristic for improving network partitions[C]//25 years of DAC Papers on Twenty-Five Years of Electronic Design Automation. New York:ACM, 1988:241-247.
[13] FARSHBAF M, FEIZI-DERAKHSHI M R. Multi-objective optimization of graph partitioning using genetic algorithms[C]//Proceedings of the 3rd International Conference on Advanced Engineering Computing and Applications in Sciences. Washington, DC:IEEE Computer Society, 2009:1-6.
[14] BOULIF M. Genetic algorithm encoding representations for graph partitioning problems[C]//Proceedings of the 2010 International Conference on Machine and Web Intelligence. Piscataway, NJ:IEEE, 2010:288-291.
[15] ROLLAND E, PIRKUL H, GLOVER F. Tabu search for graph partitioning[J]. Annals of Operations Research, 1996, 63(2):209-232.
[16] AARTS E, KORST J, MICHIELS W. Simulated annealing[J]. Metaheuristic Procedures for Training Neural Networks, 2007, 36(3):187-210.
[17] 翟明清.图的结构参数与特征值[D].上海:华东师范大学,2010:1-5.(ZHAI M Q. Structure variables and eigenvalues of graphs[D]. Shanghai:East China Normal University, 2010:1-5.)
[18] FALLAT S M, KIRKLAND S, PATI S. On graphs with algebraic connectivity equal to minimum edge density[J]. Linear Algebra & Its Applications, 2003, 373:31-50.
[19] NIKIFOROV V. Note:Eigenvalue problems of Nordhaus-Gaddum type[J]. Discrete Mathematics, 2014, 307(6):774-780.
[20] LIU H, LU M, TIAN F. On the spectral radius of unicyclic graphs with fixed diameter[J]. Linear Algebra & Its Applications, 2007, 420(2/3):449-457.
[21] KHARAGHANI H, TAYFEH-REZAIE B. On the energy of (0,1)-matrices[J]. Linear Algebra & Its Applications, 2008, 429(8):2046-2051.

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

Effects of large-scale graph structural feature on partitioning quality

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[2]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[3]	李翠, 陈庆奎. 基于DPDK并行通信的动态监控模型[J]. 计算机应用, 2020, 40(2): 335-341.
[4]	李祝红, 赵灿明, 闫龙, 张信明. 智能电网中电力线通信网络负载均衡的机会路由协议[J]. 计算机应用, 2019, 39(3): 812-816.
[5]	王泽武, 孙磊, 郭松辉, 孙瑞辰. 密码云中基于熵权评价的虚拟密码机调度方法[J]. 计算机应用, 2018, 38(5): 1353-1359.
[6]	鲁亮, 于炯, 卞琛, 英昌甜, 师康利, 蒲勇霖. Storm环境下基于权重的任务调度算法[J]. 计算机应用, 2018, 38(3): 699-706.
[7]	樊自甫, 周凯恒, 姚杰. 基于博弈论的SDN主控制器重选机制[J]. 计算机应用, 2018, 38(3): 776-779.
[8]	耿海军, 刘洁琦. 基于逐跳计算的分布式负载均衡算法[J]. 计算机应用, 2018, 38(12): 3524-3528.
[9]	徐力杰. 非对称占空比传感网中的广播能效优化算法[J]. 计算机应用, 2018, 38(11): 3275-3281.
[10]	张健, 汪洋, 刘丹丹. 分布式一致性算法Yac[J]. 计算机应用, 2017, 37(9): 2524-2530.
[11]	周渭博, 钟勇, 李振东. 基于存储熵的存储负载均衡算法[J]. 计算机应用, 2017, 37(8): 2209-2213.
[12]	李强, 刘晓峰. 基于Hopfield神经网络的云存储负载均衡策略[J]. 计算机应用, 2017, 37(8): 2214-2217.
[13]	李祝红, 赵灿明, 周方, 张信明. 电力通信网络中高效的OSPF流量负载均衡协议[J]. 计算机应用, 2017, 37(7): 1873-1876.
[14]	韩虎, 王鹏, 程琨, 李波. 基于多尺度量子谐振子算法的云计算任务调度[J]. 计算机应用, 2017, 37(7): 1888-1892.
[15]	刘必果, 束永安, 付应辉. 基于多目标优化的软件定义网络负载均衡方案[J]. 计算机应用, 2017, 37(6): 1555-1559.