Self-avoiding walks and connective constants in clustered scale-free networks

Various types of walks on complex networks have been used in recent years to model search and navigation in several kinds of systems, with particular emphasis on random walks. This gives valuable information on network properties, but self-avoiding walks (SAWs) may be more suitable than unrestricted random walks to study long-distance characteristics of complex systems. Here we study SAWs in clustered scale-free networks, characterized by a degree distribution of the form $P\left(k\right)\sim k^{-\gamma }$ for large $k$. Clustering is introduced in these networks by inserting three-node loops (triangles). The long-distance behavior of SAWs gives us information on asymptotic characteristics of such networks. The number of self-avoiding walks, $a_n$, has been obtained by direct enumeration, allowing us to determine the connective constant $\mu$ of these networks as the large-$n$ limit of the ratio $a_n/a_{n-1}$. An analytical approach is presented to account for the results derived from walk enumeration, and both methods give results agreeing with each other. In general, the average number of SAWs $a_n$ is larger for clustered networks than for unclustered ones with the same degree distribution. The asymptotic limit of the connective constant for large system size $N$ depends on the exponent $\gamma$ of the degree distribution: For $\gamma >3, \mu$ converges to a finite value as $N\to \infty$; for $\gamma =3$, the size-dependent ${\mu }_N$ diverges as $lnN$, and for $\gamma <3$ we have ${\mu }_N\sim N^{(3-\gamma )/2}$.

Figure 1

Schematic representation of a typical network considered in this work, for which one separately specifies the number of single edges and triangles (bold red edges) attached to each node. Triangles are indicated as T. Arrows indicate a possible SAW starting from node A. For the fourth step ($n=4$), there are three available edges (one $s$ link and two $t$ links) reaching nodes B, C, and D.

Figure 2

Probability density $P\left(k\right)$ as a function of the degree $k$ for networks with $\gamma =3$, minimum degree $k_0$ = 3, and $N={10}^5$ nodes. The displayed data are an average over 200 network realizations for each value of the parameter $\nu$ = 0, 1, and 2.

Figure 3

Clustering coefficient $C$ as a function of the triangle density $\nu$ for clustered scale-free networks. (a) $\gamma =5$ and various values of the minimum degree $k_0$. From top to bottom, $k_0$ = 3, 5, 7, and 9. Solid circles represent results derived from clustered networks with $N={10}^5$ nodes. Solid lines were analytically derived in the limit $N\to \infty$ by using the expressions given in the text. (b) $\gamma =2.5$ and three different network sizes: $N={10}^3, {10}^4$, and ${10}^5$. Solid lines were calculated by using the formulas for ${\langle s\rangle }_N$ and ${\langle s^2\rangle }_N$ given in Sec. 2 for $\gamma <3$.

Figure 4

Parameter ${\delta }_n$ as a function of the step number $n$ for clustered scale-free networks with triangle density $\nu =1$, size $N=128000$ nodes, and minimum degree $k_0=3$. Symbols correspond to different values of the exponent $\gamma$: 5 (circles), 3 (squares), and 2.5 (diamonds).

Figure 5

Connective constant $\mu$ vs triangle density $\nu$ for clustered scale-free networks with several values of the exponent $\gamma$: From top to bottom $\gamma$ = 4, 5, 8, and 1000. The networks size is $N$ = 128,000 and the minimum degree $k_0=3$. Solid lines correspond to the analytical procedure described in Sec. 4, whereas symbols were derived from enumeration of SAWs in clustered networks. Error bars are less than the symbol size.

Figure 6

Connective constant ${\mu }_N$ as a function of system size $N$ for scale-free networks with $\gamma =3$ and triangle density $\nu =2$. The solid and dashed lines were obtained analytically for clustered and unclustered (configuration model) networks, respectively. Symbols correspond to results found from simulated scale-free networks. Error bars are smaller than the symbol size.

Figure 7

Connective constant ${\mu }_N$ vs. triangle density $\nu$ for scale-free networks with $\gamma =3$ and $k_0=3$. The data shown correspond to two different network size: $N$ = 512 000 (top) and 32 000 (bottom). Solid and dashed lines correspond to analytical calculations for networks with and without triangles, respectively. Symbols are results derived from network simulations. Error bars are of the order of the symbol size. “cl” and “un” refer to clustered and unclustered SF networks, respectively.

Figure 8

Connective constant ${\mu }_N$ as a function of system size $N$ for scale-free networks with $\gamma =2.5$ and triangle density $\nu =2$. The solid and dashed lines were obtained analytically for clustered and unclustered networks, respectively. Symbols correspond to results obtained from simulated scale-free networks. Error bars are less than the symbol size.

Figure 9

Connective constant ${\mu }_N$ vs. triangle density $\nu$ for clustered SF networks with $\gamma =2.5$: the solid line is the result of the analytical model described in Sec. 4, whereas solid circles are data points derived from enumeration of SAWs in simulated clustered networks. The dashed line and solid squares correspond to unclustered networks (configuration model). Error bars are less than the symbol size.