Journal of Computer Science and Technology ›› 2021, Vol. 36 ›› Issue (3): 707-718.doi: 10.1007/s11390-021-9910-5

Special Issue: Computer Graphics and Multimedia

• Regular Paper • Previous Articles    

Inverse Markov Process Based Constrained Dynamic Graph Layout

Shi-Ying Sheng1, Sheng-Tao Chen2, Xiao-Ju Dong2,*, Distinguished Member, CCF, Chun-Yuan Wu1, and Xiao-Ru Yuan3, Distinguished Member, CCF, Senior Member, IEEE, Member, ACM        

  1. 1 ParisTech Elite Institute of Technology, Shanghai Jiao Tong University, Shanghai 200240, China;
    2 Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China;
    3 Key Laboratory of Machine Perception(Ministry of Education), National Engineering Laboratory for Big Data Analysis and Application, Peking University, Beijing 100080, China
  • Received:2019-08-06 Revised:2021-01-12 Online:2021-05-05 Published:2021-05-31
  • Contact: Xiao-Ju Dong
  • About author:Shi-Ying Sheng is a Master student in Shanghai Jiao Tong University, Shanghai. She received her B.S. degree in software engineering from Shanghai Jiao Tong University, Shanghai, in 2017. Her research interests are graph computing and visualization.
  • Supported by:
    This research was supported by the National Key Research and Development Program of China under Grant No. 2017YFB0701900, the National Natural Science Foundation of China under Grant No. 61100053, and the Key Laboratory of Machine Perception of Peking University under Grant No. K-2019-09.

In online dynamic graph drawing, constraints over nodes and node pairs help preserve a coherent mental map in a sequence of graphs. Defining the constraints is challenging due to the requirements of both preserving mental map and satisfying the visual aesthetics of a graph layout. Most existing algorithms basically depend on local changes but fail to do proper evaluations on the global propagation when setting constraints. To solve this problem, we introduce a heuristic model derived from PageRank which simulates the node movement as an inverse Markov process hence to give a global analysis of the layout's change, according to which different constraints can be set. These constraints, along with stress function, generate layouts maintaining spatial positions and shapes of relatively stable substructures between adjacent graphs. Experiments demonstrate that our method preserves both structure and position similarity to help users track graph changes visually.

Key words: graph drawing; data stream; dynamic graph layout;

[1] Frishman Y, Tal A. Online dynamic graph drawing. IEEE Transactions on Visualization and Computer Graphics, 2008, 14(4):727-740. DOI:10.1109/TVCG.2008.11.
[2] Branke J. Dynamic graph drawing. In Drawing Graphs, Kaufmann M, Wagner D (eds.), Springer, 2001, pp.228-246. DOI:10.1007/3-540-44969-8_9.
[3] Che L, Liang J, Yuan X et al. Laplacian-based dynamic graph visualization. In Proc. the 2015 IEEE Pacific Visualization Symposium, April 2015, pp.69-73. DOI:10.1109/PACIFICVIS.2015.7156358.
[4] Gorochowski T E, Bernardo M D, Grierson C S. Using aging to visually uncover evolutionary processes on networks. IEEE Transactions on Visualization and Computer Graphics, 2011, 18(8):1343-1352. DOI:10.1109/TVCG.2011.142.
[5] Feng K C, Wang C, Shen H W et al. Coherent time-varying graph drawing with multifocus + context interaction. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(8):1330-1342. DOI:10.1109/TVCG.2011.128.
[6] Wang Y, Wang Y, Sun Y et al. Revisiting stress majorization as a unified framework for interactive constrained graph visualization. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(1):489-499. DOI:10.1109/TVCG.2017.2745919.
[7] Yuan X R, Chen L M, Hu Y F et al. Intelligent graph layout using many users' input. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(12):2699-2708. DOI:10.1109/TVCG.2012.236.
[8] Kamada T, Kawai S. An algorithm for drawing general undirected graphs. Information Processing Letters, 1989, 31(1):7-15. DOI:10.1016/0020-0190(89)90102-6.
[9] Crnovrsanin T, Chu J, Ma K L. An incremental layout method for visualizing online dynamic graphs. In Proc. the 23rd International Symposium on Graph Drawing and Network Visualization, Sept. 2015, pp.16-29. DOI:10.1007/978-3-319-27261-0_2.
[10] Kaufmann M, Dorothea W. Drawing Graphs:Methods and Models. Springer, 2001. DOI:10.1007/3-540-44969-8.
[11] Eades P. A heuristic for graph drawing. Congressus Nutnerantiunt, 1984, 42:149-160.
[12] Fruchterman T M, Reingold E M. Graph drawing by forcedirected placement. Software:Practice and Experience, 1991, 21(11):1129-64. DOI:10.1002/spe.4380211102.
[13] Cohen R F, Battista G D, Tamassia R, Tollis I G, Bertolazzi P. A framework for dynamic graph drawing. In Proc. the 8th Annual Symposium on Computational Geometry, July 1992, pp.261-270. DOI:10.1145/142675.142728.
[14] Misue K§Eades P, Lai W et al. Layout adjustment and the mental map. Journal of Visual Languages & Computing, 1995, 6(2):183-210. DOI:10.1006/jvlc.1995.1010.
[15] Eades P, Cohen R F, Huang M L. Online animated graph drawing for web navigation. In Proc. the 5th International Symposium on Graph Drawing, Sept. 1997, pp.330-335. DOI:10.1007/3-540-63938-1_77.
[16] Erten C, Harding P J, Kobourov S G, Wampler K, Yee G. GraphAEL:Graph animations with evolving layouts. In Proc. the 11th International Symposium on Graph Drawing, Sept. 2003, pp.98-110. DOI:10.1007/978-3-540-24595-7_9.
[17] Bridgernan S, Tamassia R. Difference metrics for interactive orthogonal graph drawing algorithms. In Proc. the 6th International Symposium on Graph Drawing, August 1998, pp.57-71. DOI:10.1007/3-540-37623-25.
[18] Beck F, Burch M, Diehl S, Weiskopf D. The state of the art in visualizing dynamic graphs. In Proc. the 16th Eurographics Conference on Visualization, June 2014. DOI:10.2312/eurovisstar.20141174.
[19] Archambault D, Purchase H, Pinaud B. Animation, small multiples, and the effect of mental map preservation in dynamic graphs. IEEE Transactions on Visualization and Computer Graphics, 2010, 17(4):539-552. DOI:10.1109/TVCG.2010.78.
[20] Jacomy M, Venturini T, Heymann S et al. ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software. PLoS ONE, 2014, 9(6):Article No. e98679. DOI:10.1371/journal.pone.0098679.
[21] Friedrich C, Eades P. The Marey graph animation tool demo. In Proc. the 8th International Symposium on Graph Drawing, Sept. 2000, pp.396-406. DOI:10.1007/3-540-44541-2_37.
[22] Friedrich C, Eades P. Graph drawing in motion. J. Graph Algorithms Appl., 2002, 6(3):353-70. DOI:10.1007/3-540-45848-4_18.
[23] Hurter C, Ersoy O, Fabrikant S I, Klein T R, Telea A C. Bundled visualization of dynamic graph and trail data. IEEE Transactions on Visualization and Computer Graphics, 2013, 20(8):1141-57. DOI:10.1109/TVCG.2013.246.
[24] Diehl S, Görg C, Kerren A. Preserving the mental map using foresighted layout. In Proc. the Joint Eurographics-IEEE TCVG Symposium on Visualization, May 2001, pp.175-184. DOI:10.1007/978-3-7091-6215-6_19.
[25] Diehl S, Görg C. Graphs, they are changing. In Proc. the 10th International Symposium on Graph Drawing, August 2002, pp.23-30. DOI:10.1007/3-540-36151-0_3.
[26] Brandes U, Wagner D. A Bayesian paradigm for dynamic graph layout. In Proc. the 5th International Symposium on Graph Drawing, Sept. 1997, pp.236-247. DOI:10.1007/3-540-63938-1_66.
[27] Görg C, Birke P, Pohl M, Diehl S. Dynamic graph drawing of sequences of orthogonal and hierarchical graphs. In Proc. the 12th International Symposium on Graph Drawing, Sept. 2004, pp.228-238. DOI:10.1007/978-3-540-31843-9_24.
[28] Lee Y Y, Lin C C, Yen H C. Mental map preserving graph drawing using simulated annealing. In Proc. the 2006 Asia-Pacific Symposium on Information Visualisation, Jan. 2006, pp.179-188. DOI:10.1016/j.ins.2011.06.005.
[29] Crnovrsanin T, Chu J, Ma K L. An incremental layout method for visualizing online dynamic graphs. In Proc. the 23rd International Symposium on Graph Drawing, Sept. 2015, pp.16-29. DOI:10.1007/978-3-319-27261-0_2.
[30] Hachul S, Jünger M. Drawing large graphs with a potentialfield-based multilevel algorithm. In Proc. the 12th International Symposium on Graph Drawing, Sept. 2004, pp.285-295. DOI:10.1007/978-3-540-31843-9_29.
[31] Dwyer T, Koren Y. DIG-COLA:Directed graph layout through constrained energy minimization. In Proc. the 2005 IEEE Symposium on Information Visualization, October 2005, pp.65-72. DOI:10.1109/INFVIS.2005.1532130.
[32] Dwyer T, Koren Y, Marriott K. Constrained graph layout by stress majorization and gradient projection. Discrete Mathematics, 2009, 309(7):1895-1908. DOI:10.1016/j.disc.2007.12.103.
[33] Brin S, Page L. The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 1998, 30(1/2/3/4/5/6/7):107-117. DOI:10.1016/S0169-7552(98)00110-X.
[34] Davidson R, David H. Drawing graphs nicely using simulated annealing. ACM Transactions on Graphics, 1996, 15(4):301-331. DOI:10.1145/234535.234538.
[35] Gansner E R, Koren Y, North S. Graph drawing by stress majorization. In Proc. the 12th International Symposium on Graph Drawing, Sept. 2004, pp.239-250. DOI:10.1007/978-3-540-31843-9_25.
[36] Purchase H C, Hoggan E, Görg C. How important is the "mental map"?-An empirical investigation of a dynamic graph layout algorithm. In Proc. the 14th International Symposium on Graph Drawing, Sept. 2006, pp.184-195. DOI:10.1007/978-3-540-70904-6_19.
[37] Dwyer T. Scalable, versatile and simple constrained graph layout. Computer Graphics Forum, 2009, 28(3):991-998. DOI:10.1111/j.1467-8659.2009.01449.x.
[38] Newcomb T M. The Acquaintance Process. Holt, Rinehart & Winston, 1961. DOI:10.1037/13156-000.
[39] Hristidis V, Hwang H, Papakonstantinou Y. Authoritybased keyword search in databases. ACM Transactions on Database Systems, 2008, 33(1):Article No. 1. DOI:10.1145/1331904.1331905.
[1] Yi-Min Wen, Shuai Liu. Semi-Supervised Classification of Data Streams by BIRCH Ensemble and Local Structure Mapping [J]. Journal of Computer Science and Technology, 2020, 35(2): 295-304.
[2] Wen Liu, Yan-Ming Shen, Member, CCF, Peng Wang. An Efficient Approach of Processing Multiple Continuous Queries [J]. , 2016, 31(6): 1212-1227.
[3] Dong-Hong Han, Xin Zhang, Guo-Ren Wang. Classifying Uncertain and Evolving Data Streams with Distributed Extreme Learning Machine [J]. , 2015, 30(4): 874-887.
[4] Fang Zheng, Hong-Liang Li, Hui Lv, Feng Guo, Xiao-Hong Xu, Xiang-Hui Xie. Cooperative Computing Techniques for a Deeply Fused and Heterogeneous Many-Core Processor Architecture [J]. , 2015, 30(1): 145-162.
[5] Ke-Yan Cao, Guo-Ren Wang, Dong-Hong Han, Guo-Hui Ding, Ai-Xia Wang, and Ling-Xu Shi. Continuous Outlier Monitoring on Uncertain Data Streams [J]. , 2014, 29(3): 436-448.
[6] Amineh Amini, Teh Ying Wah, and Hadi Saboohi. On Density-Based Data Streams Clustering Algorithms:A Survey [J]. , 2014, 29(1): 116-141.
[7] Bin Wang, Member, CCF, Xiao-Chun Yang, Senior Member, CCF, Member ACM, IEEE, Guo-Ren Wang, Senior Member, CCF, Member, ACM, IEEE, and Ge Yu, Senior Member, CCF, Member, ACM, IEEE. Outlier Detection over Sliding Windows for Probabilistic Data Streams [J]. , 2010, 25(3): 389-400.
[8] Hong Shen and Yu Zhan. Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows [J]. , 2008, 23(6 ): 973-987 .
[9] Lu-An Tang, Bin Cui, Hong-Yan Li, Gao-Shan Miao, Dong-Qing Yang, and Xin-Biao Zhou. PGG: An Online Pattern Based Approach for Stream Variation Management [J]. , 2008, 23(4 ): 497-515 .
[10] Yu-Bao Liu, Jia-Rong Cai, Jian Yin, and Ada Wai-Chee Fu. Clustering Text Data Streams [J]. , 2008, 23(1): 112-128 .
[11] Xue-Gang Hu, Pei-Pei Li, Xin-Dong Wu, and Gong-Qing Wu. A semi-random multiple decision-tree algorithm for mining data streams [J]. , 2007, 22(5): 711-724 .
[12] Dong-Hong Han, Guo-Ren Wang, Chuan Xiao, and Rui Zhou. Load Shedding for Window Joins over Streams [J]. , 2007, 22(2): 182-189 .
[13] Zhi-Hong Chong, Jeffrey Xu Yu, Zhen-Jie Zhang, Xue-Min Lin, Wei Wang, and Ao-Ying Zhou. Efficient Computation of k-Medians over Data Streams Under Memory Constraints [J]. , 2006, 21(2): 284-296 .
[14] Joong Hyuk Chang and Won Suk Lee. Effect of Count Estimation in Finding Frequent Itemsets over Online Transactional Data Streams [J]. , 2005, 20(1): 0-0.
[15] HE Zengyou (何增有), XU Xiaofei (徐晓飞) and DENG Shengchun(邓胜春). Squeezer: An Efficient Algorithm for Clustering Categorical Data [J]. , 2002, 17(5): 0-0.
Full text



[1] Zhou Di;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] Chen Shihua;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] Pan Qijing;. A Routing Algorithm with Candidate Shortest Path[J]. , 1986, 1(3): 33 -52 .
[4] Wang Jianchao; Wei Daozheng;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[5] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[6] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[7] Zheng Guoliang; Li Hui;. The Design and Implementation of the Syntax-Directed Editor Generator(SEG)[J]. , 1986, 1(4): 39 -48 .
[8] Huang Xuedong; Cai Lianhong; Fang Ditang; Chi Bianjin; Zhou Li; Jiang Li;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .
[9] Xu Xiaoshu;. Simplification of Multivalued Sequential SULM Network by Using Cascade Decomposition[J]. , 1986, 1(4): 84 -95 .
[10] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved