Longest Path in the Price Model
arXiv:1903.03667 · doi:10.1038/s41598-020-67421-8
Abstract
The Price model, the directed version of the Barabási-Albert model, produces a growing directed acyclic graph. We look at variants of the model in which directed edges are added to the new vertex in one of two ways: using cumulative advantage (preferential attachment) choosing vertices in proportion to their degree, or with random attachment in which vertices are chosen uniformly at random. In such networks, the longest path is well defined and in some cases is known to be a better approximation to geodesics than the shortest path. We define a reverse greedy path and show both analytically and numerically that this scales with the logarithm of the size of the network with a coefficient given by the number of edges added using random attachment. This is a lower bound on the length of the longest path to any given vertex and we show numerically that the longest path also scales with the logarithm of the size of the network but with a larger coefficient that has some weak dependence on the parameters of the model.
arXiv commentPost-peer-review, pre-copyedit version of article to be published in Scientific Reports
References in corpus (13)
- Emergence of scaling in random networks
- Organization of Growing Random Networks
- Scale-Free Networks Generated By Random Walkers
- Scale Free Networks from Self-Organisation
- Growing complex network of citations of scientific papers -- measurements and modeling
- Transitive Reduction of Citation Networks
- Spacelike distance from discrete causal order
- Modelling Citation Networks
- Embedding Graphs in Lorentzian Spacetime
- What is the dimension of citation space?
- Growing Scale-free Networks by a Mediation-Driven Attachment Rule
- Degree Distribution, Rank-size Distribution, and Leadership Persistence in Mediation-Driven Attachment Networks
- Making Communities Show Respect for Order