Random graph models for directed acyclic networks
arXiv:0907.4346 · doi:10.1103/PhysRevE.80.046110
Abstract
We study random graph models for directed acyclic graphs, an important 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.
14 pages, 5 figures
References in corpus (14)
- Emergence of scaling in random networks
- Assortative mixing in networks
- Random graphs with arbitrary degree distributions and their applications
- Evolution of networks
- Mixing patterns in networks
- How Popular is Your Paper? An Empirical Study of the Citation Distribution
- Dynamical and correlation properties of the Internet
- Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
- The phase transition in inhomogeneous random graphs
- Pattern Detection in Complex Networks: Correlation Profile of the Internet
- Giant strongly connected component of directed networks
- Citation Networks in High Energy Physics
- Large-scale structure of time evolving citation networks
- Random acyclic networks
Cited by in corpus (23)
- Random walks and diffusion on networks
- Modern temporal network theory: A colloquium
- Edge direction and the structure of networks
- Statistical Inference for Valued-Edge Networks: Generalized Exponential Random Graph Models
- Coauthorship and citation in scientific publishing
- Transitive Reduction of Citation Networks
- On the Complexity of Newman's Community Finding Approach for Biological and Social Networks
- Practical Bounds on Optimal Caching with Variable Object Sizes
- DYMOND: DYnamic MOtif-NoDes Network Generative Model
- Community detection in directed acyclic graphs
- Complex-valued information entropy measure for networks with directed links (digraphs). Application to citations by community agents with opposite opinions
- Influence, originality and similarity in directed acyclic graphs
- Structural Analysis of Sparse Neural Networks
- Universal hierarchical behavior of citation networks
- Using Motif Transitions for Temporal Graph Generation
- ProvGen: generating synthetic PROV graphs with predictable structure
- Finite size effects. The averaged eigenvalue density of Wigner random sign real symmetric matrices
- ResNetX: a more disordered and deeper network architecture
- Formal vs self-organised knowledge systems: a network approach
- Transforming complex network to the acyclic one
- Uncovering Longitudinal Healthcare Utilization from Patient-Level Medical Claims Data
- Growth of Random Trees by Leaf Attachment
- Block-corrected Modularity for Community Detection