Random Acyclic Networks
Authors:
- 23 March 2009
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 102 (12) , 128701
Abstract
Directed acyclic graphs make up a fundamental class of networks that includes citation networks, food webs, and family trees, among others. Here we define a random graph model for directed acyclic graphs and give solutions for a number of the model’s properties, including connection probabilities and component sizes, as well as a fast algorithm for simulating the model on a computer. We compare the predictions of the model to a real-world network of citations between physics papers and find surprisingly good agreement, suggesting that the structure of the real network may be quite well described by the random graph.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Evolution of networksAdvances in Physics, 2002
- Random graphs with arbitrary degree distributions and their applicationsPhysical Review E, 2001
- Organization of growing random networksPhysical Review E, 2001
- Emergence of Scaling in Random NetworksScience, 1999
- A critical point for random graphs with a given degree sequenceRandom Structures & Algorithms, 1995
- A stochastic theory of community food webs I. Models and aggregated dataProceedings of the Royal Society of London. B. Biological Sciences, 1985
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980
- A general theory of bibliometric and other cumulative advantage processesJournal of the American Society for Information Science, 1976
- Networks of Scientific PapersScience, 1965