RandomGraphs
Jump to navigation
Jump to search
I am interested in different kinds of random graphs and their relationship to natural (particularly social) networks. By applying various statistical measurements to computer generated examples, some of the various ways that randomly generated graphs differ from one another were seen. (See the home grown software and writeup if interested.) I would like to apply these statistical measurements to real world graphs such as ====WikiWikis or the Advogato web of trust. This page serves as a notebook of resources aiding me in this journey.
==
====Basic Ideas
==
Three robust measures of network topology:
- average path length
- clustering coefficient
- degree distribution
Corresponding three flavors of random graphs:
- Erdos-Renyi (classical, 1950s), small path length
- small world (1998), high clustering coefficient
- scale-free (1999), scale free degree distribution
====Key Papers
==
- Statistical Mechanics of Complex Networks abs||http://lanl.arxiv.org/abs/cond-mat/0106096] (Albert & [[Barabasi])
- Random evolution of massive graphs abs (Fan Chung, et. al.)
- Are randomly grown graphs really random? abs||http://www.santafe.edu/sfi/publications/wpabstract/200105025] (Callaway, Hopcroft, Kleinberg, [[Newman], and Strogatz) (Presents a growing network model.)
- Cluster Growth in Two Growing Network Models growthintwogrowingnetworkmodels.pdf PDF (David Lancaster) (Presents two related growing network models.)
====Some People
==
- Albert-Laszlo Barabasi||http://www.nd.edu/~alb/] ([[arXiv])
- Fan Chung
- S. N. Dorogovtsev||http://www.fc.up.pt/fis/sdorogov/] ([[arXiv])
- M. E. J. Newman||http://www.santafe.edu/~mark/] ([[arxiv])
====Next Papers to View
==
- Evolution of Networks||http://lanl.arxiv.org/abs/cond-mat/0106144] ([[Dorogovtsev] & Mendes)
- How to generate a random growing network||http://lanl.arxiv.org/abs/cond-mat/0206132] ([[Dorogovtsev], Mendes, Samukhin)
- Random graphs with arbitrary degree distributions and their applications||http://lanl.arxiv.org/abs/cond-mat/0007235] ([[Newman], Strogatz, Watts)
Last Edit: Mon, 14 Apr 2003 02:30:28 -0700 Revisions: 8