Random walks on activity-driven networks with attractiveness

Virtually all real-world networks are dynamical entities. In social networks, the propensity of nodes to engage in social interactions (activity) and their chances to be selected by active nodes (attractiveness) are heterogeneously distributed. Here, we present a time-varying network model where each node and the dynamical formation of ties are characterized by these two features. We study how these properties affect random-walk processes unfolding on the network when the time scales describing the process and the network evolution are comparable. We derive analytical solutions for the stationary state and the mean first-passage time of the process, and we study cases informed by empirical observations of social networks. Our work shows that previously disregarded properties of real social systems, such as heterogeneous distributions of activity and attractiveness as well as the correlations between them, substantially affect the dynamical process unfolding on the network.

Figure 1

Statistical properties of the time-aggregated network. Probability density function of nodes of given in- and out-degree (a) and strength (b) for different values of time-window $\tau$. Probability density function of links of given weight for different values of the time-window $\tau$ (c). Results are shown for $N={10}^5$, $m=6$, $F\left(a\right)\sim a^{-2}$, $G\left(b\right)\sim b^{-2.5}$. For $\tau ={10}^4$ the average in-degree is $\langle k_{\text{in}}\rangle =0.6$, for $\tau ={10}^5$ it is $\langle k_{\text{in}}\rangle =5.7$, and for $\tau ={10}^6$ it is $\langle k_{\text{in}}\rangle =57.9$. Note that the average out-degree equals the average in-degree.

Figure 2

Distribution of activity and attractiveness in real datasets. Probability density function of activity ($a$) and attractiveness ($b$) for the Linux dataset (a) and the Facebook dataset (b). In the Linux network there are $N=2.7\times {10}^4$ nodes, $E=1.0\times {10}^6$ edges, and the period of measurement lasts $T=2921$ days. For the Facebook network, there are $N=4.6\times {10}^4$ nodes, $E=8.6\times {10}^5$ edges, and $T=1591$ days

Figure 3

Correlation between activity and attractiveness in real datasets. Heat map showing the correlation between activity and attractiveness in two real datasets describing interactions between people involved in the development of Linux (a) and on Facebook (b). The continuous line describes the median correlation and the dashed line denotes a power-law fit with exponent $\beta$.

Figure 4

Stationary state of the random-walk process. The average number of walkers per node of class $a$ (a) and $b$ (b) computed analytically (continuous lines) and through numerical simulations (dots, squares, and triangles) for different values of exponent of the attractiveness distribution ${\gamma }_2$. Error bars are standard deviations obtained by averaging across ${10}^3$ different network configurations. In the above panel, they are not visible on the scale of the graph. We considered $N={10}^5$, $m=6$, $W/N=200$, and ${\gamma }_1=2$. The black line shows the case in which $b_i=1/N$ for all nodes.

Figure 5

Stationary state of the random-walk process for nodes of class $(a,b)$. Heat map giving the average number of walkers $W_{ab}$ per node of class $(a,b)$ computed through numerical simulations (a) and analytically (b). Colors are attributed based on $W_{ab}$ as shown in the colorbar on the bottom of the figure. We considered $N={10}^5$, $m=6$, $W/N=200$, ${\gamma }_1=2$, and ${\gamma }_2=2$.

Figure 6

Stationary state of the random walk in the aggregated case. The average number of walkers per node of class $a$ (a) and $b$ (b) computed analytically for $\tau =0$ (continuous line) and through numerical simulations for several values of $\tau$ (dots, squares, and triangles). Dashed lines are shown as a guide for the eye. Error bars obtained by averaging across ${10}^3$ different network configurations are not visible on the scale of the graph. We considered $N={10}^5$, $m=6$, $W/N=200$, ${\gamma }_1=2$, and ${\gamma }_2=2.5$.

Figure 7

Stationary state of the random walk in the correlated case. The average number of walkers per node of class $a$ (a) and $b$ (b) computed analytically (continuous lines) and through numerical simulations (dots, squares, triangles, and crosses) for different values of the correlation exponent $\beta$. Error bars obtained by averaging across ${10}^3$ different network configurations are not visible on the scale of the graph. We considered $N={10}^5$, $m=6$, $W/N=200$, and ${\gamma }_1=2$.

Figure 8

Mean first-passage time. The average MFPT as function of $a$ (a) and $b$ (b) computed analytically (continuous lines) and through numerical simulations (dots, squares, and triangles) for different values of the exponent of the attractiveness distribution ${\gamma }_2$. Error bars are standard deviations obtained by averaging across ${10}^3$ simulations. We considered $N={10}^3$, $m=6$, and ${\gamma }_1=2$.

Figure 9

Mean first-passage time for nodes of class $(a,b)$. Heat map for the average values of MFPT per node of class $(a,b)$ computed through numerical simulations (a) and analytically (b). Colors are attributed based on the value of MFPT as shown in the colorbar on the bottom of the figure. We considered $N={10}^3$, $m=6$, ${\gamma }_1=2$, and ${\gamma }_2=2$.