Visualizing Large and Clustered Networks

Lehmann, Katharina A. and Kottler, Stephan (2007) Visualizing Large and Clustered Networks. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 240-251 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_24).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_24
Classifications:M Methods > M.999 Others
P Styles > P.999 Others
G Algorithms and Complexity > G.350 Clusters
ID Code:779

Repository Staff Only: item control page

References

Reid Andersen, Fan Chung, and Linyuan Lu. Drawing power law graphs. In Proceedings of the 12th Symposium on Graph Drawing (GD'04), 2004.

Michael Baur and Ulrik Brandes. Crossing reduction in circular layouts. In Proceedings of the 30th Workshop on Graph-Theoretic Concepts in Computer Science (WG'04), 2004.

J. Carriere and R. Kazman. Interacting with huge hierarchies: Beyond cone trees. In Proceedings of the ACM conference on Information Visualization 1995, pages 74-81, 1995.

I. Derenyi, G. Palla, and T. Vicsek. Clique percolation in random networks. Phys. Rev. Lett., 94:160-202, 2005.

Jean-Daniel Fekete, David Wang, Niem Dang, Aleks Aris, and Catherine Plaisant. Overlaying graph links on treemaps. In Proceedings of the IEEE Symposium on Information Visualization (InfoVis'03), 2003.

T.M.J. Fruchtermann and E.M. Reingold. Graph drawing by force-directed placement. Software - Practice and Experience, 21(11):1129-1164, 1991.

Michael R. Garey and David S. Johnson. Computers and intractability. W.H. Freeman and Company, New York, 1979.

Michelle Girvan and M.E.J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99:7821-7826, 2002.

Ivan Herman, Guy Melancon, Maurice M. de Ruiter, and Maylis Delest. Lecture Notes in Computer Science, chapter Latour - A tree visualization system, page 392ff. Springer Verlag, Berlin, 2000.

Katharina A. Lehmann and Stephan Kottler Visualizing Large and Clustered Networks. Technical Report of the Wilhelm-Schickard-Institut, WSI-2006-06, ISSN 0946-3852, September 2006.

Mark Newman, Albert-Laszlo Barabasi, and Duncan J. Watts. The structure and dynamics of networks. Princeton University Press, 2006.

Andreas Noack. An energy model for visual graph clustering. In Proceedings of the 11th International Symposium on Graph Drawing (GD'03), 2004.

Andreas Noack. Energy-based clustering of graphs with nonuniform degrees. In Proceedings of the 13th International Symposium on Graph Drawing (GD'05), 2005.

G. Palla, I. Derenyi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435:814, 2005.

OrganicLayouter in the yFiles library Sebastian Mueller. www.yworks.com, Version 2.2.