CS Paper Radar

Resource competition and survival for random walkers on complex networks

Snehal Shekatkar

cs.SI physics.comp-phstat.AP ·submitted 2026-10-24 18:06 UTC · v1

Abstract

We consider the problem of $W$ random walkers on a complex network where each walker requires an amount $θ$ 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ényi 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{é}nyi networks.

Comment
4 pages, 4 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Size-Independent Survival Bounds for Routing Without a Map

cs.DS ·2026-11-17 ·Krišjānis Petručeņa
theory similarity 0.58
Abstract · 38 pages, 11 figures. Follow-up to arXiv:2609.00893

A walker, such as a packet carrying a secret share, must reach a known target in an unknown graph while avoiding a fixed set of fatal vertices (compromised relays in the packet interpretation). It learns a vertex's neighbours only on reaching that vertex safely, remembers its observations, and is promised a safe route. We prove that a randomised depth-first strategy guarantees a success probability depending only on the maximum degree and the number of fatal vertices, not on the size of the graph. Planarity is not required for this guarantee, and planar examples attain the bound at every sufficiently large graph size. At those sizes, when the degree cap is at least three, the guarantee is optimal among strict depth-first strategies. Whether strategies allowed to switch between unfinished branches can guarantee a larger worst-case survival probability remains open. For unknown trees and for graphs of maximum degree two, we determine the exact best worst-case success probability over all routing strategies. Explicit examples compare our strategy with random-priority frontier routing and ordinary random walks, showing how exploration order can prevent survival probability from declining as the graph grows.

0.15

Conditional-path Monte Carlo for rare stochastic dynamics on networks: Details and derivations

cs.SI cond-mat.stat-mechphysics.comp-phphysics.soc-ph ·2026-08-18 ·Thomas Barthel, Jiazheng Sun, Jhao-Hong Peng
similarity 0.58
Abstract · 16+2 pages, 5 figures

The simulation of rare macroscopic events in stochastic network dynamics, such as widespread epidemic outbreaks, cascading failures in communication networks, or the escape from metastable states in many-body systems, is severely hindered by methodological challenges like catastrophic rejection rates, weight degeneracy, genealogical correlations, and critical slowing down inherent to standard forward-time algorithms, splitting methods, and transition-path sampling. Conditional-path Monte Carlo (CPMC) overcomes these limitations by employing non-local Swendsen-Wang-like cluster updates that operate directly on full-system trajectories. Serving as the technical companion to [Sun, Moody, and Barthel, arXiv:2608.16171], this paper provides the rigorous mathematical foundations and algorithmic details underlying the CPMC framework. We formally define the joint path-graph probability weights and derive the transition and uniformization sum rules that guarantee detailed balance. Applying the framework to susceptible-infectious-susceptible (SIS) models, we systematically construct and optimize single-node and edge graph vertex sets specifically designed to prevent lock avalanches and maintain the structural mobility of the epidemic trunk. Furthermore, we detail a dynamic programming scheme to exactly implement complex boundary conditions - including patient-zero and macroscopic outbreak-size constraints - enabling the rejection-free generation of valid trajectories. Finally, we assess the computational complexity of the algorithm, describe parallelization strategies, and validate CPMC against exact solutions for dynamics on small networks.

0.42

Structural Sign Herdability in Temporal Networks: A Sufficient Condition via $π_p$-Graphs

eess.SY ·2026-09-09 ·Pradeep M, Twinkle Tripathy
similarity 0.57
Abstract

In this letter, we study the herdability of temporally switching directed networks. A temporal network is modeled as a switched system with a fixed switching sequence, which imposes more restrictive herdability conditions than those of conventional switched systems. By exploiting the relationship between temporal walks and the entries of the controllability matrix, we derive sufficient conditions for herdability. We further show that the magnitude of edge weights influences the sign pattern of the controllability matrix, thereby affecting herdability. Consequently, herdability in temporal networks depends not only on the network topology and switching durations, but also on the magnitude of the edge weights. Motivated by this observation, we establish equivalent graph-theoretic conditions for structural sign ($\mathcal{SS}$) herdability in temporal networks. In particular, we introduce the union multigraph of temporal subsystems and propose the notion of a $π$-graph. We show that the existence of a $π_p$-graph, which is a temporally evolving $π$-graph, is sufficient to guarantee $\mathcal{SS}$ herdability. Illustrative examples are provided to demonstrate the proposed results.

0.36

Online Network Design with Maximum Delay and Stochastic Arrivals

cs.DS ·2026-11-10 ·Tianhang Lu
theory similarity 0.56
Abstract

We study online network services that combine pending requests into batches. Each batch pays for its spatial service and for the waiting time of its oldest request. The objective is the sum of these costs over all batches. Thus requests can share both a spatial purchase and one maximum-delay charge. We assume independent Poisson arrivals of known rates, while actual requests are revealed only upon arrival. For stateless services, suppose that each type has an attainable minimum cost when served alone, that every batch costs at least the stand-alone minimum of each type it contains, and that one finite-cost action can serve any batch, regardless of its request multiplicities. We give a deterministic algorithm with long-run ratio of expectations $e/(e-1)$ against an unrestricted offline optimum. This factor is optimal, even allowing randomization, already at one request location. The key comparison measures the union of time intervals associated with requests. The theorem applies directly to multi-root and pair aggregation on trees. We also study facility location, where each request pays its own connection distance and the bounded-action assumption can fail. A deterministic policy gives a ratio $3$ for arbitrary nonnegative opening costs. It immediately serves a finite initial set of requests, computes an assignment from their observed arrival gaps, and then keeps that assignment fixed. Its analysis combines Poisson insertion with a time-slice packing bound on the offline optimum. Every guarantee includes the full cost of completing finite inputs without an end-of-input signal.

0.15

Percolation in the Stochastic Block Model

cs.SI physics.soc-phcond-mat.stat-mechmath.PR ·2026-09-22 ·Luca Pieleanu, Moritz Laber, Narayan G. Sabhahit, Dmitri Krioukov
similarity 0.55
Abstract · 23 pages, 10 figures

The stochastic block model is a paradigmatic model of networks with community structure. Yet percolation in the model has been studied primarily in cases with a fixed block structure, even though in real networks, the community structure may evolve as the network grows. Here we study percolation in sequences of stochastic block models in which the numbers and sizes of communities, as well as the intra- and intercommunity connection probabilities may all change with the network size. We analyze five such sequences using two methods: linearized self-consistent equations for the locally tree-like models and a branching process at the community scale for the models with nonvanishing clustering. We find that the critical average degree is not generally equal to $1$, even in locally tree-like sequences, because the transition depends on how connections are distributed across the evolving community structure. We also show that the community-scale branching process accurately predicts the transition when intercommunity connections are sufficiently sparse, even in the presence of nonvanishing clustering, while a geometric stochastic block model sequence demonstrates the limitations of this method when correlations between intercommunity connections cannot be neglected. These results extend percolation studies in the stochastic block model to more realistic scenarios with evolving community structure, and may provide new methods to derive the upper and lower bounds for the percolation threshold in geometric long-range percolation.

0.19

Shortest-path percolation and structural robustness of quantum internet networks

cs.SI physics.soc-phcond-mat.stat-mechquant-ph ·2026-11-16 ·Victor H. F. Francheto, Thomas Peron
code/data similarity 0.55
Abstract · 20 pages, 18 figures. Code available at https://github.com/VictorFrancheto/shortest-path-percolation-implementation

We study shortest-path percolation on spatial networks that model the quantum internet based on optical fibers. In this process, the removal of paths describes the consumption of the entangled links used for communication. We compare finite and unrestricted path-length bounds for networks whose average degree either increases with system size or remains approximately constant. We show that networks become more robust as the average degree increases, whereas networks with approximately constant average degree exhibit a data collapse for the fixed finite bounds considered. Using Monte Carlo sampling of the shortest-path-length distribution, we estimate an equivalent path cost, a finite bound that approximately reproduces the degradation of the network in the unrestricted case. For networks with fixed average degree, this cost grows approximately as the square root of the number of nodes. Increasing the bound beyond this value requires additional computation time without appreciably changing the percolation dynamics. As a complementary result, for Erdős-Rényi random networks, we find an empirical relation between the initial average degree and the approximately common crossing point of the percolation curves for different path-length bounds.

0.39

Stochastic Network Speed Scaling with Competitive Ratios Independent of the Network

cs.DS cs.PF ·2026-10-02 ·Yash Khanna
theory similarity 0.54
Abstract · 14 pages, 2 figures, 1 table

In network speed scaling, jobs arrive over time at a network of servers whose speeds can be tuned, every job must be processed by the servers along one of its allowed routes, and the goal is to minimize the total flow time plus the total energy. For stochastic arrivals, the competitive ratio of Vaze and Nair depends on the network, through the lengths of the routes it uses. We show that this dependence can be removed: we give an algorithm, which routes the jobs by solving a convex program and runs every server at a fixed speed, whose competitive ratio depends only on the power functions; for $P(s)=s^2$, it is at most the golden ratio $\varphi\approx1.618$. The key idea is a lower bound on the optimal cost which, like the cost of our algorithm, is a sum over the servers of a function of each server's load, so the analysis reduces to a single server. We also show that the routing rule of Vaze and Nair can be a factor $Ω(L)$ away from optimal, where $L$ is the length of the longest route.

0.31

Capacity-Aware Redistribution Control for Mitigation of Cascading Failures in Networks

eess.SY math.OC ·2026-11-18 ·Ujjwal Pratap, Christian A. Hans
similarity 0.53
Abstract

This paper studies the control of irreversible cascading failures in networks with finite node capacities. Each node carries a nonnegative divisible quantity, referred to as load, and fails irreversibly when its load exceeds its capacity. The network dynamics are represented by topology-dependent row-stochastic matrices. When nodes fail, these matrices must be updated. However, directly deleting rows and columns corresponding to failed nodes can reduce the total load in the network. We therefore introduce a topology update that preserves unit row sums and quantifies any unserved load explicitly. We derive the resulting load-balance relation and a necessary and sufficient condition for lossless redistribution after simultaneous failures. Based on these results, we formulate a two-stage optimization problem: the first stage minimizes unserved load, and the second stage minimizes the highest capacity utilization among the surviving nodes. Simulations on grid and Barabasi-Albert networks show that, unlike the standard equal and residual-capacity redistribution approaches, the proposed method prevents secondary failures in all tested cases, with a tradeoff against served load on scale-free networks.

0.32