title: Random graph models for directed acyclic networks.
abstract: We study random graph models for directed acyclic graphs, a class of networks that includes citation networks, food webs, and feed-forward neural networks among others. We propose two specific models roughly analogous to the fixed edge number and fixed edge probability variants of traditional undirected random graphs. We calculate a number of properties of these models, including particularly the probability of connection between a given pair of vertices, and compare the results with real-world acyclic network data finding that theory and measurements agree surprisingly well-far better than the often poor agreement of other random graph models with their corresponding real-world networks.
authors.affiliation: Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA.
authors.forename: Brian
authors.initials: B
authors.lastname: Karrer
authors.forename: M E J
authors.initials: ME
authors.lastname: Newman
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D008962:Models, Theoretical