基于多层次随机梯度下降的大规模图布局算法  

Large-scale graph layout algorithm based on multi-level stochastic gradient descent

作　　者：周颖鑫 李学俊[1] 吴亚东 张红英[2] 王娇[2] 张秋梅 王桂娟 Zhou Yingxin;Li Xuejun;Wu Yadong;Zhang Hongying;Wang Jiao;Zhang Qiumei;Wang Guijuan(School of Computer Science&Technology,Southwest University of Science&Technology,Mianyang Sichuan 621000,China;School of Information Engineering,Southwest University of Science&Technology,Mianyang Sichuan 621000,China;School of Computer Science&Engineering,Sichuan University of Science&Engineering,Zigong Sichuan 643000,China)

机构地区：[1]西南科技大学计算机科学与技术学院,四川绵阳621000 [2]西南科技大学信息工程学院,四川绵阳621000 [3]四川轻化工大学计算机科学与工程学院,四川自贡643000

出　　处：《计算机应用研究》2024年第11期3394-3400,共7页Application Research of Computers

基　　金：四川省自然科学基金资助项目(24NSFSC5113)。

摘　　要：大规模图布局问题是图可视化领域研究热点之一。应力布局模型在保持全局布局结构方面表现出色,然而其求解速度却不及弹簧电荷模型,且局部布局质量也有所欠缺。在维持全局结构稳定条件下,为提高应力模型求解大规模图时的布局速度、改进布局局部结构表达,提出了一个新的多层次随机梯度下降图布局模型。首先利用基于邻居结构的图压缩合并算法生成层次图结构,再使用节点最优放置算法初始化节点坐标。最后利用融合了节点正负样本的随机梯度下降算法细化布局,改进局部布局质量。同时多层次方法也有效提高了布局速度。在30个不同规模的数据集上与现有布局模型进行对比实验,从布局计算效率、布局质量以及可视化效果三个方面证明了该方法的有效性。Large-scale graph layout remains a prominent focus in graph visualization research.While the stress model excels in representing global structure,its speed lags behind the spring-electric model,and its local structure quality is suboptimal.This paper proposed a graph layout algorithm,aimed at enhancing the efficiency of layout while preserving global structure and improving local quality.The model first utilized graph compression based on neighbor structure to generate a hierarchical graph structure,and then used the node optimal placement algorithm to initialize the node coordinates.Next,it improved the local quality of layout using a SGD layout algorithm based on positive and negative samples,and further enhanced the layout speed through multi-level algorithm.Finally,comparative experiments with existing layout models on 30 datasets of different scales demonstrate the effectiveness of the proposed model in terms of efficiency,layout quality and visualization.

关 键 词：大规模图布局 应力模型 随机梯度下降 多层次布局 图可视化 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]