Exact calculations of first-passage properties on the pseudofractal scale-free web

Junhao Peng, Elena Agliari, Zhongzhi ZhangChaos 2015 · DOI · arXiv

Abstract

In this paper, we consider discrete time random walks on the pseudofractal scale-free web (PSFW) and we study analytically the related first passage properties. First, we classify the nodes of the PSFW into different levels and propose a method to derive the generation function of the first passage probability from an arbitrary starting node to the absorbing domain, which is located at one or more nodes of low-level (i.e., nodes with large degree). Then, we calculate exactly the first passage probability, the survival probability, the mean, and the variance of first passage time by using the generating functions as a tool. Finally, for some illustrative examples corresponding to given choices of starting node and absorbing domain, we derive exact and explicit results for such first passage properties. The method we propose can as well address the cases where the absorbing domain is located at one or more nodes of high-level on the PSFW, and it can also be used to calculate the first passage properties on other networks with self-similar structure, such as (u, v) flowers and recursive scale-free trees.

Introduction

In the study of random walks, the "First-Passage Time" (FPT) is a critical metric. It represents the moment a walker first hits a target, which models everything from a chemical reaction starting to a neuron firing or a stock option being triggered. While many scientists calculate the Mean First-Passage Time (MFPT)—the average time it takes—an average is often a poor descriptor of a complex system. If the variance is high, the "average" might never actually happen.

The challenge is that calculating the full First-Passage Probability (FPP)—the exact probability of hitting a target at time $n$—is mathematically grueling for complex networks. This paper tackles this for the Pseudofractal Scale-Free Web (PSFW), a network model that mimics real-world biological and technological systems with its "small-world" properties and "scale-free" (uneven) degree distribution.

The Pseudofractal Scale-Free Web

The authors leverage the self-similarity of the PSFW. Because the network is grown recursively, it looks the same at different scales. Starting with a simple triangle at $t=0$, every edge is replaced with a new triangle at each subsequent step, creating a complex, hierarchical structure.

The recursive growth process of the PSFW from generation t=0 to t=2.

Analytical Framework: Node Leveling and Generating Functions

To solve the FPP, the researchers developed a rigorous analytical method based on the following steps:

  1. Node Leveling: They classify nodes into "levels" based on their age and connectivity. Level-0 nodes are the original "hubs" with the highest degrees, while higher-level nodes are newer and less connected.
  2. Generating Functions: Instead of calculating probabilities directly, they use Probability Generating Functions (PGFs). Think of a PGF as a mathematical "suitcase" that packs an entire infinite sequence of probabilities into a single function.
  3. Recursive Derivation: By establishing how a walker moves between different levels of the network, they created recursive equations. They solved these to find the exact PGF for a walker starting at any node and ending at a specific "absorbing" (target) domain.
The recursive construction steps showing how new nodes are added based on the previous generation's structure.

Once they had the PGF, they used calculus (derivatives) to "unpack" the suitcase, revealing the exact FPP, the survival probability (the chance the walker hasn't hit the target yet), the mean, and the variance.

Key Insights and Results

  • Beyond the Average: The paper proves that the MFPT alone is insufficient. They found that the standard deviation of the first-passage time scales linearly with the mean. This means the "spread" of possible arrival times is just as large as the average arrival time itself, making the process highly stochastic.
  • Sublinear Scaling: The MFPT scales sublinearly with the "volume" (total number of nodes) of the network. Specifically, it scales as $V_t^{1/(\gamma-1)}$, where $\gamma$ is the power-law exponent of the degree distribution. This confirms that hubs in these networks are incredibly efficient at "trapping" random walkers.
  • Universal Tool: The "leveling" method provides a blueprint for solving first-passage problems on any network that grows recursively. If you can define the relationship between a parent structure and its "children," you can find the exact probability distribution.

Conclusion

The authors derived explicit, closed-form expressions for the probability of reaching a hub at any discrete time step $n$. They showed that the probability of a walker "surviving" (not hitting the target) decays exponentially over time, but the rate depends heavily on the starting node's level. For the first time on this specific web, they provided the exact variance of the FPT, showing it scales quadratically with the mean—a hallmark of transport in finite-degree self-similar graphs.

While the explicit examples focus on cases where the target is a high-degree hub, the method is generalizable. Future work could involve applying this PGF-based recursive method to non-fractal or more disordered scale-free networks to see if these scaling laws hold true in less "perfect" geometries.

Summary updated

Abstract

In this paper, we consider discrete time random walks on the pseudofractal scale-free web (PSFW) and we study analytically the related first passage properties. First, we classify the nodes of the PSFW into different levels and propose a method to derive the generation function of the first passage probability from an arbitrary starting node to the absorbing domain, which is located at one or more nodes of low-level (i.e., nodes with large degree). Then, we calculate exactly the first passage probability, the survival probability, the mean, and the variance of first passage time by using the generating functions as a tool. Finally, for some illustrative examples corresponding to given choices of starting node and absorbing domain, we derive exact and explicit results for such first passage properties. The method we propose can as well address the cases where the absorbing domain is located at one or more nodes of high-level on the PSFW, and it can also be used to calculate the first passage properties on other networks with self-similar structure, such as (u, v) flowers and recursive scale-free trees.
BibTeX
@inproceedings{peng2015exact,
  author = {Junhao Peng and Elena Agliari and Zhongzhi Zhang},
  title = {{Exact calculations of first-passage properties on the pseudofractal scale-free web}},
  booktitle = {Chaos},
  year = {2015},
  doi = {10.1063/1.4927085},
}
Figure