Popularity-driven random walks on a class of scale-free graphs

Area of Science:

• Graph theory
• Network science
• Statistical physics

Background:

• Random walks are fundamental to analyzing graph structures.
• Understanding graph exploration dynamics is crucial in network analysis.
• Previous models often assume uniform or degree-based transition probabilities.

Purpose of the Study:

• Introduce a generalized random walk model with tunable bias.
• Analyze the stationary distribution and exploration efficiency of these walks.
• Investigate behavior on Barabasi-Albert random graphs.

Main Methods:

• Derivation of the stationary distribution for the proposed random walk.
• Analysis of expected behavior on Barabasi-Albert random graphs.
• Mathematical modeling of biased transitions proportional to neighbor degree power (α).

Main Results:

• The stationary distribution was derived for the generalized random walks.
• Fastest graph exploration is achieved with negative α (bias towards low-degree neighbors).
• This negative bias counteracts the inherent degree distribution bias, promoting uniform vertex visitation probability.

Conclusions:

• A novel class of biased random walks offers tunable graph exploration.
• Negative α parameter significantly enhances exploration efficiency in scale-free networks.
• The findings provide insights into optimizing traversal strategies in complex networks.