Drawing Power Law Graphs

Andersen, Reid and Chung, Fan and Lu, Lincoln (2004) Drawing Power Law Graphs. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 12-17 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_2).

Full text not available from this repository.


We present methods for drawing graphs that arise in various information networks. It has been noted that many realistic graphs have a power law degree distribution and exhibit the small world phenomenon. Our methods are influenced by recent developments in the modeling of such graphs.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_2
Classifications:P Styles > P.720 Straight-line
M Methods > M.400 Force-directed / Energy-based
ID Code:557

Repository Staff Only: item control page


R. Andersen, J. Chung and L. Lu, Analyzing the small world phenomenon using a hybrid model with local network flow, Proceedings of the Third Workshop on Algorithms and Models for the Web-Graph (2004).

F. Chung and L. Lu, Average distances in random graphs with given expected degree sequences, Proceedings of National Academy of Science, 99 (2002).

F. Chung and L. Lu, The small world phenomenon in hybrid power law graphs Complex Networks, (EDS. E. Ben-Naim et. al.), Springer-Verlag, (2004).

Fabrikant, E. Koutsoupias and C.H. Papadimitriou, Heuristically optimized trade-offs: a new paradigm for power laws in the Internet, STOC 2002.

N. Garg, J.Könemann, Faster and simpler algorithms for multicommodity flow and other fractional packing problems. Technical Reort, Max-Planck-Institut für Informatik, Saarbrücken, Germany (1997).

Jerry Grossman, Patrick Ion, and Rodrigo De Castro, Facts about Erdös Numbers and the Collaboration Graph, http://www.oakland.edu/~grossman/trivia.html.

J. Kleinberg, The small-world phenomenon: An algorithmic perspective, Proc. 32nd ACM Symposium on Theory of Computing, 2000.

M. Mitzenmacher, A Brief History of Generative Models for Power Law and Lognormal Distributions, Internet Math. 1 (2003), no. 2.