Exact encounter times for many random walkers on regular and complex networks

The exact mean time between encounters of a given particle in a system consisting of many particles undergoing random walks in discrete time is calculated, on both regular and complex networks. Analytical results are obtained both for independent walkers, where any number of walkers can occupy the same site, and for walkers with an exclusion interaction, when no site can contain more than one walker. These analytical results are then compared with numerical simulations, showing very good agreement.

Figure 1

(Color online) Mean encounter time $N⟨\tau ⟩$ on a linear chain of length $V=100$, as a function of the number of particles $N$, with and without exclusion. Numerical results, evaluated as a mean over ${10}^8$ steps, are compared to the analytical results; lines are shown as a guide for the eye. Error bars are of the order of the symbol size. There is excellent agreement in both cases. Dashed lines show the asymptotic behavior.

Figure 2

(Color online) Mean occupation number $⟨n_i⟩$ for each site $i$, as a function of the degree $k_i$ of the site, for dynamics with and without exclusion, on a single random network with power-law degree distribution $P\left(k\right)\sim k^{-\alpha }$ with $\alpha =2.5$. The network has $V=1000$ nodes and mean degree $⟨k⟩=5.036$. The numerical data for each site is shown as a symbol, and the curves show the analytical results; the lowest curve is the zeroth-order approximation $p_i\left(0\right)$ in the exclusion case. The complete curve in the case of independent dynamics continues to grow linearly for larger $k_i$ (not shown).

Figure 3

(Color online) (a) Mean encounter time $⟨\tau ⟩$ of a distinguished walker on networks with power-law degree distribution $P\left(k\right)\sim k^{-\alpha }$, for different values of $\alpha$ with $V=1000$ sites and for a chain with $V=100$, as a function of the density, $\rho$. Only data for exclusion dynamics are shown; data for independent walkers are very close to these. To highlight the differences between the curves, (b) shows $1/⟨\tau ⟩$ for different $\alpha$ compared to the analytical results, drawn with black dotted lines. The lowest dashed line shows the mean-field result for comparison.

Figure 4

(Color online) Mean encounter time $⟨\tau ⟩$ as a function of the power-law exponent $\alpha$, for different densities $\rho$, on networks of size $V=1000$. The black dotted lines show the analytical results for comparison.