Source-linked AI summary
Resource competition and survival for random walkers on complex networks
Snehal Shekatkar
TL;DR
The paper studies how network movement and resource production shape the survival of resource-competing random walkers. It combines simulations with an independent-lifespan approximation and finds that topology and resource distribution affect survival, while degree-biased movement can extend survival on scale-free networks.
Problem
The paper asks how walker survival time depends on network topology, resource production, and movement when each walker needs a minimum resource share at every step.
Source: §I · p. 1Method
The authors simulate resource-consuming random walks and derive a survival-time distribution under an independent-lifespan assumption.
Source: §I · p. 1, A. Independent walker lifespans… · p. 2, §II · p. 2Results
Erdős–Rényi networks and uniform resource production yield longer mean survival than scale-free networks and exponential production, while scale-free networks show strong lifespan dependence.
Source: A. Variation with threshold for… · pp. 2–3Takeaways & Limitations
Biasing walkers toward low-degree neighbors substantially increases survival time on scale-free networks, bringing it close to the corresponding Erdős–Rényi value.
Source: B. Improving the survival time by… · p. 3The independent-lifespan approximation is most plausible when W(0) ≪ N and walkers are uniformly distributed, making shared-vertex deaths negligible.
Source: A. Independent walker lifespans… · p. 2
Abstract
from arXiv · showhide
We consider the problem of $W$ random walkers on a complex network where each walker requires an amount $\theta$ of resource at each time to survive. Resource is stochastically produced at each vertex of the network with a specified distribution. The survival time of the system of walkers is defined as the time required for all $W$ walkers to die. Using numerical simulations, we show that Erd{\H o}s-R\'enyi networks a have higher mean survival time than Scale-free networks as expected, but also that uniform distribution production leads to higher mean survival time than exponential distribution with the same mean. We derive an exact expression for the survival-time distribution under the assumption of independent walker lifespans, and use it to show that scale-free network topology produces strong dependence in the lifespans but homogeneous topology does not. We moreover demonstrate how the survival time can be substantially increased without changing the resource production or network topology by appropriately biasing the movement of the walkers towards low degree vertices on Scale-free networks, but has no effect on Erd{\H o}s-R{\'e}nyi networks.
I. THE MODEL
The model tracks walkers moving on a network while consuming perishable, stochastically produced vertex resources. It studies how survival time depends on walker count, topology, resource distribution, threshold, and movement bias.
I. THE MODEL
- Walkers move to neighboring vertices with probabilities proportional to each neighbor’s degree raised to the bias parameter η.The movement rule uses the destination vertex degree k_v.Source: §I · p. 1
- At each time step, vertices independently produce resource amounts from a shared distribution, and walkers at each vertex divide its current resource equally.Resource is perishable, so walkers cannot use amounts left over from earlier time steps.Source: §I · p. 1
- All walkers on a vertex die if their equal share of that vertex’s resource is below the survival threshold θ.Each walker needs θ at every time step.Source: §I · p. 1
- System survival time T_s is the time at which the last walker dies.The model initializes W(0) walkers uniformly at random across the network’s N vertices.Source: §I · p. 1
- The analysis asks how mean survival time varies with initial walker count, network topology, resource kernel, threshold, and movement bias.For a nonempty initial population, the minimum possible survival time is one time step.Source: §I · p. 1
A. Independent walker lifespans approximation
The section derives a survival-time distribution by approximating walker lifespans as independent, an approximation most plausible when few walkers are spread uniformly across many vertices. The resulting mean survival time is topology-independent and serves as an upper bound.
A. Independent walker lifespans approximation
- The independent-lifespan approximation is most plausible when W(0) is much smaller than N and walkers start uniformly at random.Under these conditions, multiple walkers dying on the same vertex are unlikely.Source: A. Independent walker lifespans… · p. 2
- A walker’s lifespan distribution assigns probability F(θ) to dying at time t after surviving the previous t−1 steps.F is the cumulative distribution function of the resource kernel p(x).Source: A. Independent walker lifespans… · p. 2
- The system survival-time CDF is the probability that the maximum of all individual lifespans is at most t, computed using independence.This yields the exact distribution under the independent-lifespan assumption.Source: A. Independent walker lifespans… · p. 2
- The resulting mean survival time is topology-independent and provides an upper bound because walkers can meet and die together on one vertex.Source: A. Independent walker lifespans… · p. 2
II. RESULTS
The experiments compare scale-free and Erdős–Rényi networks with matched mean degree, using two resource kernels and repeated network realizations.
II. RESULTS
- Both network topologies are generated with the configuration model and matched to the same average degree.The scale-free network uses a degree distribution parameterized by α and k_min.Source: §II · p. 2
- The scale-free degree distribution is specified using the Hurwitz zeta function.Source: §II · p. 2
- For the stated α = 2.2 and k_min = 2, the mean degree is approximately 9.36; the equivalent Erdős–Rényi network draws degrees from a Poisson distribution with that mean.The scale-free degrees are stub-matched to generate the configuration-model network.Source: §II · p. 2
- The simulations use uniform and exponential resource kernels with mean resource 1, 10,000 initial walkers, and 1,000 random network realizations.The kernels are X ∼ U(0, 2) and X ∼ Exponential(1).Source: §II · p. 2
A. Variation with threshold for unbiased walks
For unbiased walks, Erdős–Rényi networks and uniform resource production each yield longer system survival than their alternatives. Higher thresholds shorten survival, while topology and production differences diminish at high thresholds.
A. Variation with threshold for unbiased walks
- Erdős–Rényi networks outperform scale-free networks, and uniform production outperforms exponential production, when each pair has the same mean degree or resource mean.The paper attributes the network difference to the prevalence of high-degree vertices in scale-free networks, where survival chances are lower.Source: A. Variation with threshold for… · p. 2, Figure 1 · p. 3
- Increasing the walker threshold θ decreases mean system survival time across the tested network and production combinations.Higher resource requirements make walkers die faster.Source: A. Variation with threshold for… · p. 2, Figure 1 · p. 3
- At high θ, the four network-topology and resource-production combinations converge to the same mean survival time.Source: A. Variation with threshold for… · p. 3
- Scale-free topology produces strong dependence among walker movements, whereas Erdős–Rényi topology is nearly consistent with independent walkers.The comparison uses the survival-time distribution and an independence-based curve.Source: A. Variation with threshold for… · p. 3, Figure 3 · p. 3
- On scale-free networks, walkers starting at high-degree vertices tend to live longer, while walkers dying at high-degree vertices tend not to have survived long.The high-degree observations are noisy because such vertices are relatively rare.Source: A. Variation with threshold for… · p. 3, Figure 2 · p. 3
B. Improving the survival time by degree-biasing
Biasing movement toward low-degree neighbors substantially increases survival time on scale-free networks, without changing topology or resource production. The strategy has no effect on Erdős–Rényi networks.
B. Improving the survival time by degree-biasing
- Bias toward low-degree neighbors (η < 0) substantially increases mean survival time on scale-free networks, but movement bias has no effect on Erdős–Rényi networks.On scale-free networks, survival rises close to the corresponding Erdős–Rényi value.Source: B. Improving the survival time by… · p. 3, Figure 4 · p. 4
III. CONCLUSION
The conclusion introduces a simple random-walk model of the effect of overcrowding on individuals.
III. CONCLUSION
- The conclusion presents a simple random-walk model for studying the effect of overcrowding on individuals.Source: §III · p. 4