Visual abstraction of dynamic network via improved multi-class blue noise sampling

Abstract

Massive sequence view (MSV) is a classic timeline-based dynamic network visualization approach. However, it is vulnerable to visual clutter caused by overlapping edges, thereby leading to unexpected misunderstanding of time-varying trends of network communications. This study presents a new edge sampling algorithm called edge-based multi-class blue noise (E-MCBN) to reduce visual clutter in MSV. Our main idea is inspired by the multi-class blue noise (MCBN) sampling algorithm, commonly used in multi-class scatterplot decluttering. First, we take a node pair as an edge class, which can be regarded as an analogy to classes in multi-class scatterplots. Second, we propose two indicators, namely, class overlap and inter-class conflict degrees, to measure the overlapping degree and mutual exclusion, respectively, between edge classes. These indicators help construct the foundation of migrating the MCBN sampling from multi-class scatterplots to dynamic network samplings. Finally, we propose three strategies to accelerate MCBN sampling and a partitioning strategy to preserve local high-density edges in the MSV. The result shows that our approach can effectively reduce visual clutters and improve the readability of MSV. Moreover, our approach can also overcome the disadvantages of the MCBN sampling (i.e., long-running and failure to preserve local high-density communication areas in MSV). This study is the first that introduces MCBN sampling into a dynamic network sampling.

Graphical abstract

Keywords

dynamic network visualization / massive sequence view / multi-class blue noise sampling / visual abstraction

Yanni Peng is currently pursuing the PhD degree with Central South University, China. Her research interests are visualization and visual analytics

Xiaoping Fan is a professor in Central South University, China. His main research interests include intelligent information processing, and analysis and application of financial big data

Rong Chen is currently pursuing the bachelor’s degree with Central South University, China. Her research interests are data analysis and artificial intelligence

Ziyao Yu is currently pursuing the bachelor’s degree with Central South University, China. Her research interests are visualization and data analysis

Shi Liu is currently pursuing the bachelor’s degree with Central South University, China. His research interests are visualization and data analysis

Yunpeng Chen is currently pursuing the PhD degree with Central South University, China. His research interests are visualization and visual analysis

Ying Zhao is a professor in Central South University, China. His main research interests include visualization and visual analytics

Fangfang Zhou is a professor in Central South University, China. Her research interests include visualization and visual analytics

References

[1] Pan J C , Han D M , Guo F Z , Zhou D W , Cao N , He J R , Xu M L , Chen W . RCAnalyzer: visual analytics of rare categories in dynamic networks. Frontiers of Information Technology & Electronic Engineering, 2020, 21( 4): 491– 506

[2] Han D , Pan J , Zhao X , Chen W . NetV.js: A web-based library for high-efficiency visualization of large-scale graphs and networks. Visual Informatics, 2012, 5( 1): 61– 66

[3] Chen W , Guo F , Han D , Pan J , Nie X , Xia J , Zhang X . Structure-based suggestive exploration: a new approach for effective exploration of large networks. IEEE Transactions on Visualization and Computer Graphics, 2019, 25( 1): 555– 565

[4] Beck F, Burch M, Diehl S, Weiskopf D. The state of the art in visualizing dynamic graphs. In: Proceedings of the 16th Eurographics Conference on Visualization. 2014, 83– 103

[5] van den Elzen S , Holten D , Blaas J , van Wijk J J . Dynamic network visualization with extended massive sequence views. IEEE Transactions on Visualization and Computer Graphics, 2014, 20( 8): 1087– 1099

[6] van den Elzen S, Holten D, Blaas J, van Wijk J J. Reordering massive sequence views: enabling temporal and structural analysis of dynamic networks. In: Proceedings of 2013 IEEE Pacific Visualization Symposium. 2013, 33– 40

[7] Cornelissen B, Holten D, Zaidman A, Moonen L, van Wijk J J, van Deursen A. Understanding execution traces using massive sequence and circular bundle views. In: Proceedings of the 15th International Conference on Program Comprehension. 2007, 49– 58

[8] Mastrandrea R , Fournet J , Barrat A . Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys. PLoS One, 2015, 10( 9): e0136497–

[9] Cui Q , Ward M , Rundensteiner E , Yang J . Measuring data abstraction quality in multiresolution visualizations. IEEE Transactions on Visualization and Computer Graphics, 2006, 12( 5): 709– 716

[10] Eick S E, Ward A. An interactive visualization for message sequence charts. In: Proceedings of the 4th Workshop on Program Comprehension. 1996, 2– 8

[11] Jerding D F, Stasko J T, Ball T. Visualizing interactions in program executions. In: Proceedings of the 19th International Conference on Software Engineering. 1997, 360– 370

[12] Dang T N , Pendar N , Forbes A G . TimeArcs: visualizing fluctuations in dynamic networks. Computer Graphics Forum, 2016, 35( 3): 61– 69

[13] Jerding D F , Stasko J T . The information mural: a technique for displaying and navigating large information spaces. IEEE Transactions on Visualization and Computer Graphics, 1998, 4( 3): 257– 271

[14] Zhao Y , She Y , Chen W , Lu Y , Xia J , Chen W , Liu J , Zhou F . EOD edge sampling for visualizing dynamic network via massive sequence view. IEEE Access, 2018, 6 : 53006– 53018

[15] Wei L Y . Multi-class blue noise sampling. ACM Transactions on Graphics, 2010, 29( 4): 79–

[16] Wikipedia contributors. Message sequence chart. See encyclopedia.thefreedictionary.com/Message+sequence+chart website, 2020

[17] Holten D, Cornelissen B, van Wijk J J. Trace visualization using hierarchical edge bundles and massive sequence views. In: Proceedings of the 4th IEEE International Workshop on Visualizing Software for Understanding and Analysis. 2007, 47– 54

[18] Cornelissen B , Zaidman A , Holten D , Moonen L , van Deursen A , van Wijk J J . Execution trace analysis through massive sequence and circular bundle views. Journal of Systems and Software, 2008, 81( 12): 2252– 2268

[19] Bach B . Unfolding dynamic networks for visual exploration. IEEE Computer Graphics and Applications, 2016, 36( 2): 74– 82

[20] Linhares C D G , Ponciano J R , Pereira F S F , Rocha L E C , Paiva J G S , Travencolo B A N . A scalable node ordering strategy based on community structure for enhanced temporal network visualization. Computers & Graphics, 2019, 84 : 185– 198

[21] Ponciano J R , Linhares C D G , Melo S L , Lima L V , Travencolo B A N . Visual analysis of contact patterns in school environments. Informatics in Education, 2020, 19( 3): 455– 472

[22] Yue X , Shu X , Zhu X , Du X , Yu Z , Papadopoulos D , Liu S . BitExTract: interactive visualization for extracting bitcoin exchange intelligence. IEEE Transactions on Visualization and Computer Graphics, 2019, 25( 1): 162– 171

[23] Linhares C D G, Travençolo B A N, Paiva J G S, Rocha L E C. DyNetVis: a system for visualization of dynamic networks. In: Proceedings of 2017 Symposium on Applied Computing. 2017, 187– 194

[24] Viola I, Chen M, Isenberg T. Visual abstraction. In: Chen M, Hauser H, Rheingans P, Scheuermann G, eds. Foundations of Data Visualization. Cham: Springer International Publishing, 2020

[25] Zhou Z , Meng L , Tang C , Zhao Y , Guo Z , Hu M , Chen W . Visual abstraction of large Scale geospatial origin-destination movement data. IEEE Transactions on Visualization and Computer Graphics, 2019, 25( 1): 43– 53

[26] Weng D , Zheng C , Deng Z , Ma M , Bao J , Zheng Y , Xu M , Wu Y . Towards better bus networks: a visual analytics approach. IEEE Transactions on Visualization and Computer Graphics, 2021, 27( 2): 817– 827

[27] Huang Z S , Zhao Y , Chen W , Gao S , Yu K , Xu W , Tang M , Zhu M , Xu M . A natural-language-based visual query approach of uncertain human trajectories. IEEE Transactions on Visualization and Computer Graphics, 2020, 26( 1): 1256– 1266

[28] Wang J , Wu J , Cao A , Zhou Z , Zhang H , Wu Y . Tac-Miner: visual tactic mining for multiple table tennis matches. IEEE Transactions on Visualization and Computer Graphics, 2021, 27( 6): 2770– 2782

[29] Chen W , Lao T , Xia J , Huang X , Zhu B . GameFlow: visualizing NBA game data. IEEE Transactions on Multimedia, 2016, 18( 11): 2247– 2256

[30] Wang M , Lin Y , Tian Q , Si G . Transfer learning promotes 6G wireless communications: recent advances and future challenges. IEEE Transactions on Reliability, 2021, 70( 2): 790– 807

[31] Zhao Y , Luo X , Lin X , Wang H , Kui X , Zhou F , Wang J , Chen Y , Chen W . Visual analytics for electromagnetic situation awareness in radio monitoring and management. IEEE Transactions on Visualization and Computer Graphics, 2020, 26( 1): 590– 600

[32] Zhou F , Lin X , Liu C , Zhao Y , Xu P , Ren L , Xue T , Ren L . A survey of visualization for smart manufacturing. Journal of Visualization, 2019, 22( 2): 419– 435

[33] Li G , Wang J , Shen H W , Chen K , Shan G , Lu Z . CNNPruner: pruning convolutional neural networks with visual analytics. IEEE Transactions on Visualization and Computer Graphics, 2021, 27( 2): 1364– 1373

[34] Zhao Y , Luo F , Chen M , Wang Y , Xia J , Zhou F , Wang Y , Chen Y , Chen W . Evaluating multi-dimensional visualizations for understanding fuzzy clusters. IEEE Transactions on Visualization and Computer Graphics, 2019, 25( 1): 12– 21

[35] Xia J Z , Zhang Y H , Ye H , Wang Y , Jiang G , Zhao Y , Xie C , Kui X Y , Liao S H , Wang W P . SuPoolVisor: a visual analytics system for mining pool surveillanc. Frontiers of Information Technology & Electronic Engineering, 2020, 21( 4): 507– 523

[36] Du F , Shneiderman B , Plaisant C , Malik S , Perer A . Coping with volume and variety in temporal event sequences: strategies for sharpening analytic focus. IEEE Transactions on Visualization and Computer Graphics, 2017, 23( 6): 1636– 1649

[37] Ellis G , Dix A . A taxonomy of clutter reduction for information visualisation. IEEE Transactions on Visualization and Computer Graphics, 2007, 13( 6): 1216– 1223

[38] Shurkhovetskyy G , Andrienko N , Andrienko G , Fuchs G . Data abstraction for visualizing large time series. Computer Graphics Forum, 2018, 37( 1): 125– 144

[39] Song S , Shao Y , Du Y . Survey of sampling methods. Journal of Data Acquisition & Processing, 2016, 31( 3): 452– 463

[40] Bertini E , Santucci G . Give chance a chance: modeling density to enhance scatter plot quality through random data sampling. Information Visualization, 2006, 5( 2): 95– 110

[41] Chen H , Chen W , Mei H , Liu Z , Zhou K , Chen W , Gu W , Ma K L . Visual abstraction and exploration of multi-class scatterplots. IEEE Transactions on Visualization and Computer Graphics, 2014, 20( 12): 1683– 1692

[42] Hu R , Sha T , van Kaick O , Deussen O , Huang H . Data sampling in multi-view and multi-class scatterplots via set cover optimization. IEEE Transactions on Visualization and Computer Graphics, 2020, 26( 1): 739– 748

[43] Johansson J , Cooper M . A screen space quality method for data abstraction. Computer Graphics Forum, 2008, 27( 3): 1039– 1046

[44] Bertini E , Santucci G . Improving visual analytics environments through a methodological framework for automatic clutter reduction. Journal of Visual Languages & Computing, 2011, 22( 3): 194– 212

[45] Ellis G, Dix A. The plot, the clutter, the sampling and its lens: occlusion measures for automatic clutter reduction. In: Proceedings of Working Conference on Advanced Visual Interfaces. 2006, 266– 269

[46] Zhou Z , Ma Y , Zhang Y , Liu Y , Liu Y , Zhang L , Deng S . Context-aware visual abstraction of crowded parallel coordinates. Neurocomputing, 2021, 459 : 23– 34

[47] Liu M , Shi J , Cao K , Zhu J , Liu S . Analyzing the training processes of deep generative models. IEEE Transactions on Visualization and Computer Graphics, 2018, 24( 1): 77– 87

[48] Zhao Y , Shi J , Liu J , Zhao J , Zhou F , Zhang W , Chen K , Zhao X , Zhu C , Chen W . Evaluating Effects of Background Stories on Graph Perception. IEEE Transactions on Visualization and Computer Graphics, 2021,

[49] Maiya A S, Berger-Wolf T Y. Benefits of bias: towards better characterization of network sampling. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011, 105– 113

[50] Ribeiro B, Towsley D. Estimating and sampling graphs with multidimensional random walks. In: Proceedings of the 10th ACM SIGCOMM conference on Internet measurement. 2010, 390– 403

[51] Ahmed N K, Berchmans F, Neville J, Kompella R. Time-based sampling of social network activity graphs. In: Proceedings of the 8th Workshop on Mining and Learning with Graphs. 2010, 1– 9

[52] Ahmed N K , Neville J , Kompella R . Network sampling: from static to streaming graphs. ACM Transactions on Knowledge Discovery from Data, 2014, 8( 2): 7–

[53] Ahmed N K, Duffield N, Neville J, Kompella R. Graph sample and hold: a framework for big-graph analytics. In: Proceedings of the 20th SIGKDD International Conference on Knowledge Discovery and Data Mining. 2014, 1446−1455

[54] Aggarwal C C, Zhao Y, Yu P S. Outlier detection in graph streams. In: Proceedings of the 27th International Conference on Data Engineering. 2011, 399– 409

[55] Lim Y, Kang U. MASCOT: memory-efficient and accurate sampling for counting local triangles in graph streams. In: Proceedings of the 21st SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015, 685– 694

[56] de Stefani L, Epasto A, Riondato M, Upfal E. TRIÈST: counting local and global triangles in fully- dynamic streams with fixed memory size. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016, 825– 834

[57] Sikdar S, Chakraborty T, Sarkar S, Ganguly N, Mukherjee A. ComPAS: community preserving sampling for streaming graphs. In: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems. 2018, 184– 192

[58] Zhang J , Zhu K , Pei Y , Fletcher G , Pechenizkiy M . Cluster-preserving sampling from fully-dynamic streaming graphs. Information Sciences, 2019, 482 : 279– 300

[59] Zhou Z , Shi C , Shen X , Cai L , Wang H , Liu Y , Zhao Y , Chen W . Context-aware sampling of large networks via graph representation learning. IEEE Transactions on Visualization and Computer Graphics, 2021, 27( 2): 1709– 1719

[60] Zhao Y , Jiang H , Chen Q A , Qin Y , Xie H , Wu Y , Liu S , Zhou Z , Xia J , Zhou F . Preserving minority structures in graph sampling. IEEE Transactions on Visualization and Computer Graphics, 2021, 27( 2): 1698– 1708

[61] Robert C P, Casella G. Monte Carlo Statistical Methods. 2nd ed. New York: Springer Publishing Company, 2004

[62] Stehlé J , Voirin N , Barrat A , Cattuto C , Colizza V , Isella L , Régis C , Pinton J F , Khanafer N , van den Broeck W , Vanhems P . Simulation of an SEIR infectious disease model on the dynamic contact network of conference attendees. BMC Medicine, 2011, 9( 1): 87–

[63] Sun J, Faloutsos C, Papadimitriou S, Yu P S. GraphScope: Parameter-free mining of large time-evolving graphs. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2007, 687– 696

Acknowledgements

The work was supported in part by the National Key Research and Development Program of China (2018YFB1700403), the Special Funds for the Construction of an Innovative Province of Hunan (2020GK2028), the National Natural Science Foundation of China (Grant Nos. 61872388, 62072470), and the Natural Science Foundation of Hunan Province (2020JJ4758).

RIGHTS & PERMISSIONS

2021 Higher Education Press 2021