Random acyclic networks.
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.
Karrer
Brian
B
Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA.
Newman
M E J
ME
D020387:Food Chain; D008962:Models, Theoretical