基于标签传播与沙丘猫群优化的属性图划分算法

doi:10.19678/j.issn.1000-3428.0069650

摘要/Abstract

摘要：

图在社交网络、通信网络等领域有着广泛应用，而且随着图规模日益增长，分布式图处理系统成为处理、分析大规模图数据的主要手段。图划分算法是此类系统的基础。目前提出的图划分算法通常假定顶点和边无属性，在对属性图进行划分时，易出现负载不均衡的问题。为此，将负载均衡分为图规模均衡和存储容量均衡，将属性图划分问题建模为一个带约束的单目标优化问题，进而提出一种基于标签传播和沙丘猫群优化(SCSO)的属性图划分算法LSPGP。该算法首先利用标签传播算法(LPA)将图进行均匀划分，使划分结果达到图规模和存储容量上的负载均衡；然后改进SCSO算法，使其能够求解组合优化问题，并基于改进的SCSO算法求解最优顶点迁移策略，以优化分区质量，在负载均衡的基础上达到最小化割边率的目标。实验结果显示，相较于基线算法，所提算法在存储容量负载均衡率(VLF)上最多降低了33百分点，同时在割边率和图规模负载均衡率(SLF)方面与基线算法的差距均保持在9百分点以内。此外，该算法在真实属性图结构上也展现出了良好的可扩展性。

关键词: 图划分, 属性图, 负载均衡, 标签传播, 沙丘猫群优化算法

Abstract:

The graphs are widely applied in social networks and communication networks, and the distributed graph processing systems have been used more frequently in processing and analyzing large-scale graphs with the increase of the scale of the graphs. The graph partitioning is the basis of these systems. The existing graph partitioning algorithms usually lead to load unbalance for property graphs, because they assume that the edges and vertices have no attributes. Therefore, this paper considers two kinds of load balance factors: the graph-size load and the storage load balance, and it formulates the property graph partitioning problem as a constrained single-objective optimization problem. In further, it proposes a large-scale property graph partition algorithm based on label propagation and Sand Cat Swarm Optimization (SCSO), named LSPGP. The proposed algorithm partitions the graph by Label Propagation Algorithm (LPA) to achieve graph-size and storage balance in first. Secondly, the SCSO algorithm is improved to enable it to solve combinatorial optimization problems, and it is applied to guide the vertices migration to optimize the partition result. The experimental results show that, compared with the baseline algorithm, the proposed algorithm achieves a maximum reduction of 33 percentage points in Volume Load Balancing Factor (VLF), while maintaining a gap of less than 9 percentage points with the baseline algorithm in both Scale Load Balancing Factor (SLF) and graph size load balance ratio. Furthermore, the algorithm also demonstrates good scalability on real-world property graph structures.

Key words: graph partitioning, property graph, load balance, label propagation, Sand Cat Swarm Optimization (SCSO) algorithm

崔焕庆, 吴一凡, 董柯桢, 周升庆. 基于标签传播与沙丘猫群优化的属性图划分算法[J]. 计算机工程, 2025, 51(12): 180-188.

CUI Huanqing, WU Yifan, DONG Kezhen, ZHOU Shengqing. Property Graph Partition Algorithm Based on Label Propagation and Sand Cat Swarm Optimization[J]. Computer Engineering, 2025, 51(12): 180-188.

https://www.ecice06.com/CN/Y2025/V51/I12/180

图/表 12

图1 SCSO算法的流程图

Fig.1 Flowchart of SCSO algorithm

图2 LSPGP算法的流程图

Fig.2 Flowchart of LSPGP algorithm

图3 图规模负载均衡率对比(幂律图)

Fig.3 Comparison of SLF (power-law graph)

图4 图规模负载均衡率对比(非幂律图)

Fig.4 Comparison of SLF (non-power-law graph)

图5 图存储容量负载均衡率对比(幂律图)

Fig.5 Comparison of VLF (power-law graph)

图6 图存储容量负载均衡率对比(非幂律图)

Fig.6 Comparison of VLF (non-power-law graph)

图7 参数α和β对图划分效果的影响

Fig.7 Impacts of α and β on graph partition effect

图8 算法的时间开销

Fig.8 Time overheads of algorithms

参考文献 29

1	RONG X Y, CUI H Q. Large-scale dynamic graph updating algorithm in distributed computing system[C]//Proceedings of the 2nd International Conference on Big Data Technologies. New York, USA: ACM Press, 2019: 248-251.
2	FAN W F , HE T , LAI L B , et al. GraphScope. Proceedings of the VLDB Endowment, 2021, 14 (12): 2879- 2892. doi: 10.14778/3476311.3476369
3	DAI G H , HUANG T H , CHI Y Z , et al. GraphH: a processing-in-memory architecture for large-scale graph processing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 38 (4): 640- 653. doi: 10.1109/TCAD.2018.2821565
4	GONZALEZ J E, LOW Y, GU H, et al. PowerGraph: distributed graph-parallel computation on natural graphs[C]//Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation. [S. l. ]: USENIX Association, 2012: 17-30.
5	GONZALEZ J E, XIN R S, DAVE A, et al. GraphX: graph processing in a distributed dataflow framework[C]//Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation. [S. l. ]: USENIX Association, 2014: 599-613.
6	GONG S F, ZHANG Y F, YU G. HBP: hotness balanced partition for prioritized iterative graph computations[C]//Proceedings of the IEEE 36th International Conference on Data Engineering (ICDE). Dallas, USA: IEEE Press, 2020: 1942-1945.
7	AKHREMTSEV Y , SANDERS P , SCHULZ C . High-quality shared-memory graph partitioning. IEEE Transactions on Parallel and Distributed Systems, 2020, 31 (11): 2710- 2722.
8	WANG L, XIAO Y H, SHAO B, et al. How to partition a billion-node graph[C]//Proceedings of the IEEE 30th International Conference on Data Engineering. Chicago, USA: IEEE Press, 2014: 568-579.
9	柳菁, 李琪. DisHAP: 基于层次亲和聚类的分布式大图划分算法. 电子学报, 2021, 49 (10): 2002- 2011.
	LIU J , LI Q . DisHAP: a distributed partition algorithm for large scale graphs based on hierarchical affinity clustering. Acta Electronica Sinica, 2021, 49 (10): 2002- 2011.
10	崔焕庆, 杨君三. 异构集群下基于标签传播的大规模图划分算法. 计算机工程与设计, 2023, 44 (5): 1400- 1404.
	CUI H Q , YANG J S . Label propagation based large-scale graph partitioning algorithm for heterogeneous clusters. Computer Engineering and Design, 2023, 44 (5): 1400- 1404.
11	LI M H , CUI H Q , ZHOU C N , et al. GAP: genetic algorithm based large-scale graph partition in heterogeneous cluster. IEEE Access, 2020, 8, 144197- 144204. doi: 10.1109/ACCESS.2020.3014351
12	ZHANG W, CHEN Y, DAI D. AKIN: a streaming graph partitioning algorithm for distributed graph storage systems[C]//Proceedings of the 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID). Washington D. C., USA: IEEE Press, 2018: 183-192.
13	SUN Z P , ZENG G S , DING C L , et al. A streaming graph partitioning method to achieve high cohesion and equilibrium via multiplayer repeated game. IEEE Transactions on Computational Social Systems, 2024, 11 (1): 803- 814. doi: 10.1109/TCSS.2022.3226230
14	ZENG Y Y , LI Y F , ZHOU X , et al. Efficient game theoretic approach to dynamic graph partitioning. Information Sciences, 2022, 606, 892- 909. doi: 10.1016/j.ins.2022.05.096
15	张明, 郭文康, 王海峰. 面向大规模动态图的异构图计算系统设计. 计算机工程, 2025, 51 (3): 197- 207. doi: 10.19678/j.issn.1000-3428.0068477
	ZHANG M , GUO W K , WANG H F . A heterogeneous graph computing system for large-scale dynamic graph. Computer Engineering, 2025, 51 (3): 197- 207. doi: 10.19678/j.issn.1000-3428.0068477
16	AZADE N, WILL H, ANNA G, et al. A deep learning framework for graph partitioning[C]//Proceedings of the 7th International Conference on Learning Representations. Washington D. C., USA: IEEE Press, 2019: 1-10.
17	GATTI A, HU Z, SMIDT T, et al. Deep learning and spectral embedding for graph partitioning[C]//Proceedings of SIAM Conference on Parallel Processing for Scientific Computing. [S. l. ]: Society for Industrial and Applied Mathematics, 2022: 25-36.
18	YANG Z X , SHI R Y , QUAN P , et al. Semi-supervised graph neural networks for graph partitioning problem. Procedia Computer Science, 2023, 221, 789- 796. doi: 10.1016/j.procs.2023.08.052
19	AYALL T A , LIU H W , ZHOU C J , et al. Graph computing systems and partitioning techniques: a survey. IEEE Access, 2022, 10, 118523- 118550. doi: 10.1109/ACCESS.2022.3219422
20	PETRONI F, QUERZONI L, DAUDJEE K, et al. HDRF: stream-based partitioning for power-law graphs[C]//Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. New York, USA: ACM Press, 2015: 243-252.
21	LI H , YUAN H , HUANG J B , et al. Group reassignment for dynamic edge partitioning. IEEE Transactions on Parallel and Distributed Systems, 2021, 32 (10): 2477- 2490. doi: 10.1109/TPDS.2021.3069292
22	LI Y B, LI C Y, ORGERIE A C, et al. WSGP: a window-based streaming graph partitioning approach[C]//Proceedings of the IEEE/ACM 21st International Symposium on Cluster, Cloud and Internet Computing (CCGrid). Melbourne, Australia: IEEE Press, 2021: 586-595.
23	张正康, 杨丹, 聂铁铮, 等. 基于图结构聚类的自监督学习疾病诊断方法. 计算机工程, 2024, 50 (7): 360- 371. doi: 10.19678/j.issn.1000-3428.0068187
	ZHANG Z K , YANG D , NIE T Z , et al. Self-supervised learning based on graph structural clustering for disease diagnosis method. Computer Engineering, 2024, 50 (7): 360- 371. doi: 10.19678/j.issn.1000-3428.0068187
24	HOGAN A , BLOMQVIST E , COCHEZ M , et al. Knowledge graphs. ACM Computing Surveys, 2022, 54 (4): 1- 37.
25	HE C B , LIU S Y , ZHANG L , et al. A fuzzy clustering based method for attributed graph partitioning. Journal of Ambient Intelligence and Humanized Computing, 2019, 10 (9): 3399- 3407. doi: 10.1007/s12652-018-1054-2
26	SAKOUHI C , KHALDI A , BEN G H . Hammer lightweight graph partitioner based on graph data volumes. Journal of Parallel and Distributed Computing, 2021, 158, 16- 28. doi: 10.1016/j.jpdc.2021.07.008
27	SEYYEDABBASI A , KIANI F . Sand cat swarm optimization: a nature-inspired algorithm to solve global optimization problems. Engineering with Computers, 2023, 39 (4): 2627- 2651. doi: 10.1007/s00366-022-01604-x
28	LESKOVEC J, KREVL A. SNAP datasets: Stanford large network dataset collection[EB/OL]. [2024-01-02]. https://snap.stanford.edu/data/.
29	HE C, FEI X, LI H, et al. A multi-view clustering method for community discovery integrating links and tags[C]//Proceedings of the IEEE 14th International Conference on e-Business Engineering. Shanghai, China: IEEE Press, 2017: 23-30.

[1]	黄尧, 柴志雷. 基于通信和拓扑感知的SNN分区与映射算法[J]. 计算机工程, 2025, 51(5): 219-228.
[2]	魏德宾, 乔维维, 张怡. 基于麻雀搜索算法的软件定义卫星网络控制器部署[J]. 计算机工程, 2025, 51(3): 172-179.
[3]	张明, 郭文康, 王海峰. 面向大规模动态图的异构图计算系统设计[J]. 计算机工程, 2025, 51(3): 197-207.
[4]	聂雷, 胡字升, 鲍海洲. 基于RSU辅助和自适应分簇的异构车载网络选择方法[J]. 计算机工程, 2025, 51(3): 162-171.
[5]	游奕桁, 王鑫, 马梦露, 王惠. 一种面向大规模知识图谱的混合存储方案[J]. 计算机工程, 2025, 51(12): 43-55.
[6]	朱亚州, 杜平川, 柴志雷. 基于Kubernetes的异构任务调度方法[J]. 计算机工程, 2025, 51(12): 337-345.
[7]	张正康, 杨丹, 聂铁铮, 寇月. 基于图结构聚类的自监督学习疾病诊断方法[J]. 计算机工程, 2024, 50(7): 360-371.
[8]	莫少聪, 陈庆锋, 谢泽, 刘春雨, 邱俊铼. 基于动态图注意力与标签传播的实体对齐[J]. 计算机工程, 2024, 50(4): 150-159.
[9]	彭世明, 林士飏, 贾硕, 杨苗会. 基于负载预测的多目标优化任务卸载策略[J]. 计算机工程, 2024, 50(1): 206-215.
[10]	刘向举, 赵犇, 方贤进, 徐杨洋. SDN中基于过程优化的动态负载均衡策略[J]. 计算机工程, 2023, 49(8): 137-145.
[11]	白明昌. 基于折叠路径聚合的属性网络节点嵌入方法[J]. 计算机工程, 2023, 49(7): 76-84.
[12]	高小方, 原玉梁, 温静, 白雪飞. 面向相交多流形聚类的标签传播算法[J]. 计算机工程, 2023, 49(6): 90-98.
[13]	王晓峰, 于卓, 赵健, 曹泽轩. 大规模图例的最大团问题算法分析[J]. 计算机工程, 2022, 48(6): 182-192,199.
[14]	王奎宇, 宋晓勤, 缪娟娟, 张昕婷, 雷磊. 基于SDN的高性能QoS保障低轨道卫星星间路由算法[J]. 计算机工程, 2022, 48(5): 185-190,199.
[15]	孙福禄, 王宇嘉, 刘子怡. 基于节点引力与鱼记忆的社区检测算法[J]. 计算机工程, 2022, 48(5): 104-111.

选择文件类型/文献管理软件名称

选择包含的内容