Abstract
The need to visualize large and complex networks has strongly increased in the last decade. Although networks with more than 1000 vertices seem to be prohibitive for a comprehensive layout, real-world networks exhibit a very inhomogenous edge density that can be harnessed to derive an aesthetic and structured layout. Here, we will present a heuristic that finds a spanning tree with a very low average spanner property for the non-tree edges, the so-called backbone of a network. This backbone can then be used to apply a modified tree-layout algorithm to draw the whole graph in a way that highlights dense parts of the graph, so-called clusters, and their inter-connections.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Andersen, R., Chung, F., Lu, L.: Drawing power law graphs. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, Springer, Heidelberg (2005)
Baur, M., Brandes, U.: Crossing reduction in circular layouts. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, Springer, Heidelberg (2004)
Carriére, J., Kazman, R.: Interacting with huge hierarchies: Beyond cone trees. In: Proceedings of the ACM conference on Information Visualization 1995, pp. 74–81. ACM Press, New York (1995)
Derényi, I., Palla, G., Vicsek, T.: Clique percolation in random networks. Phys. Rev. Lett. 94, 160–202 (2005)
Fekete, J.-D., Wang, D., Dang, N., Aris, A., Plaisant, C.: Overlaying graph links on treemaps. In: Proceedings of the IEEE Symposium on Information Visualization (InfoVis’03), IEEE Computer Society Press, Los Alamitos (2003)
Fruchtermann, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Software - Practice and Experience 21(11), 1129–1164 (1991)
Garey, M.R., Johnson, D.S.: Computers and intractability. W.H. Freeman and Company, New York (1979)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99, 7821–7826 (2002)
Herman, I., Melançon, G., de Ruiter, M M., Delest, M.: Lecture Notes in Computer Science. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, p. 392. Springer, Heidelberg (1997)
Lehmann, K.A., Kottler, S.: Visualizing Large and Clustered Networks. Technical Report of the Wilhelm-Schickard-Institut, WSI-2006-06, ISSN 0946-3852 (September 2006)
Newman, M., Barabasi, A.-L., Watts, D.J.: The structure and dynamics of networks. Princeton University Press, Princeton (2006)
Noack, A.: An energy model for visual graph clustering. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, Springer, Heidelberg (2004)
Noack, A.: Energy-based clustering of graphs with nonuniform degrees. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, Springer, Heidelberg (2006)
Palla, G., Derényi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814 (2005)
Mueller, S.: OrganicLayouter in the yFiles library, Version 2.2. http://www.yworks.com
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Lehmann, K.A., Kottler, S. (2007). Visualizing Large and Clustered Networks. In: Kaufmann, M., Wagner, D. (eds) Graph Drawing. GD 2006. Lecture Notes in Computer Science, vol 4372. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70904-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-70904-6_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70903-9
Online ISBN: 978-3-540-70904-6
eBook Packages: Computer ScienceComputer Science (R0)