Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2020 Jun 29;10(1):10503.
doi: 10.1038/s41598-020-67421-8.

The longest path in the Price model

Tim S Evans  1 , Lucille Calmon  2 , Vaiva Vasiliauskaite  2
Affiliations

The longest path in the Price model

Tim S Evans et al. Sci Rep. .

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.

PubMed Disclaimer

Conflict of interest statement

The authors declare no competing interests.

Figures

Fig. 1
Fig. 1
An illustration of a Price-model style DAG where the longest, shortest and reverse greedy paths from last point to the first are distinct. The longest path from the source node to the sink node is highlighted in blue dot-dash line; the reverse greedy path is the dotted green path. Note the first edge is the same for both—the green-blue edge. As illustrated here, the Price model produces DAGs which are neither transitively complete nor transitively reduced. In a transitively complete DAG, all nodes which are connected by a path are connected by a direct edge. Likewise, except for the case of one-incoming edge per node, the model is not transitively reduced, that is some edges could be removed without removing a path between any pair of nodes.
Fig. 2
Fig. 2
An illustration of the Price Model. Here the height of the node on the page indicates the time with the first node at the bottom being the node t=1. At each stage we show the graph G(t) so after the new nodes and its incoming edges have been added.
Fig. 3
Fig. 3
On the left is a plot of path length against t for a single network realisation showing noisy the data is. Averaging over 100 runs greatly reduces the fluctuations as shown in the righthand plot. Fitted lines are of the form aln(t)+b. In both figures, a random sample of 105 points is plotted. The abscissa axes are logarithmic to show the linear behaviour between the path lengths and t.
Fig. 4
Fig. 4
The ratio of the average over 100 runs of the path length measured numerically, Lobs and ℓobs, divided by the expected values, as described by the numerical best fit. The data for p=0.375m=5 from t=1,000 (represented by a vertical dashed line) to t=108 was fitted to Eq. (6). The reverse greedy path results are shown on the left, and the longest path are shown on the right. The error bar on each point is calculated from the standard error in the mean from the results for each node over 100 runs. A random sample of 103 points is plotted in both figures.
Fig. 5
Fig. 5
The ratio of aobs/(mp¯) where aobs is the coefficient of ln(t) derived from the best fit of the numerical path length data to aln(t)+b Eq. (6) while mp¯ is the analytical prediction for the value of a when looking at the length of the reverse greedy path. The red triangles show the results for the reverse greedy path value of a while yellow circles are the longest path values. These values were obtained by fitting the form to nodes created between t=1,000 and t=108 from 100 realisations. Errors on the fitted values of a were smaller than the marker size and are not shown.
Fig. 6
Fig. 6
The ratio of amax/agr where a is the coefficient of ln(t) in the best fit of the numerical path length data to Eq. (6), amax for the longest path data and agr for the reverse greedy path data. These values were obtained by fitting the form to nodes created between t=1,000 and t=108 from 100 realisations. As a result the errors on the fitted values of a, as estimated from the covariance matrix of the linear fitting algorithm, were smaller than the marker size and so these are not shown.
See this image and copyright information in PMC

References

    1. Price DS. The scientific foundations of science policy. Nature. 1965;206:233–238. doi: 10.1038/206233a0. - DOI
    1. Price DS. A general theory of bibliometric and other cumulative advantage processes. J. Am. Soc. Inf. Sci. 1976;27:292–306. doi: 10.1002/asi.4630270505. - DOI
    1. Clough JR, Gollings J, Loach TV, Evans TS. Transitive reduction of citation networks. J. Complex Netw. 2015;3:189–203. doi: 10.1093/comnet/cnu039. - DOI
    1. Newman M. Networks: An Introduction. Oxford: Oxford University Press; 2009.
    1. Simkin, M. V. & Roychowdhury, V. P. Stochastic modeling of citation slips. Scientometrics62, 367–384 (2005). arXiv:cond-mat/0401529.