图的表示与可视化方法综述

doi:10.16182/j.issn1004731x.joss.19-VR0444

摘要/Abstract

摘要： 图是由节点和边组成的图形,通常用于表示两个或多个实体之间的关系。基于图的分析可以帮助人们理解实体关系的结构和本质,探索图中的隐含关联。图的表示与可视化方法在图分析中起着的重要作用,在图可视化研究中首先要考虑知识传达是否准确、人们的思维地图等方面,同时还要考虑图形是否美观、构建图所需的时间、以及计算机的性能等问题。综述了基于节点-链接、邻接矩阵以及图嵌入的图表示方法、图布局算法以及可视化方法,并对这些方法进行归纳与对比。最后对图表示与可视化技术的未来发展趋势进行了展望。

关键词: 图表示, 可视化, 节点-链接图, 邻接矩阵, 图嵌入

Abstract: A graph consists of nodes and edges, and represents the relationship between two or more entities. Graph-based analysis can help understand the structure and nature of the entity relationships and reveal the implicit relationships in graphs. The representation and visualization methods of graphs play an important role in the graph analysis. In graph visualization research, the accuracy of knowledge transfer and people's mental map, etc. should be considered first, then the graphs beauty, the time requirement, and the computer performance. The graph representation methods, graph layout algorithms, visualization methods based on node-link-graphs, adjacency matrices, and graph embedding are reviewed, summarized and contrasted. The future work and challenges are discussed.

Key words: Graph representation, visualization, node-link-graph, adjacency matrix, graph embedding

中图分类号:

TP391

陈谊, 张梦录, 万玉钗. 图的表示与可视化方法综述[J]. 系统仿真学报, 2020, 32(7): 1232-1243.

Chen Yi, Zhang Menglu, Wan Yuchai. A Survey on Graph Representation and Visualization Techniques[J]. Journal of System Simulation, 2020, 32(7): 1232-1243.

参考文献 62

[1]	Heer J, Boyd D.Vizster: Visualizing Online Social Networks[C]// IEEE Symposium on Information Visualization. Washington: IEEE, 2005: 32-39.
[2]	江美辉, 安海忠, 高湘昀, 等. 基于复杂网络的食品安全事件新闻文本可视化及分析[J]. 情报杂志, 2015, 34(12): 121-127.Jiang Meihui, An Haizhong, Gao Xiangyun, et al.The Visualization and Analysis of News Texts about Food Safety Incidents Based on Complex Networks[J]. Journal of Intelligence, 2015, 34(12): 121-127.
[3]	杜晓敏, 陈谊, 李玥. TransGraph: 一种基于变换的可视分析关联图[J]. 计算机辅助设计与图形学学报, 2018(1): 79-89.Du Xiaomin, Chen Yi, Li Yue.TransGraph: A Transformation-Based Graph for Analyzing Relations in Data Set[J]. Journal of Computer-Aided Design & Computer Graphics, 2018(1): 79-89.
[4]	Beck F, Burch M, Diehl S, et al.A Taxonomy and Survey of Dynamic Graph Visualization[J]. Computer Graphics Forum (S0167-7055), 2017, 36(1): 133-159.
[5]	李志刚, 陈谊, 张鑫跃, 等. 一种基于力导向布局的层次结构可视化方法[J]. 计算机仿真, 2014, 31(3): 283-288.Li Zhigang, Chen Yi, Zhang Xinyue, et al.Hierarchical Structure Visualization Methods Research[J]. Computer Simulation, 2014, 31(3): 283-288.
[6]	Eades P.A heuristic for graph drawing[J]. Congressus Numerantium (S0316-1382), 1984, 42: 149-160.
[7]	Kamada T, Kawai S.An algorithm for drawing general undirected graphs[J]. Information Processing Letters (S0020-0190), 1989, 31(1): 7-15.
[8]	Chen Y, Guan Z, Zhang R, et al.A survey on visualization approaches for exploring association relationships in graph data[J]. Journal of Visualization (S1343-8875), 2019, 22(3): 625-639.
[9]	时磊, 廖琦, 林闯. 基于变换的大图点边可视化综述[J]. 计算机辅助设计与图形学学报, 2013, 25(3): 304-311.Shi Lei, Liao Qi, Lin Chuang.Survey on Transformation-based Large Graph Visualization[J]. Journal of Computer-Aided Design & Computer Graphics, 2013, 25(3): 304-311.
[10]	Pienta R, Abello J, Kahng M, et al.Scalable graph exploration and visualization: Sensemaking challenges and opportunities[C]// International Conference on Big Data & Smart Computing. Bangkok. Thailand: IEEE, 2014: 271-278.
[11]	陈为, 沈则潜, 陶煜波. 数据可视化[M]. 北京: 电子工业出版社, 2013.Chen Wei, Shen Zeqian, Tao Yubo.Data visualization[M]. Beijing: Publishing House of Electronics Industry, 2013.
[12]	Battista G D, Eades P, Tamassia R, et al.Graph Drawing: Algorithms for the Visualization of Graphs[M]. Upper Saddle River: Prentice Hall, 1998.
[13]	Eades P, Feng Q W.Multilevel visualization of clustered graphs[C]// Graph drawing. Berlin Heidelberg: Springer, 1997: 101-112.
[14]	Wang Y H, Wang Y Y, Zhang H F, et al.Structure-aware Fisheye Views for Efficient Large Graph Exploration[J]. IEEE Transactions on Visualization and Computer Graphics (S1077-2626), 2018, 25(1): 566-575.
[15]	Fruchterman T M J, Reingold E M. Graph drawing by force-directed placement[J]. Software-Practice and Experience (S0038-0644), 1991, 21(11): 1129-1164.
[16]	Arleo A, Didimo W, Liotta G, et al.A distributed multilevel force-directed algorithm[J]. IEEE Transactions on Parallel and Distributed Systems (S1045-9219), 2019, 30(4): 754-765.
[17]	Khoury M, Hu Y, Krishnan S, et al.Drawing Large Graphs by Low-Rank Stress Majorization[J]. Computer Graphics Forum (S0167-7055), 2012, 31(3): 975-984.
[18]	Ko Y J, Yen H C.Drawing clustered graphs using stress majorization and force-directed placements[C]// 20th International Conference Information Visualisation. PORTUGAL: IEEE, 2016: 69-74.
[19]	Hu Y.Algorithms for Visualizing Large Networks[J]. Combinatorial Scientific Computing (S1862-4405), 2011, 5(3): 180-186.
[20]	Gibson H, Faith J, Vickers P.A survey of two- dimensional graph layout techniques for information visualisation[J]. Information Visualization (S1473-8716), 2013, 12(3/4): 324-357.
[21]	Wang Y, Wang Y, Sun Y, et al.Revisiting Stress Majorization as a Unified Framework for Interactive Constrained Graph Visualization[J]. IEEE Trans Vis Comput Graph (S1077-2626), 2018, 24(1): 489-499.
[22]	Tim D, Yehuda K, Kim M.IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs[J]. IEEE Transactions on Visualization and Computer Graphics (S1077-2626), 2006, 12(5): 821-828.
[23]	He W, Marriott K.Constrained graph layout[C]// International Symposium on Graph Drawing. Berlin Heidelberg: Springer, 1998: 289-314.
[24]	Dwyer T, Koren Y, Marriott K.Stress Majorization with Orthogonal Ordering Constraints[C]// Graph Drawing. Berlin Heidelberg: Springer, 2006: 141-152.
[25]	Didimo W, Montecchiani F.Fast layout computation of clustered networks: Algorithmic advances and experimental analysis[J]. Information Sciences (S0020-0255), 2014, 260(15): 185-199.
[26]	Xiang-Sheng Z J, Samraat P, Matthew G D F. Graph Drawing by Stochastic Gradient Descent[J]. IEEE Transactions on Visualization and Computer Graphics (S1077-2626), 2018, 25(9): 2738-2748.
[27]	Wu H Y, Takahashi S, Ishida R.Overlap-free labeling of clustered networks based on Voronoi tessellation[J]. Journal of Visual Languages & Computing (S1045-926X), 2018, 44: 106-119.
[28]	Barnard S T, Simon H D.Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems[J]. Concurrency & Computation Practice & Experience (S1532-0634), 1994, 6(2): 101-117.
[29]	Meyerhenke H, Nollenburg M, Schulz C.Drawing Large Graphs by Multilevel Maxent-Stress Optimization[J]. IEEE Trans Vis Comput Graph (S1077-2626), 2018, 24(5): 1814-1827.
[30]	Gajer P, Kobourov S G.GRIP: Graph Drawing with Intelligent Placement[C]// Proceedings of the 8th International Symposium on Graph Drawing. London: Spring, 2001: 222-228.
[31]	Hachul S, Junger M.Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm (Extended Abstract)[C]// Lecture Notes in Computer Science. Heidelberg: Springer, 2004: 285-295.
[32]	Nguyen A, Hong S H. k-core based multi-level graph visualization for scale-free networks[C]//Pacific Visualization Symposium. Seoul: IEEE, 2017: 21-25.
[33]	Gansner E R, Hu Y, North S C.A maxent-stress model for graph layout[J]. IEEE Transactions on Visualization and Computer Graphics (S1077-2626), 2013, 19(6): 927-940.
[34]	Kirmani S, Raghavan P.Scalable parallel graph partitioning[C]// Proceedings of the International Conference on High Performance Computing. Denver, Colorado: ACM, 2013: 1-10.
[35]	Robertson G G, Mackinlay J D, Card S K.Cone-Trees: Animated 3D Visualizations of Hierarchical Information[C]// Sigchi Conference on Human Factors in Computing Systems. New Orleans: ACM, 1991: 189-194.
[36]	Archambault D, Purchase H C.The “Map” in the mental map: Experimental results in dynamic graph drawing[J]. International Journal of Human-Computer Studies (S1071-5819), 2013, 71(11): 1044-1055.
[37]	Hayashi A, Matsubayashi T, Hoshide T I, et al.Initial positioning method for online and real time dynamic graph drawing for time varying data[C]// Proceedings of the 17th International Conference on Information Visualisation. Washington D C: IEEE Computer Society Press, 2013: 435-444.
[38]	Alper B, Bach B, Riche N H, et al.Weighted graph comparison techniques for brain connectivity analysis[C]//Sigchi Conference on Human Factors in Computing Systems. New York: ACM, 2013:483-492.
[39]	Behrisch M, Bach B, Riche N H, et al.Matrix Reordering Methods for Table and Network Visualization[J]. Computer Graphics Forum (S0167-7055), 2016, 35(3): 693-716.
[40]	Ghoniem M, Fekete J D, Castagliola P.On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis[J]. Information Visualization (S1473-8716), 2005, 4(2): 114-135.
[41]	Henry N, Fekete J D.MatrixExplorer: a Dual-Representation System to Explore Social Networks[J]. IEEE Transactions on Visualization and Computer Graphics (S1473-8716), 2006, 12(5): 677-684.
[42]	Henry N, Fekete J D.MatLink: Enhanced Matrix Visualization for Analyzing Social Networks[C]// IFIP Conference on Human-Computer Interaction. Heidelberg: Springer, 2007: 288-302.
[43]	Lex A, Streit M, Schulz H J, et al.StratomeX: Visual Analysis of Large-Scale Heterogeneous Genomics Data for Cancer Subtype Characterization[J]. Computer Graphics Forum (S0167-7055), 2012, 31(3): 1175-1184.
[44]	Rufiange S, Melançon G.AniMatrix: A Matrix-Based Visualization of Software Evolution[C]// Software Visualization. Victoria: IEEE, 2014: 137-146.
[45]	Nobre C, Streit M, Lex A.Juniper: A tree+ table approach to multivariate graph visualization[J]. IEEE Transactions on Visualization and Computer Graphics (S1077-2626), 2019, 25(1): 544-554.
[46]	Mikolov T, Sutskever I, Chen K, et al.Distributed Representations of Words and Phrases and their Compositionality[C]// Proceedings of the 26th International Conference on Neural Information Processing Systems. Nevada: Curran Associates Inc, 2013, 3111-3119.
[47]	Perozzi B, Al-Rfou R, Skiena S.DeepWalk: Online learning of social representations[C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2014: 701-710.
[48]	Grover A, Leskovec J. node2vec: Scalable Feature Learning for Networks[C]//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. California: ACM, 2016: 1225-1234.
[49]	Tang J, Qu M, Wang M, et al.Line: Large-scale information network embedding[C]// Proceedings of the 24th International Conference on World Wide Web. Florence: International World Wide Web Conferences Steering Committee, 2015: 1067-1077.
[50]	Narayanan A, Chandramohan M, Chen L, et al.subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs[C]// Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Canada: ACM, 2016: 385-394.
[51]	Xiaojun Xu, Chang Liu, Qian Feng, Heng Yin, Le Song,Dawn Song.Neural network-based graph embedding for cross-platform binary code similarity detection[C]// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas: ACM, 2017: 363-376.
[52]	Dong Y X, Chawla N V, Swami A.Metapath2vec: Scalable Representation Learning for Heterogeneous Networks[C]// Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Canada: ACM, 2017: 135-144.
[53]	Sun Y Z, Han J W.Mining Heterogeneous Information Networks: Principles and Methodologies[J]. ACM SIGKDD explorations newsletter (S1931-0145), 2012, 14(2): 439-473.
[54]	Fu T Y, Lee W C, Lei Z.HIN2Vec: Explore Meta-paths in Heterogeneous Information Networks for Representation Learning[C]// ACM Conference on Information and Knowledge Managemen. Singapore: ACM, 2017: 1797-1806.
[55]	Shi C, Hu B B, Zhao W X, et al.Heterogeneous Information Network Embedding for Recommendation[J]. IEEE Transactions on Knowledge and Data Engineering (S2326-3865), 2018, 31(2): 357-370.
[56]	Wang X, Zhang Y D, Shi C.Hyperbolic Heterogeneous Information Network Embedding[C]// 33rd AAAI Conference on Artificial Intelligence. Honolulu: AAAI, 2019: 5337-5344.
[57]	Van der M L, Hinton G. Visualizing data using t-SNE[J]. Journal of Machine Learning Research (S1532-4435), 2008, 9(11): 2579-2605.
[58]	Tang J, Liu J, Zhang M, et al.Visualizing Large-scale and High-dimensional Data[C]// Proceedings of the 25th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee. Canada: ACM, 2016: 287-297.
[59]	Pienta R, Hohman F, Endert A, et al.VIGOR: Interactive Visual Exploration of Graph Query Results[J]. IEEE Transactions on Visualization and Computer Graphics (S1077-2626), 2018, 24(1): 215-225.
[60]	Yan K, Cui W W, Zhao T J.Frequent Pattern-based Graph Exploration[C]// Proceedings of the 12th International Symposium on Visual Information Communication and Interaction. Shanghai: ACM, 2019: 1-8.
[61]	Elseidy M, Abdelhamid E, Skiadopoulos S, et al.GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph[J]. Proceedings of the VLDB Endowment (S2150-8097), 2014, 7(7): 517-528.
[62]	Chen W, Guo F Z, Han D M, et al.Structure-Based Suggestive Exploration: A New Approach for Effective Exploration of Large Networks[J]. IEEE Transactions on Visualization and Computer Graphics (S1473-8716), 2019, 25(1): 555-565.