TY - JOUR
AB - 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 inwhich directed edges are added to the new vertex in one of two ways: usingcumulative advantage (preferential attachment) choosing vertices in proportionto their degree, or with random attachment in which vertices are chosenuniformly at random. In such networks, the longest path is well defined and insome cases is known to be a better approximation to geodesics than the shortestpath. We define a reverse greedy path and show both analytically andnumerically that this scales with the logarithm of the size of the network witha coefficient given by the number of edges added using random attachment. Thisis a lower bound on the length of the longest path to any given vertex and weshow numerically that the longest path also scales with the logarithm of thesize of the network but with a larger coefficient that has some weak dependenceon the parameters of the model.
AU - Evans,TS
AU - Calmon,L
AU - Vasiliauskaite,V
DO - 10.1038/s41598-020-67421-8
EP - 9
PY - 2020///
SN - 2045-2322
SP - 1
TI - Longest path in the price model
T2 - Scientific Reports
UR - http://dx.doi.org/10.1038/s41598-020-67421-8
UR - http://arxiv.org/abs/1903.03667v2
UR - https://www.nature.com/articles/s41598-020-67421-8
UR - http://hdl.handle.net/10044/1/81284
VL - 10
ER -