Kumar, Goswami and Santhanam showed numerically that the fraction sW(t)s_W(t) of nodes of a scale-free network not visited by WW independent random walkers within tt steps follows a stretched exponential, sW(t)=((N−1)/N)exp⁡(−A(Wt/N)β)s_W(t)=((N-1)/N)\exp(-A(Wt/N)^{\beta}), with β\beta depending on the network but not on the number of walkers, so that multi-walker coverage effectively reduces to single-walker coverage. No analytical derivation of this law exists: neither the origin of the scaling variable x=Wt/Nx=Wt/N, nor what fixes the stretching exponent β\beta, nor the finite-size and finite-walker corrections, nor why the scaling appears on scale-free but not on small-world or Erdős–Rényi graphs is understood. The problem is to develop such an analytical theory, or to refute the stretched-exponential form as the correct asymptotic law.

Background

A random walk on a network (graph) with NN nodes is a discrete-time Markov chain that at each step hops from its current node to a uniformly chosen neighbor. The number of distinct nodes SW(t)S_W(t) visited up to time tt by WW independent walkers, and the complement sW(t)=(N−SW(t))/Ns_W(t)=(N-S_W(t))/N (the fraction of nodes still unvisited), measure the territory explored by the walkers — a basic quantity for search, crawling, and spreading processes on networks. The cover time tcovt_{cov} is the time by which every node has been visited at least once. A scale-free network is one whose degree distribution (the fraction of nodes with kk neighbors) follows a power law P(k)∼k−γP(k)\sim k^{-\gamma}; standard generators are the Barabási–Albert (BA) preferential-attachment model, in which new nodes attach preferentially to existing high-degree nodes, and the configuration model, which builds a random network with a prescribed degree sequence.

For regular lattices the multi-walker problem is classical: Larralde, Trunfio, Havlin, Stanley and Weiss (Phys. Rev. A 45, 7128, 1992) identified three temporal regimes for ⟨SW(t)⟩\langle S_W(t)\rangle on dd-dimensional lattices, and Kundu, Majumdar and Schehr (Phys. Rev. Lett. 110, 220602, 2013) obtained exact distributions of distinct and common sites for WW walkers on a one-dimensional lattice via extreme-value statistics. For networks much less is known. For a single walker on finite scale-free networks, Lee, Yook and Kim (Physica A 387, 3033, 2008) showed numerically that S1(t)≈tS_1(t)\approx t at short times before finite-size saturation, and De Bacco, Majumdar and Sollich (J. Phys. A 48, 205004, 2015) developed a generating function formalism for ⟨S1(t)⟩\langle S_1(t)\rangle on random graphs. On the rigorous side, Cooper and Frieze (J. Comb. Theory B 97, 269, 2007) proved that the single-walker cover time of the preferential-attachment graph is Θ(Nlog⁡N)\Theta(N\log N), and Alon, Avin, Koucký, Kozma, Lotker and Tuttle (arXiv:0705.0467, 2007) initiated the study of the cover time of kk parallel walks starting from the same vertex, proving linear-in-kk speedup for many graphs while showing that the speedup can be as small as logarithmic. Maier and Brockmann (Phys. Rev. E 96, 042307, 2017) gave a method to compute single-walker mean cover times on arbitrary complex networks.

Against this background, Kumar, Goswami and Santhanam (Physica A 532, 121875, 2019; arXiv:1501.01246) simulated WW independent walkers, all starting from one randomly chosen node, on BA networks, configuration-model networks, and four real-world scale-free networks (Enron email, yeast protein-interaction, Internet autonomous systems, cond-mat collaboration). They found a striking empirical data collapse: with the scaled variable x=Wt/Nx=Wt/N, the fraction of unvisited nodes follows a stretched exponential (a decay of the form exp⁡(−Axβ)\exp(-Ax^{\beta}) with stretching exponent 0<β<10<\beta<1, familiar from relaxation in disordered systems),

sW(t)=(N−1N)e−A x(t)β,x(t)=WtN,s_{W}(t)=\left(\frac{N-1}{N}\right)e^{-A\,x(t)^{\beta}},\qquad x(t)=\frac{Wt}{N},

with AA and β\beta fitted by regression (β\beta ranging from about 0.58 to 0.88 across the six networks studied). This implies the scaling relation log⁡sW2(t)=(W2/W1)βlog⁡sW1(t)\log s_{W_2}(t)=(W_2/W_1)^{\beta}\log s_{W_1}(t), so the multi-walker problem reduces to the single-walker one on the same network. The law holds in an intermediate window τr<t≪tcov\tau_r<t\ll t_{cov}, where τr\tau_r is the early-time relaxation scale of order N/WN/W below which the walkers have not yet decorrelated from their common starting node; deviations appear at short times (finite WW) and near the cover time (finite NN). Notably, the authors did not observe the scaling on two other standard network classes: small-world networks (the Watts–Strogatz model, a ring lattice in which a small fraction of edges are rewired at random, giving high clustering with short paths) and Erdős–Rényi random graphs (the classical random graph in which each possible edge is present independently with a fixed probability). The paper states explicitly that analytical justifications for the scaling relation would be an interesting and promising direction, and that no exact closed-form result for ⟨SW(t)⟩\langle S_W(t)\rangle on arbitrary networks is known.

Problem Statement

For independent random walkers on scale-free networks (P(k)∼k−γP(k)\sim k^{-\gamma}, e.g. the Barabási–Albert preferential-attachment ensemble and configuration-model ensembles with a prescribed power-law degree sequence, and real-world networks with approximately power-law degrees), develop an analytical theory of the coverage curve — the fraction of nodes sW(t)s_W(t) not visited by WW walkers within tt steps — that explains the empirically observed law sW(t)=((N−1)/N)exp⁡(−A(Wt/N)β)s_W(t)=((N-1)/N)\exp(-A(Wt/N)^{\beta}) found by Kumar, Goswami and Santhanam. Concretely: (i) derive the stretched-exponential form and the emergence of the scaling variable x=Wt/Nx=Wt/N from the network's heavy-tailed structure; (ii) identify which structural statistics fix the stretching exponent β\beta and the amplitude AA, and determine whether and how β\beta depends systematically on the degree exponent γ\gamma (empirically β\beta varies across networks, from about 0.58 to 0.88, but not systematically with γ\gamma); (iii) characterize analytically the finite-WW and finite-NN corrections and the boundaries of the validity window τr<t≪tcov\tau_r<t\ll t_{cov} (τr\tau_r the early-time relaxation scale, of order N/WN/W), including the short-time and cover-time-saturation regimes; and (iv) explain why the scaling arises for scale-free topologies but is not observed for small-world (Watts–Strogatz-type) and Erdős–Rényi (uniform random) networks. An answer may alternatively refute the stretched-exponential form — showing it is a crossover artifact and deriving the correct asymptotic coverage law — provided the analysis addresses the same intermediate regime and network classes as the source. A full resolution requires all four parts (i)–(iv) together, and progress on a proper subset of them is partial rather than resolving; by contrast, a refutation of the stretched-exponential form, meeting the conditions just stated, resolves the task on its own. The common objective of all parts is to elevate the reported empirical scaling into predictive theory for multi-agent exploration of heavy-tailed networks.

References

  1. Aanjaneya Kumar, Yagyik Goswami, M. S. Santhanam, "Distinct nodes visited by random walkers on scale-free networks", Physica A: Statistical Mechanics and its Applications 532, 121875 (2019). DOI: 10.1016/j.physa.2019.121875; arXiv:1501.01246. https://doi.org/10.1016/j.physa.2019.121875
  2. Hernan Larralde, Paul Trunfio, Shlomo Havlin, H. Eugene Stanley, George H. Weiss, "Number of distinct sites visited by N random walkers", Physical Review A 45, 7128–7138 (1992). DOI: 10.1103/PhysRevA.45.7128. https://doi.org/10.1103/PhysRevA.45.7128
  3. Anupam Kundu, Satya N. Majumdar, Grégory Schehr, "Exact Distributions of the Number of Distinct and Common Sites Visited by N Independent Random Walkers", Physical Review Letters 110, 220602 (2013). DOI: 10.1103/PhysRevLett.110.220602. https://doi.org/10.1103/PhysRevLett.110.220602
  4. Sungmin Lee, Soon-Hyung Yook, Yup Kim, "Random walks and diameter of finite scale-free networks", Physica A: Statistical Mechanics and its Applications 387, 3033–3038 (2008). DOI: 10.1016/j.physa.2008.01.101. https://doi.org/10.1016/j.physa.2008.01.101
  5. Caterina De Bacco, Satya N. Majumdar, Peter Sollich, "The average number of distinct sites visited by a random walker on random graphs", Journal of Physics A: Mathematical and Theoretical 48, 205004 (2015). DOI: 10.1088/1751-8113/48/20/205004. https://doi.org/10.1088/1751-8113/48/20/205004
  6. Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, Mark R. Tuttle, "Many random walks are faster than one", arXiv:0705.0467 (2007). https://arxiv.org/abs/0705.0467
  7. Colin Cooper, Alan Frieze, "The cover time of the preferential attachment graph", Journal of Combinatorial Theory, Series B 97, 269–290 (2007). DOI: 10.1016/j.jctb.2006.05.007. https://doi.org/10.1016/j.jctb.2006.05.007
  8. Benjamin F. Maier, Dirk Brockmann, "Cover time for random walks on arbitrary complex networks", Physical Review E 96, 042307 (2017). DOI: 10.1103/PhysRevE.96.042307. https://doi.org/10.1103/PhysRevE.96.042307
  9. Ido Tishby, Ofer Biham, Eytan Katzav, "Analytical results for the distribution of cover times of random walks on random regular graphs", Journal of Physics A: Mathematical and Theoretical 55, 015003 (2022). DOI: 10.1088/1751-8121/ac3a34. https://doi.org/10.1088/1751-8121/ac3a34
  10. Nicolás Rivera, Thomas Sauerwald, John Sylvester, "Multiple random walks on graphs: mixing few to cover many", Combinatorics, Probability and Computing, 1–44 (2023). DOI: 10.1017/S0963548322000372; arXiv:2011.07893. https://doi.org/10.1017/S0963548322000372
  11. Léo Régnier, Maxim Dolgushev, S. Redner, Olivier Bénichou, "Universal exploration dynamics of random walks", Nature Communications 14, 618 (2023). DOI: 10.1038/s41467-023-36233-5. https://doi.org/10.1038/s41467-023-36233-5
  12. Sarvesh K. Upadhyay, Trifce Sandev, Sanjay Kumar, R. K. Singh, "Network exploration by random walks: A large deviation perspective", Chaos, Solitons & Fractals 211, 118810 (2026). DOI: 10.1016/j.chaos.2026.118810; arXiv:2604.20829. https://doi.org/10.1016/j.chaos.2026.118810