Random walker's view of networks whose growth it shapes

We study a simple model in which the growth of a network is determined by the location of one or more random walkers. Depending on walker motility rate, the model generates a spectrum of structures situated between well-known limiting cases. We demonstrate that the average degree observed by a walker is a function of its motility rate. Modulating the extent to which the location of node attachment is determined by the walker as opposed to random selection is akin to scaling the speed of the walker and generates new limiting behavior. The model raises questions about energetic and computational resource requirements in a physical instantiation.

Figure 1

Networks created by WING. The motility rate, $r_W$, of the only walker differs across panels, while the network growth rate is constant $r_N=1$. For the sake of less congestion, simulations are stopped after $t=50$ time units. The seed network is a fully connected set of $N_0=5$ nodes, still recognizable as the only clique. (a) $r_W=0$; (b) $r_W=0.1$; (c) $r_W=1$; (d) $r_W=100$.

Figure 2

Degree distributions generated by WING. The panels are for different $r_W$ values. For all panels $r_N=1$, $m=1$, and averages are taken over 1000 replicates. (a) $r_W=0.01$; (b) $r_W=1$; (c) $r_W=10$; (d) $r_W=100$. In panels (a)–(c), simulations were run to $t_1=100000$ (blue circles) and to $t_2=200000$ (red diamonds), indicating stationarity. In panel (d), representing the large-$r$ case, we compare the WING model (blue circles) with the BA procedure ($r_W\sim \infty$, green diamonds) at $t=100000$. The red line is $p_{BA}\left(k\right)=4/\left[k(k+1)(k+2)\right]$ as per Refs. [8, 15].

Figure 3

Distance between nodes as a function of age. The average distance between a node of age 4000 and all other nodes in a network generated with WING is shown as a function of their age difference for different values of walker motility. $r_W=10$ (blue disks), $r_W=5$ (green dashed), $r_W=2$ (blue dot-dashed), $r_W=1$ (blue solid), $r_W=0.5$ (red dashed), and $r_W=0.1$ (red squares). $N=10000$.

Figure 4

The local degree distribution. $p\left(k\right)$ (blue disks) is compared with $p_W\left(k\right)$ (red diamonds) after $N=10000$ growth events. Convergence of $p_W\left(k\right)$ to a stationary distribution is fast. $r_W=1$, $r_N=1$.

Figure 5

The view from the walker. The red diamonds show $\langle k_W\rangle$ obtained directly by simulation, and the blue disks show $\langle k_W\rangle$ obtained from (4) with $\langle k^2\rangle$ obtained from simulation. The second moment, $\langle k_W^2\rangle$, is shown in the Supplemental Material [16]. $r_N=1$, $N=10000$, and $R=100000$ replicates.

Figure 6

Tunable walker influence. The graph depicts $\langle k_W\left(\alpha \right)\rangle$ as a function of walker motility $r_W$ for different time points (numbers of growth events or, equivalently, network sizes) $N$, with $r_N=1$ and $\alpha =0.5$. Data points are averaged over $10000$ replicates. We obtain the same graphs using both simulation data and (8) (not shown). Blue diamonds: $N=10000$, red disks: $N=20000$, orange squares: $N=50000$, brown asterisks: $N=100000$, green triangles: $N=200000$. The coupling parameter $\alpha =0.5$ has here half the value it has in Fig. 5. The dashed line is the graph shown in Fig. 5 but plotted against an abscissa scaled by a factor of $1/\alpha =2$.

Figure 7

Multiple walkers. The figure depicts the first moment of the degree distribution observed by two random walkers, 1 and 2, as a function of the movement rate of walker 2. (a) The red diamonds show $\langle k_W\rangle$ averaged over both walkers obtained directly by simulation, and the blue disks show $\langle k_W\rangle$ according to (6) with $m=2$ and $\alpha =1$, where $\langle k^2\rangle$ is obtained from simulation. (b) The mean degree seen by each walker as obtained from simulation directly. In both panels, $r_N=1$, $N=2000000$, and $R=100$ replicates.