Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Research Article
  • Published:
Frontiers of Computer Science Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

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

    Article  Google Scholar 

  16. Wikipedia contributors. Message sequence chart. See https://encyclopedia.thefreedictionary.com/Message+sequence+chartwebsite, 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

    Article  Google Scholar 

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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

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

    Book  Google Scholar 

  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

    Article  Google Scholar 

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

Download references

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).

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, Central South University, Changsha, 410083, China

    Yanni Peng, Xiaoping Fan, Rong Chen, Ziyao Yu, Shi Liu, Yunpeng Chen, Ying Zhao & Fangfang Zhou

  2. Institute of Big Data, Hunan University of Finance and Economics, Changsha, 410205, China

    Xiaoping Fan

  3. Rail Data Research and Application Key Laboratory of Hunan Province, Changsha, 410083, China

    Ying Zhao

Authors
  1. Yanni Peng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiaoping Fan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rong Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ziyao Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Shi Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Yunpeng Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Ying Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Fangfang Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Xiaoping Fan or Ying Zhao.

Additional information

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.

Electronic supplementary material

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Peng, Y., Fan, X., Chen, R. et al. Visual abstraction of dynamic network via improved multi-class blue noise sampling. Front. Comput. Sci. 17, 171701 (2023). https://doi.org/10.1007/s11704-021-0609-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11704-021-0609-0

Keywords

Search

Navigation