Abstract
Private industry datasets and public records contain more information than any algorithm can efficiently process or any person can reasonably interpret. This is a basic problem faced by researchers in visual analytics. Graph visualizations (a common large dataset representation) can organize relationships and entities in a visually accessible manner. Our work applies graph sampling and summarization to the interactive visualization of complex networks. We implemented several unbiased sampling techniques to facilitate large scale graph analysis. Moreover, we show biased sampling techniques can improve visualization by emphasizing key graph nodes. We combine algorithmic processing with human interpretations by allowing users to adjust sampling parameters, inspect sample graph visualizations, and compare sample distributions. Summarization also reduces graph complexity. By adjusting rendered graph density, users can navigate and maintain constant on-screen density.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cohen, R., Havlin, S.: Complex Networks: Structure, Robustness and Function, 1st edn. Cambridge University Press, New York (2010)
Hidalgo, C.A., Blumm, N., Barabási, A.-L., Christakis, N.A.: A dynamic network approach for the study of human phenotypes. PLoS Comput. Biol. 5, e1000353 (2009). doi:10.1371/journal.pcbi.1000353
Gehrke, J., Ginsparg, P., Kleinberg, J.: Overview of the: KDD Cup. ACM SIGKDD Explor. 5(2003), 149–151 (2003)
Jiang, J., Wilson, C., Wang, X., Sha, W., Huang, P., Dai, Y., Zhao, B.Y.: Understanding latent interactions in online social networks. ACM Trans. Web 7, 18 (2013)
Tozal, M.E.: The internet: a system of interconnected autonomous systems. In: Rassa, B. (ed.) Proceedings of the 11th Annual IEEE Systems Conference, Orlando, FL pp. 1–8 (2016)
Cem, E., Tozal, M.E., Sarac, K.: Impact of sampling design in estimation of graph characteristics. In: Wang, Y., Xu, K. (eds.) Proceedings of the 32nd International Performance Computing and Communications Conference (IPCCC), San Diego, CA, pp. 1–10 (2013)
Ahmed, N.K., Rossi, R.A.: Interactive visual graph analytics on the web. In: Hamilton, C. (ed.) Proceedings of the International 9th AAAI Conference on Web and Social Media, Oxford, UK, pp. 566–569 (2015)
Rossi, R.A., Ahmed, N.K.: An interactive data repository with visual analytics. ACM SIGKDD Explor. Newslett. 17, 37–41 (2015)
Ingram, A., Wang, X., Ribarsky, W.: Towards the establishment of a framework for intuitive multi-touch interaction design. In: Tortora, G., Levialdi, S., Tucci, M. (eds.) Proceedings of the International Working Conference on Advanced Visual Interfaces, Capri Island, Italy, pp. 66–73 (2012)
Baur, D., Lee, B., Carpendale, S.: TouchWave: kinetic multi-touch manipulation for hierarchical stacked graphs. In: Shaer, O., Shen, C. (eds.) Proceedings of the ACM International Conference on Interactive Tabletops and Surfaces, Cambridge, MA, pp. 255–264 (2012)
Drucker, S.M., Fisher, D., Sadana, R., Herron, J., Schraefel, M.: TouchViz: a case study comparing two interfaces for data analytics on tablets. In: Mackay, W.E. (ed.) Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, Paris, France, pp. 2301–2310 (2013)
Chau, D.H., Faloutsos, C., Tong, H., Hong, J., Gallagher, B., Eliassi-Rad, T.: GRAPHITE: a visual query system for large graphs. In: Wu, X. (ed.) Proceedings of the IEEE International Conference on Data Mining Workshops, Las Vegas, NV, pp. 963–966 (2008)
Chau, D.H., Kittur, A., Hong, J., Faloutsos, C.: Apolo: making sense of large network data by combining rich user interaction and machine learning. In: Tan, D. (ed.) Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, Vancouver, BC, pp. 167–176 (2011)
Hu, Y.: Algorithms for visualizing large networks. In: Naumann, U., Schenk, O. (eds.) Combinatorial Scientific Computing, 1st edn., pp. 525–545. Chapman and Hall/CRC, Berkeley (2012)
Eades, P.: A heuristic for graph drawing. Congressus numerantium 42, 146–160 (1984)
Hendrickson, B., Leland, R.W.: A multi-level algorithm for partitioning graphs. In: Karin, S. (ed.) Proceedings of the ACM/IEEE Conference on Supercomputing, San Diego, CA (1995). Article 28
Navlakha, S., Rastogi, R., Shrivastava, N.: Graph summarization with bounded error. In: Lakshmanan, L., Ng, R.T., Shasha, D. (eds.) Proceedings of the ACM SIGMOD International Conference on Management of Data, Vancouver, BC, pp. 419–432 (2008)
Hu, P., Lau, W.C.: A survey and taxonomy of graph sampling, CoRR 1308.5865 (2013)
Csardi, G., Nepusz, T.: The igraph software package for complex network research. Int. J. Complex Syst. 1695, 1–9 (2006)
Kurant, M., Markopoulou, A., Thiran, P.: Towards unbiased BFS sampling. IEEE J. Sel. Area Commun. 29, 1799–1809 (2011)
Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002)
Acknowledgments
This research was funded by the Center for Visual and Decision Informatics (CVDI), an Industry/University Cooperative Research Center of the National Science Foundation, members from an Industry Advisory Board, and University matching funds. Information about CVDI can be found at nsfcvdi.org. We thank Dr. Raju Gottumukkala, Sivarama K. Venna, and Maryam H. Beisafar for earlier Analytics Server work.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Lipari, N.G., Borst, C.W., Tozal, M.E. (2016). Visual Analytics Using Graph Sampling and Summarization on Multitouch Displays. In: Bebis, G., et al. Advances in Visual Computing. ISVC 2016. Lecture Notes in Computer Science(), vol 10072. Springer, Cham. https://doi.org/10.1007/978-3-319-50835-1_42
Download citation
DOI: https://doi.org/10.1007/978-3-319-50835-1_42
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-50834-4
Online ISBN: 978-3-319-50835-1
eBook Packages: Computer ScienceComputer Science (R0)