×

Online force-directed algorithms for visualization of dynamic graphs. (English) Zbl 1484.68339

Summary: Force-directed (FD) algorithms can be used to explore relationships in social networks, visualize money markets, and analyze transaction networks. However, FD algorithms are mainly designed for visualizing static graphs in which the topology of the networks remains constant throughout the calculation. In contrast to static graphs, nodes and edges in dynamic graphs can be added or removed as time progresses. In these situations, existing FD algorithms do not scale well, since any changes in the topology will trigger these algorithms to completely restart the entire computation. To alleviate this problem, we propose a design and implementation of five online FD algorithms to visualize dynamic graphs while maintaining their native force models. The online FD algorithms developed in this paper are able to reuse the force models of existing FD algorithms without significant modifications. To evaluate the effectiveness of the proposed approach, online FD algorithms are compared against static FD algorithms for visualizing dynamic graphs. Experimental results show that among the five algorithms evaluated, the online FD algorithm achieves the best number of edge crossings and the standard deviation of edge lengths for visualizing dynamic graphs.

MSC:

68W27 Online algorithms; streaming algorithms
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Fruchterman, T. M.; Reingold, E. M., Graph drawing by force-directed placement, Software: Practice and Experience, 21, 11, 1129-1164 (1991)
[2] Noack, A., An energy model for visual graph clustering, (International Symposium on Graph Drawing (2003), Springer), 425-436 · Zbl 1215.05119
[3] Kamada, T.; Kawai, S., An algorithm for drawing general undirected graphs, Information Processing Letters, 31, 1, 7-15 (1989) · Zbl 0679.68128
[4] Davidson, R.; Harel, D., Drawing graphs nicely using simulated annealing, ACM Transactions on Graphics (TOG), 15, 4, 301-331 (1996)
[5] Jacomy, M.; Venturini, T.; Heymann, S.; Bastian, M., Forceatlas2, a continuous graph layout algorithm for handy network visualization designed for the gephi software, PloS one, 9, 6, Article e98679 pp. (2014)
[6] Rufiange, S.; McGuffin, M. J., Diffani: Visualizing dynamic graphs with a hybrid of difference maps and animation, IEEE Transactions on Visualization and Computer Graphics, 19, 12, 2556-2565 (2013)
[7] Yee, K.-P.; Fisher, D.; Dhamija, R.; Hearst, M., Animated exploration of dynamic graphs with radial layout, InfoVis, IEEE, 43 (2001)
[8] 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, 17, 4, 539-552 (2011)
[9] Ahn, J.-W.; Taieb-Maimon, M.; Sopan, A.; Plaisant, C.; Shneiderman, B., Temporal visualization of social network dynamics: Prototypes for nation of neighbors, (International Conference on Social Computing, Behavioral-Cultural Modeling, and Prediction (2011), Springer), 309-316
[10] Brandes, U.; Indlekofer, N.; Mader, M., Visualization methods for longitudinal social networks and stochastic actor-oriented modeling, Social Networks, 34, 3, 291-308 (2012)
[11] Brasch, S.; Fuellen, G.; Linsen, L., Venlo: Interactive visual exploration of aligned biological networks and their evolution, (Visualization in Medicine and Life Sciences II (2012), Springer), 229-247
[12] Burch, M.; Beck, F.; Raschke, M.; Blascheck, T.; Weiskopf, D., A dynamic graph visualization perspective on eye movement data, (Proceedings of the Symposium on Eye Tracking Research and Applications, ACM (2014)), 151-158
[13] T. Dwyer, P. Eades, Visualising a fund manager flow graph with columns and worms, in: Information Visualisation, 2002. Proceedings. Sixth International Conference on, IEEE, 2002, pp. 147-152.
[14] von Landesberger, T.; Diel, S.; Bremm, S.; Fellner, D. W., Visual analysis of contagion in networks, Information Visualization, 14, 2, 93-110 (2015)
[15] Brath, R.; Jonker, D., Graph Analysis and Visualization: Discovering Business Opportunity in Linked Data (2015), John Wiley & Sons
[16] Frishman, Y.; Tal, A., Online dynamic graph drawing, IEEE Transactions on Visualization and Computer Graphics, 14, 4, 727-740 (2008)
[17] Kumar, G.; Garland, M., Visual exploration of complex time-varying graphs, IEEE Transactions on Visualization and Computer Graphics, 12, 5, 805-812 (2006)
[18] Coleman, M. K.; Parker, D. S., Aesthetics-based graph layout for human consumption, Software: Practice and Experience, 26, 12, 1415-1438 (1996)
[19] Misue, K.; Eades, P.; Lai, W.; Sugiyama, K., Layout adjustment and the mental map, Journal of Visual Languages & Computing, 6, 2, 183-210 (1995)
[20] H. Purchase, E. Hoggan, C. Görg, How important is the mental map, GD. · Zbl 1185.68494
[21] Ghoniem, M.; Fekete, J.-D.; Castagliola, P., A comparison of the readability of graphs using node-link and matrix-based representations, IEEE Symposium on Information Visualization, IEEE, 17-24 (2004)
[22] Chechik, G.; Shalit, U.; Sharma, V.; Bengio, S., An online algorithm for large scale image similarity learning, Advances in Neural Information Processing Systems, 306-314 (2009)
[23] E. Keogh, S. Chu, D. Hart, M. Pazzani, An online algorithm for segmenting time series, in: Data Mining, 2001. ICDM 2001, Proceedings IEEE International Conference on, IEEE, 2001, pp. 289-296.
[24] S.-H. Cheong, Y.-W. Si, Accelerating the kamada-kawai algorithm for boundary detection in a mobile ad hoc network, ACM Transactions on Sensor Networks (TOSN) 13 (1) (2016) 3.
[25] R. Heijmans, R. Heuver, C. Levallois, I. van Lelyveld, Dynamic visualization of large transaction networks: the daily dutch overnight money market.
[26] Crnovrsanin, T.; Chu, J.; Ma, K.-L., An incremental layout method for visualizing online dynamic graphs, (International Symposium on Graph Drawing and Network Visualization (2015), Springer), 16-29 · Zbl 1471.68190
[27] McGinn, D.; Birch, D.; Akroyd, D.; Molina-Solana, M.; Guo, Y.; Knottenbelt, W. J., Visualizing dynamic bitcoin transaction patterns, Big Data, 4, 2, 109-119 (2016)
[28] G. Di Battista, V. Di Donato, M. Patrignani, M. Pizzonia, V. Roselli, R. Tamassia, Bitconeview: visualization of flows in the bitcoin transaction graph, in: Visualization for Cyber Security (VizSec), 2015 IEEE Symposium on, IEEE, 2015, pp. 1-8.
[29] P.J. Sazama, An overview of visualizing dynamic graphs.
[30] F. Beck, M. Burch, S. Diehl, D. Weiskopf, The state of the art in visualizing dynamic graphs, EuroVis STAR 2.
[31] Erten, C.; Harding, P. J.; Kobourov, S. G.; Wampler, K.; Yee, G., Graphael: Graph animations with evolving layouts, International Symposium on Graph Drawing, Springer, 98-110 (2003) · Zbl 1215.68180
[32] M. Burch, Visualizing large dynamic digraphs.
[33] Brandes, U.; Wagner, D., A bayesian paradigm for dynamic graph layout, International Symposium on Graph Drawing, Springer, 236-247 (1997)
[34] D. Holten, J.J. Van Wijk, Force-directed edge bundling for graph visualization, in: Computer graphics forum, Vol. 28, Wiley Online Library, 2009, pp. 983-990.
[35] Liang, S., The Java Native Interface: Programmer’s Guide and Specification (1999), Addison-Wesley Professional
[36] Kumar, S.; Spezzano, F.; Subrahmanian, V.; Faloutsos, C., Edge weight prediction in weighted signed networks, (Data Mining (ICDM), 2016 IEEE 16th International Conference on IEEE (2016)), 221-230
[37] Gajer, P.; Goodrich, M. T.; Kobourov, S. G., A multi-dimensional approach to force-directed layouts of large graphs, International Symposium on Graph Drawing, Springer, 211-221 (2000) · Zbl 1043.68618
[38] S.G. Kobourov, Spring embedders and force directed graph drawing algorithms, arXiv preprint arXiv:1201.3011.
[39] Eades, P., A heuristic for graph drawing, Congressus numerantium, 42, 149-160 (1984)
[40] Chen, C., Information Visualization: Beyond the Horizon (2006), Springer Science & Business Media
[41] A. Paranjape, A.R. Benson, J. Leskovec, Motifs in temporal networks, in: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, WSDM ’17, ACM, New York, NY, USA, 2017, pp. 601-610. doi:10.1145/3018661.3018731. URL:http://doi.acm.org/10.1145/3018661.3018731.
[42] Panzarasa, P.; Opsahl, T.; Carley, K. M., Patterns and dynamics of users’ behavior and interaction: Network analysis of an online community, Journal of the Association for Information Science and Technology, 60, 5, 911-932 (2009)
[43] Kinderman, A. J.; Monahan, J. F., Computer generation of random variables using the ratio of uniform deviates, ACM Transactions on Mathematical Software (TOMS), 3, 3, 257-260 (1977) · Zbl 0387.65006
[44] Agarwal, M. K.; Ramamritham, K.; Bhide, M., Real time discovery of dense clusters in highly dynamic graphs: identifying real world events in highly dynamic environments, Proceedings of the VLDB Endowment, 5, 10, 980-991 (2012)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.