Random graph models for directed acyclic networks

2009/07/24 by Brian Karrer, M. E. J. Newman · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Neural Networks #Combinatorics #Complex Network Analysis Techniques #Computer science #Directed acyclic graph #Directed graph #Discrete mathematics #Graph #Graph theory and applications #Mathematics #Random graph #Theoretical computer science #cond-mat.stat-mech #physics.data-an #physics.soc-ph

paper · pdf · doi:10.1103/physreve.80.046110

published as Phys. Rev. E 80, 046110 (2009) · 14 pages, 5 figures

arxiv created 2009/07/24 · openalex publication_date 2009/10/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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.

Citations

• Detection of topological patterns in complex networks: correlation profile of the internet
• Large-scale structure of time evolving citation networks
• Dynamical and Correlation Properties of the Internet
• Citation Networks in High Energy Physics
• Emergence of scaling in random networks
• Mixing patterns in networks
• Assortative Mixing in Networks
• Evolution of networks
• Random graphs with arbitrary degree distributions and their applications
• On random graphs. I.

Cited by

• Efficient Discovery of Motif Transition Process for Large-Scale Temporal Graphs