基于用户样例的图布局定制化调整

doi:10.11996/JG.j.2095-302X.2025020402

图学学报 ›› 2025, Vol. 46 ›› Issue (2): 402-414.DOI: 10.11996/JG.j.2095-302X.2025020402

• 计算机图形学与虚拟现实 • 上一篇下一篇

基于用户样例的图布局定制化调整

陈俊旭¹(), 吴子梁¹, 朱闽峰², 陈为¹()

1.浙江大学计算机辅助设计与图形系统全国重点实验室，浙江杭州 310058
2.浙江大学软件学院，浙江杭州 310058

收稿日期:2024-08-23 接受日期:2024-11-07 出版日期:2025-04-30 发布日期:2025-04-24
通讯作者:陈为(1976-)，男，教授，博士。主要研究方向为可视化、可视分析等。E-mail：chenvis@zju.edu.cn
第一作者:陈俊旭(1999-)，男，硕士研究生。主要研究方向为可视化与可视分析。E-mail：chenjx_work@163.com
基金资助:
国家自然科学基金重点项目(62132017);浙江省领雁研发攻关计划(2024C01167);浙江省自然科学基金重大项目(LD24F020011)

Graph layout customization based on user-specified examples

CHEN Junxu¹(), WU Ziliang¹, ZHU Minfeng², CHEN Wei¹()

1. State Key Laboratory of CAD&CG, Zhejiang University, Hangzhou Zhejiang 310058, China
2. School of Software Technology, Zhejiang University, Hangzhou Zhejiang 310058, China

Received:2024-08-23 Accepted:2024-11-07 Published:2025-04-30 Online:2025-04-24
First author：CHEN Junxu (1999-), master student. His main research interests cover visualization and visual analytics. E-mail：chenjx_work@163.com
Supported by:
National Natural Science Foundation of China Key Project(62132017);“Pioneer”and“Leading Goose”Research and Development Program of Zhejiang(2024C01167);Major Project of the Natural Science Foundation of Zhejiang Province(LD24F020011)

摘要/Abstract

摘要：

传统的自动图布局算法虽然能保证图布局的整体美学特性，但却无法生成定制化的图布局。在不同的实际应用场景下，用户常常需要对自动布局后的图进行调整以满足具体的需求。现有的图布局调整主要分为2类：节点级别的手动调整和基于约束的图布局，前者非常耗时且枯燥，后者常常缺乏灵活性。为此，提出了一种基于用户样例的图布局定制化调整方法，主要基于图混合理论将样例图的属性和特点混合到源图上，从而实现灵活、高效的图布局定制化调整。首先对样例进行预处理，然后设计2种映射样例和6种映射模式来生成样例和源图之间节点级的映射矩阵，并使用该映射矩阵将样例图向源图对齐，最后按照一定比例进行混合得到定制化调整的图布局。设计开发了一个基于web的交互系统来实现该方法，系统支持样例草图绘制、样例导入和选取、源图导入和选取、映射模式选择、图混合比例控制、节点级的微调。同时开展了案例分析和评估实验，结果验证了该方法的可行性和有效性。

关键词: 图布局, 节点连接图, 用户交互, 图可视化

Abstract:

Traditional automatic graph layout algorithms, while ensuring the overall aesthetic properties of graph lay-outs, are unable to generate customized graph layouts. In different practical application scenarios, users often need to adjust the automatically generated graph layouts to meet specific requirements. Existing graph layout adjustments mainly fall into two categories: manual node-level adjustments and constraint-based graph layouts. The former is extremely time-consuming and monotonous, while the latter often lacks flexibility. A customized graph layout adjustment method based on user examples was proposed. This method primarily utilized graph blending theory to integrate the attributes and characteristics of example graphs into the source graphs, thereby achieving flexible and efficient customized graph layout adjustments. Initially, the examples were preprocessed. Two mapping examples and six mapping modes were then designed to generate node-level mapping matrices between the examples and the source graphs. The mapping matrices were employed to align the example graph with the source graph, and the graphs were blended at a certain ratio to obtain the customized graph layout adjustments. A web-based interactive system was designed and developed to implement this method, supporting example Sketch drawing, example importing and selection, source graph importing and selection, mapping mode selection, graph blending ratio control, and node-level fine-tuning. Case studies and evaluation experiments were conducted to validate the feasibility and effectiveness of the proposed method.

Key words: graph layout, node-link diagram, user interactions, graph visualization

中图分类号:

陈俊旭, 吴子梁, 朱闽峰, 陈为. 基于用户样例的图布局定制化调整[J]. 图学学报, 2025, 46(2): 402-414.

CHEN Junxu, WU Ziliang, ZHU Minfeng, CHEN Wei. Graph layout customization based on user-specified examples[J]. Journal of Graphics, 2025, 46(2): 402-414.

图/表 10

图1 基于用户样例的图布局定制化调整方法流程

Fig. 1 The process of graph layout customization based on user-specified examples

图2 系统界面1 ((a)预览视图；(b)混合候选视图；(c)探索视图；(d)样例视图-Network样例；(e)工具栏-Network工具)

Fig. 2 System interface ((a) Preview view; (b) Candidate view; (c) Exploration view; (d) Example view-Network example; (e) Toolbar-Network tools)

图3 系统界面2 ((a)预览视图；(b)混合候选视图；(c)探索视图；(d)样例视图-Sketch样例：交互式绘制样例；(e)工具栏-Sketch工具)

Fig. 3 System interface ((a) Preview view; (b) Candidate view; (c) Exploration view; (d) Example view-Sketch example: interactive drawing example; (e) Toolbar-Sketch tools)

表1 案例1~2, Sketch样例+2类映射

Table 1 Case 1-2, Sketch example & two types of mapping

映射	样例	源图 (混合前)	源图 (混合后)
线性映射
指定映射

表2 案例3~7, Network样例+五类映射

Table 2 Case 3-7, Network example & five types of mapping

映射	样例	源图 (混合前)	源图 (混合后)
指定映射
中介中心性映射
接近中心性映射
聚类系数映射
度中心性映射

图4 Route views Networks案例((a)调整前的源图；(b)调整后的源图；(c)源图中选定的待调整的结构；(d)用户定制的Sketch样例，用于调整源图结构)

Fig. 4 Route views Networks Case ((a) Source graph before adjustment; (b) Source graph after adjustment; (c) Selected structure in the source graph for adjustment; (d) User-customized Sketch example used to adjust the source graph structure)

图5 Facebook100案例((a)调整前的源图；(b) Network样例；(c) 90%混合比例下调整后的源图)

Fig. 5 Facebook100 Case ((a) Source graph before adjustment; (b) Network example; (c) Source graph after adjustment with 90% blend ratio)

表3 6种映射模式中映射矩阵构建的时间复杂度(n=max(n1,n2), m=max(m1,m2))

Table 3 The time complexity of mapping matrix construction in the six mapping modes(n=max(n1,n2), m=max(m1,m2))

映射	稀疏图	稠密图
线性映射	O(n)	O(n)
指定映射	O(n)	O(n)
度中心性映射	O(nlogn+m)	O(nlogn+m)
聚类系数映射	O(nlogn+m)	O(n³)
中介中心性映射	O(n²)	O(n³)
接近中心性映射	O(n²)	O(n³)

图6 6种映射模式下的图混合与2个经典力导布局算法的时效性比较(CPU：15核Xeon(R) Gold 5218)

Fig. 6 Comparison of the timeliness of graph blending under six mapping modes and two classic force-directed layout algorithms (CPU: 15-core Xeon(R) Gold 5218)

图7 样例(10个节点)和源图节点数差异较大时，线性映射和指定映射的时效性分析(CPU：15核Xeon(R) Gold 5218)

Fig. 7 Timeliness analysis of linear mapping and specific mapping when there is a significant difference in the number of nodes between the sample (10 nodes) and the source graph. (CPU: 15-core Xeon(R) Gold 5218)

参考文献 32

[1]	XUE M L, WANG Z, ZHONG F H, et al. Taurus: towards a unified force representation and universal solver for graph layout[J]. IEEE Transactions on Visualization and Computer Graphics, 2023, 29(1): 886-895.
[2]	BALCI H, DOGRUSOZ U. fCoSE: a fast compound graph layout algorithm with constraint support[J]. IEEE Transactions on Visualization and Computer Graphics, 2022, 28(12): 4582-4593.
[3]	张野, 王松, 吴亚东. FMR: 基于FR的快速多层次算法[J]. 图学学报, 2019, 40(1): 78-86. DOI
	ZHANG Y, WANG S, WU Y D. FMR: a fast multilevel algorithm based on FR[J]. Journal of Graphics, 2019, 40(1): 78-86 (in Chinese). DOI
[4]	汤颖, 汪斌, 范菁. 节点属性嵌入的改进图布局算法[J]. 计算机辅助设计与图形学学报, 2016, 28(2): 228-237.
	TANG Y, WANG B, FAN J. An improved graph layout algorithm of embedded node attributes[J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(2): 228-237 (in Chinese).
[5]	王智, 薛明亮, 王一凡, 等. 基于无冲突并行随机梯度下降的图布局求解方法[J/OL]. (2024-08-21)[2024-10-01]. http://kns.cnki.net/kcms/detail/11.2925.TP.20240820.1554.006.html.
	WANG Z, XUE M L, WANG Y F, et al. Graph drawing by conflict-free parallel stochastic gradient descent[J/OL]. (2024-08-21)[2024-10-01]. http://kns.cnki.net/kcms/detail/11.2925.TP.20240820.1554.006.html (in Chinese).
[6]	EADES P. A heuristic for graph drawing[J]. Congressus Numerantium, 1984, 42(11): 149-160.
[7]	FRUCHTERMAN T M J, REINGOLD E M. Graph drawing by force‐directed placement[J]. Software: Practice and Experience, 1991, 21(11): 1129-1164.
[8]	HU Y. Efficient, high-quality force-directed graph drawing[J]. Mathematica Journal, 2006, 10(1): 37-71.
[9]	ZHONG F H, XUE M L, ZHANG J, et al. Force-directed graph layouts revisited: a new force based on the t-distribution[J]. IEEE Transactions on Visualization and Computer Graphics, 2024, 30(7): 3650-3663.
[10]	KAMADA T, KAWAI S. An algorithm for drawing general undirected graphs[J]. Information Processing Letters, 1989, 31(1): 7-15.
[11]	DAVIDSON R, HAREL D. Drawing graphs nicely using simulated annealing[J]. ACM Transactions on Graphics, 1996, 15(4): 301-331.
[12]	TORGERSON W S. Multidimensional scaling: I. Theory and method[J]. Psychometrika, 1952, 17(4): 401-419.
[13]	VAN DER MAATEN L,. HINTON G. Visualizing data using t-SNE[J]. Journal of Machine Learning Research, 2008, 9(86): 2579-2605.
[14]	MCINNES L, HEALY J, MELVILLE J. UMAP: uniform manifold approximation and projection for dimension reduction[EB/OL]. [2024-06-01]. https://arxiv.org/abs/1802.03426.
[15]	MI P, SUN M Y, MASIANE M, et al. Interactive graph layout of a million nodes[J]. Informatics, 2016, 3(4): 23.
[16]	JUSUFI I, KERREN A, ZIMMER B. Multivariate Network exploration with JauntyNets[C]// The 17th International Conference on Information Visualisation. New York: IEEE Press, 2013: 19-27.
[17]	HOSOBE H. A high-dimensional approach to interactive graph visualization[C]// 2004 ACM Symposium on Applied Computing. New York: ACM, 2004: 1253-1257.
[18]	PETZOLD J, DOMRÖS S, SCHÖNBERNER C, et al. An interactive graph layout constraint framework[EB/OL]. [2024-06-22]. https://www.scitepress.org/Link.aspx?doi=10.5220/0011803000003417.
[19]	GUCHEV V, GENA C. Sketch-based interactions for untangling of force-directed graphs[C]// 2017 21st International Conference Information Visualisation. New York: IEEE Press, 2017: 288-291.
[20]	HENRY N, FEKETE J D, MCGUFFIN M J. NodeTrix: a hybrid visualization of social Networks[J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(6): 1302-1309. PMID
[21]	RYALL K, MARKS J, SHIEBER S. An interactive constraint-based system for drawing graphs[C]// The 10th Annual ACM Symposium on User Interface Software and Technology. New York: ACM, 1997: 97-104.
[22]	SCHREIBER F, DWYER T, MARRIOTT K, et al. A generic algorithm for layout of biological Networks[J]. BMC Bioinformatics, 2009, 10: 375. DOI PMID
[23]	HOFFSWELL J, BORNING A, HEER J. SetCoLa: high-level constraints for graph layout[J]. Computer Graphics Forum, 2018, 37(3): 537-548.
[24]	MASUI T. Graphic object layout with interactive genetic algorithms[C]// The IEEE Workshop on Visual Languages. New York: IEEE Press, 1992: 74-80.
[25]	DWYER T, MARRIOTT K, WYBROW M. Dunnart: a constraint-based Network diagram authoring tool[C]// The 16th International Symposium on Graph Drawing. Cham: Springer, 2009: 420-431.
[26]	BURCH M, TEN BRINKE K B, CASTELLA A, et al. Guiding graph exploration by combining layouts and reorderings[C]// The 13th International Symposium on Visual Information Communication and Interaction. New York: ACM, 2020: 1-5.
[27]	KWON O H, MA K L. A deep generative model for graph layout[J]. IEEE Transactions on Visualization and Computer Graphics, 2020, 26(1): 665-675.
[28]	GIOVANNANGELI L, LALANNE F, AUBER D, et al. Toward efficient deep learning for graph drawing (DL4GD)[J]. IEEE Transactions on Visualization and Computer Graphics, 2024, 30(2): 1516-1532.
[29]	LING H Y, JIANG Z M, LIU M, et al. Graph mixup with soft alignments[EB/OL]. [2024-06-22]. https://dl.acm.org/doi/10.5555/3618408.3619287.
[30]	BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large Networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008.
[31]	MO Y J, PENG L, XU J, et al. Simple unsupervised graph representation learning[C]// The 36th AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2022: 7797-7805.
[32]	ZHOU Z G, SHI C, SHEN X L, et al. Context-aware sampling of large Networks via graph representation learning[J]. IEEE Transactions on Visualization and Computer Graphics, 2021, 27(2): 1709-1719.

映射	样例	源图 (混合前)	源图 (混合后)
指定映射
中介中心性映射
接近中心性映射
聚类系数映射
度中心性映射

映射	样例	源图 (混合前)	源图 (混合后)
指定映射
中介中心性映射
接近中心性映射
聚类系数映射
度中心性映射

基于用户样例的图布局定制化调整

Graph layout customization based on user-specified examples

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 32

相关文章 3

编辑推荐

Metrics

本文评价

[1]	罗月童, 彭俊, 高景一, 罗睿明, 陈绩, 周波. 面向线束预装配的多约束线束布局方法研究[J]. 图学学报, 2024, 45(1): 139-147.
[2]	张野，王松，吴亚东 . FMR：基于 FR 的快速多层次算法[J]. 图学学报, 2019, 40(1): 78-86.
[3]	陈炳坤，周虹 . 基于多层图布局算法的不确定性网络可视化方法[J]. 图学学报, 2018, 39(6): 1130-1138.