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

New Quality Metrics for Dynamic Graph Drawing

  • Conference paper
  • First Online:
Graph Drawing and Network Visualization (GD 2020)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 12590))

Included in the following conference series:

Abstract

In this paper, we present new quality metrics for dynamic graph drawings. Namely, we present a new framework for change faithfulness metrics for dynamic graph drawings, which compare the ground truth change in dynamic graphs and the geometric change in drawings.

More specifically, we present two specific instances, cluster change faithfulness metrics and distance change faithfulness metrics. We first validate the effectiveness of our new metrics using deformation experiments. Then we compare various graph drawing algorithms using our metrics. Our experiments confirm that the best cluster (resp. distance) faithful graph drawing algorithms are also cluster (resp. distance) change faithful.

This work is supported by ARC DP grant.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Archambault, D., Purchase, H.C.: The “map” in the mental map: experimental results in dynamic graph drawing. Int. J. Hum Comput Stud. 71(11), 1044–1055 (2013)

    Article  Google Scholar 

  2. Archambault, D., Purchase, H.C.: Can animation support the visualisation of dynamic graphs? Inf. Sci. 330, 495–509 (2016)

    Article  Google Scholar 

  3. Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall PTR, Upper Saddle River (1998)

    Google Scholar 

  4. Baur, M., et al.: Visone software for visual social network analysis. In: International Symposium on Graph Drawing, pp. 463–464. Springer (2001). https://doi.org/10.1007/3-540-45848-4_47

  5. Beck, F., Burch, M., Diehl, S., Weiskopf, D.: A taxonomy and survey of dynamic graph visualization. In: Computer Graphics Forum, vol. 36, pp. 133–159. Wiley Online Library, Hoboken (2017)

    Google Scholar 

  6. Böhringer, K.F., Paulisch, F.N.: Using constraints to achieve stability in automatic graph layout algorithms. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 43–51 (1990)

    Google Scholar 

  7. Brandes, U., Pich, C.: Eigensolver methods for progressive multidimensional scaling of large data. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 42–53. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70904-6_6

    Chapter  MATH  Google Scholar 

  8. Branke, J.: Dynamic graph drawing. In: Kaufmann, M., Wagner, D. (eds.) Drawing Graphs. LNCS, vol. 2025, pp. 228–246. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44969-8_9

    Chapter  MATH  Google Scholar 

  9. David, A.: Tulip. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 435–437. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45848-4_34

    Chapter  Google Scholar 

  10. Diehl, S., Görg, C.: Graphs, they are changing. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 23–31. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36151-0_3

    Chapter  MATH  Google Scholar 

  11. Eades, P., Hong, S.H., Nguyen, A., Klein, K.: Shape-based quality metrics for large graph visualization. J. Graph Algorithms Appl. 21(1), 29–53 (2017)

    Article  MathSciNet  Google Scholar 

  12. Eades, P., Lai, W., Misue, K., Sugiyama, K.: Preserving the mental map of a diagram. Technical report, Technical Report IIAS-RR-91-16E, Fujitsu Laboratories (1991)

    Google Scholar 

  13. Ellson, J., Gansner, E., Koutsofios, L., North, S.C., Woodhull, G.: Graphviz— open source graph drawing tools. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 483–484. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45848-4_57

    Chapter  MATH  Google Scholar 

  14. Fowlkes, E.B., Mallows, C.L.: A method for comparing two hierarchical clusterings. J. Am. Stat. Assoc. 78(383), 553–569 (1983). https://doi.org/10.1080/01621459.1983.10478008

    Article  MATH  Google Scholar 

  15. Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Softw. Pract. Experience 21(11), 1129–1164 (1991). https://doi.org/10.1002/spe.4380211102

  16. Gansner, E.R., Hu, Y., North, S.: A maxent-stress model for graph layout. IEEE Trans. Visual Comput. Graph. 19(6), 927–940 (2012)

    Article  Google Scholar 

  17. Gansner, E.R., Koren, Y., North, S.: Graph drawing by stress majorization. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31843-9_25

    Chapter  MATH  Google Scholar 

  18. Hu, Y.: Efficient, high-quality force-directed graph drawing. Math. J. 10(1), 37–71 (2005)

    Google Scholar 

  19. Huang, W., Hong, S.H., Eades, P.: Effects of crossing angles. In: 2008 IEEE Pacific Visualization Symposium, pp. 41–46. IEEE (2008)

    Google Scholar 

  20. Hubert, L., Arabie, P.: Comparing partitions. J. Classif. 2(1), 193–218 (1985). https://doi.org/10.1007/BF01908075

    Article  MATH  Google Scholar 

  21. Kruiger, J.F.: tsNET (2017). https://github.com/HanKruiger/tsNET/

  22. Kruiger, J.F., Rauber, P.E., Martins, R.M., Kerren, A., Kobourov, S., Telea, A.C.: Graph layouts by t-SNE. Comput. Graph. Forum 36(3), 283–294 (2017). https://doi.org/10.1111/cgf.13187

    Article  Google Scholar 

  23. Maaten, L.V.D., Hinton, G.: Visualizing data using t-SNE. J. Mach. Learn. Res. 9, 2579–2605 (2008)

    MATH  Google Scholar 

  24. MacQueen, J., et al.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281–297. University of California Press (1967)

    Google Scholar 

  25. Madan, A., Cebrian, M., Moturu, S., Farrahi, K., et al.: Sensing the “health state” of a community. IEEE Pervasive Comput. 11(4), 36–45 (2011)

    Article  Google Scholar 

  26. Meidiana, A., Hong, S.H., Eades, P., Keim, D.: A quality metric for symmetric graph drawings. arXiv preprint arXiv:1910.04974 (2019)

  27. Meidiana, A., Hong, S.-H., Eades, P., Keim, D.: A quality metric for visualization of clusters in graphs. In: Archambault, D., Tóth, C.D. (eds.) GD 2019. LNCS, vol. 11904, pp. 125–138. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-35802-0_10

    Chapter  MATH  Google Scholar 

  28. Meidiana, A., Hong, S.H., Eades, P., Keim, D.: Quality metrics for symmetric graph drawings. In: 2020 IEEE Pacific Visualization Symposium (PacificVis), pp. 11–15. IEEE (2020)

    Google Scholar 

  29. Nguyen, Q., Eades, P., Hong, S.H.: On the faithfulness of graph visualizations. In: 2013 IEEE Pacific Visualization Symposium (PacificVis), pp. 209–216. IEEE (2013)

    Google Scholar 

  30. Noack, A.: An energy model for visual graph clustering. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 425–436. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24595-7_40

    Chapter  MATH  Google Scholar 

  31. Nocaj, A., Ortmann, M., Brandes, U.: Untangling the hairballs of multi-centered, small-world online social media networks. J. Graph Algorithms Appl. 19(2), 595–618 (2015). https://doi.org/10.7155/jgaa.00370

    Article  MathSciNet  MATH  Google Scholar 

  32. Ortmann, M., Klimenta, M., Brandes, U.: A sparse stress model. In: Hu, Y., Nöllenburg, M. (eds.) GD 2016. LNCS, vol. 9801, pp. 18–32. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-50106-2_2

    Chapter  Google Scholar 

  33. Pedregosa, F., et al.: Scikit-learn: Machine learning in Python. J. Mach. Learn. Res. 12, 2825–2830 (2011)

    Google Scholar 

  34. Purchase, H.: Which aesthetic has the greatest effect on human understanding? In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 248–261. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63938-1_67

    Chapter  Google Scholar 

  35. Purchase, H.C., Cohen, R.F., James, M.: Validating graph drawing aesthetics. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 435–446. Springer, Heidelberg (1996). https://doi.org/10.1007/BFb0021827

    Chapter  Google Scholar 

  36. Rand, W.M.: Objective criteria for the evaluation of clustering methods. J. Am. Stat. Assoc. 66(336), 846–850 (1971). https://doi.org/10.1080/01621459.1971.10482356

    Article  Google Scholar 

  37. Tamassia, R., Di Battista, G., Batini, C.: Automatic graph drawing and readability of diagrams. IEEE Trans. Syst. Man Cybern. 18(1), 61–79 (1988). https://doi.org/10.1109/21.87055

    Article  Google Scholar 

  38. Torgerson, W.S.: Multidimensional scaling: I. theory and method. Psychometrika 17(4), 401–419 (1952). https://doi.org/10.1007/BF02288916

  39. Tufte, E.R., Goeler, N.H., Benson, R.: Envisioning information, vol. 126. Graphics press Cheshire, CT (1990)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Sydney, Sydney, Australia

    Amyra Meidiana, Seok-Hee Hong & Peter Eades

Authors
  1. Amyra Meidiana
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Seok-Hee Hong
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Peter Eades
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Amyra Meidiana .

Editor information

Editors and Affiliations

  1. LaBRI, University of Bordeaux, Talence, France

    David Auber

  2. Charles University, Prague, Czech Republic

    Pavel Valtr

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Meidiana, A., Hong, SH., Eades, P. (2020). New Quality Metrics for Dynamic Graph Drawing. In: Auber, D., Valtr, P. (eds) Graph Drawing and Network Visualization. GD 2020. Lecture Notes in Computer Science(), vol 12590. Springer, Cham. https://doi.org/10.1007/978-3-030-68766-3_35

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-68766-3_35

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-68765-6

  • Online ISBN: 978-3-030-68766-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation