Random acyclic networks

Abstract

Directed acyclic graphs are 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.

4 pages, 2 figures

References in corpus (5)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Organization of Growing Random Networks

Cited by in corpus (16)

• Structure-based control of complex networks with nonlinear dynamics
• Random graphs containing arbitrary distributions of subgraphs
• Potential Theory for Directed Networks
• Gibbs entropy of networks ensembles by cavity methods
• Random graph models for directed acyclic networks
• Modeling scientific-citation patterns and other triangle-rich acyclic networks
• Distance Measures for Dynamic Citation Networks
• Community detection in directed acyclic graphs
• Extreme robustness of scaling in sample space reducing processes explains Zipf's law in diffusion on directed networks
• Influence, originality and similarity in directed acyclic graphs
• Exploring the randomness of Directed Acyclic Networks
• Unevenness of Loop Location in Complex Networks
• Ontologies and tag-statistics
• Power-law intensity distribution in $\gamma$-decay cascades -- Nuclear Structure as a Scale-Free Random Network
• On the Stability of Community Detection Algorithms on Longitudinal Citation Data
• Transforming complex network to the acyclic one