The longest path in the Price model.

Area of Science:

• Network Science
• Complex Systems
• Graph Theory

Background:

• The Price model, a directed version of the Barabási-Albert model, generates growing directed acyclic graphs (DAGs).
• In these networks, the longest path is a relevant metric, sometimes approximating geodesics better than shortest paths.

Purpose of the Study:

• To investigate variants of the Price model with different edge attachment mechanisms: preferential attachment and random attachment.
• To analyze the scaling behavior of the longest path in these growing directed networks.

Main Methods:

• Studied two attachment strategies for new vertices: cumulative advantage (preferential attachment) and random attachment.
• Defined and analyzed a 'reverse greedy path' both analytically and numerically.
• Performed numerical simulations to determine the scaling of the longest path.

Main Results:

• The reverse greedy path length scales logarithmically with network size, with a coefficient determined by random attachment edges.
• This reverse greedy path provides a lower bound for the longest path to any vertex.
• The longest path also scales logarithmically with network size, exhibiting a larger coefficient influenced by model parameters.

Conclusions:

• The longest path in Price model variants grows logarithmically with network size.
• The attachment strategy (preferential vs. random) influences the coefficient of this logarithmic scaling.
• The findings provide a deeper understanding of path length properties in growing directed networks.