Random walks on weighted networks

Zhongzhi Zhang, Tong Shan, Guanrong ChenPhysical 2013 · DOI · arXiv

Abstract

Random walks constitute a fundamental mechanism for a large set of dynamics taking place on networks. In this article, we study random walks on weighted networks with an arbitrary degree distribution, where the weight of an edge between two nodes has a tunable parameter. By using spectral graph theory, we derive analytical expressions for the stationary distribution, mean first-passage time (MFPT), average trapping time (ATT), and lower bound of the ATT. All these results depend on the weight parameter, indicating a significant role of network weights on random walks. For uncorrelated scale-free networks, when the target is placed on a node with the highest degree, we show that ATT can display various scalings of network size, depending on the weight parameter. Our findings could pave a way to delicately controlling random-walk dynamics on complex networks.

Introduction

Random walks serve as the mathematical foundation for modeling diverse phenomena, including search engine algorithms, epidemic spreading, and diffusion in physical systems. While random walks on binary networks—where edges are either present or absent—are well-documented, real-world networks such as airport connections or metabolic pathways are inherently weighted. These weights are rarely random; they often correlate with the importance or "degree" of the nodes they connect.

This research addresses the lack of a general analytical theory for how these correlated weights influence key transport metrics. Specifically, it focuses on the Mean First-Passage Time (MFPT)—the expected time to travel between two nodes—and the Average Trapping Time (ATT)—the time required to reach a specific "trap" node from a random starting point.

Methodology

The authors employ spectral graph theory and the formalism of generating functions to derive their results. The core of their approach lies in a specific weight model where the weight $w_{ij}$ between nodes $i$ and $j$ follows a power-law relationship: $w_{ij} = (d_i d_j)^\theta$. Here, $d$ represents the node degree and $\theta$ is a controllable parameter that adjusts the influence of node importance on edge weight.

By defining a biased transition matrix based on node "strengths" (the sum of weights of edges connected to a node), the researchers analyzed eigenvalues and eigenvectors to derive closed-form expressions for the stationary distribution and MFPT. To validate these theoretical derivations, numerical simulations were performed on Barabási-Albert (BA) scale-free networks, which are standard models for social and technological systems.

Key Insights: The Role of $\theta$

The parameter $\theta$ acts as a mathematical steering mechanism for the random walker. When $\theta > 0$, the walker is effectively "attracted" to high-degree hubs. Conversely, when $\theta < 0$, the walker is biased toward the periphery or low-degree nodes. This shift fundamentally alters the stationary distribution; unlike unbiased walks where the probability of being at a node is proportional to its degree, in this model, it is proportional to the node's strength $s_i$, which is heavily influenced by $\theta$.

Trapping Efficiency and Scaling Laws

A critical finding of the study is that for scale-free networks, the time it takes to find a "trap" at a major hub scales differently with the network size $N$ depending on the value of $\theta$. The authors identified three distinct regimes for the ATT to a hub:

  1. $\theta > \gamma - 2$: The ATT is constant and independent of network size.
  2. $\theta = \gamma - 2$: The ATT grows logarithmically ($\ln N$).
  3. $\theta < \gamma - 2$: The ATT grows as a power of $N$.
Average trapping time (ATT) as a function of network size N for different values of the weight parameter θ.

As shown in the figure above, numerical simulations on BA networks perfectly match these theoretical scaling predictions. Increasing $\theta$ significantly accelerates the trapping process, demonstrating that transport efficiency can be tuned by adjusting the weight-degree correlation.

Conclusion

This work provides a comprehensive framework for understanding how edge weights dictate navigation in complex networks. By deriving a universal lower bound for the ATT, the authors show that trapping efficiency is fundamentally limited by the strength of the target node relative to the total network strength. While the study is currently limited to undirected graphs and a specific functional form for weights, it opens the door to more sophisticated control of random-walk dynamics in evolving or directed real-world systems.

Summary updated

Abstract

Random walks constitute a fundamental mechanism for a large set of dynamics taking place on networks. In this article, we study random walks on weighted networks with an arbitrary degree distribution, where the weight of an edge between two nodes has a tunable parameter. By using the spectral graph theory, we derive analytical expressions for the stationary distribution, mean first-passage time (MFPT), average trapping time (ATT), and lower bound of the ATT, which is defined as the average MFPT to a given node over every starting point chosen from the stationary distribution. All these results depend on the weight parameter, indicating a significant role of network weights on random walks. For the case of uncorrelated networks, we provide explicit formulas for the stationary distribution as well as ATT. Particularly, for uncorrelated scale-free networks, when the target is placed on a node with the highest degree, we show that ATT can display various scalings of network size, depending also on the same parameter. Our findings could pave a way to delicately controlling random-walk dynamics on complex networks.
BibTeX
@inproceedings{zhang2013random,
  author = {Zhongzhi Zhang and Tong Shan and Guanrong Chen},
  title = {{Random walks on weighted networks}},
  booktitle = {Physical},
  year = {2013},
  doi = {10.1103/physreve.87.012112},
}
Figure