Longest path in the price model
File(s)s41598-020-67421-8.pdf (1.71 MB)
Published version
Author(s)
Evans, Tim S
Calmon, Lucille
Vasiliauskaite, Vaiva
Type
Journal Article
Abstract
The Price model, the directed version of the Barab\'{a}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.
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.
Date Issued
2020-06-29
Date Acceptance
2020-03-02
Citation
Scientific Reports, 2020, 10, pp.1-9
ISSN
2045-2322
Publisher
Nature Publishing Group
Start Page
1
End Page
9
Journal / Book Title
Scientific Reports
Volume
10
Copyright Statement
© 2020 The Author(s). This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/.
Identifier
http://arxiv.org/abs/1903.03667v2
Subjects
physics.soc-ph
physics.soc-ph
Notes
Post-peer-review, pre-copyedit version of article to be published in Scientific Reports
Publication Status
Published
Article Number
ARTN 10503
Date Publish Online
2020-06-29