Partition of networks into basins of attraction

We study partition of networks into basins of attraction based on a steepest ascent search for the node of highest degree. Each node is associated with, or “attracted” to its neighbor of maximal degree, as long as the degree is increasing. A node that has no neighbors of higher degree is a peak, attracting all the nodes in its basin. Maximally random scale-free networks exhibit different behavior based on their degree distribution exponent $\gamma$: For small $\gamma$ (broad distribution) networks are dominated by a giant basin, whereas for large $\gamma$ (narrow distribution) there are numerous basins, with peaks attracting mainly their nearest neighbors. We derive expressions for the first two moments of the number of basins. We also obtain the complete distribution of basin sizes for a class of hierarchical deterministic scale-free networks that resemble random nets. Finally, we generalize the problem to regular networks and lattices where all degrees are equal, and thus the attractiveness of a node must be determined by an assigned weight, rather than the degree. We derive the complete distribution of basins of attraction resulting from randomly assigned weights in one-dimensional chains.

Figure 1

(Color online) Decomposition of a network into basins of attraction. The number inside each node indicates its degree, and the arrows point from a node to its attractor—the neighbor with highest degree. Nodes with no neighbors of higher degree are peaks and are highlighted in the schematic. A peak represents a basin of attraction: All nodes which are attracted to it belong to its basin of attraction. The basins in this schematic have different background colors.

Figure 2

(Color online) Average density of basins in SF networks. Plotted is $⟨n_b⟩$ vs $\gamma$, as well as the density of solitary basins, $Q\left(1\right)$. Simulation results (symbols), for networks with $N=1000$ and $m=1,2$, are matched by theory, Eqs. (2, B2) (solid lines).

Figure 3

(Color online) Distribution of basin sizes in SF networks. Plotted is $Q\left(s\right)$ for three values of $\gamma$ ($N=1000$, $m=1$). Inset: The basin exponent $\alpha$, characterizing the power-law decay at small $s$, plotted vs the degree exponent $\gamma$.

Figure 4

(Color online) Degree of the peaks in SF networks. Plotted is the distribution of the degree of the peaks for three values of $\gamma$ ($N=1000$ and $m=1$). Inset: For large $\gamma$, the exponent $\beta$ characterizing the decay of the pdf (circles) follows $\gamma$ (solid line) very closely.

Figure 5

(Color online) Size of the largest basin. Plotted is the relative size of the largest basin $(S∕N)$ vs $\gamma$ for SF networks with $N={10}^3$, ${10}^4$, and ${10}^5$, and $m=1$. Inset: The largest basin’s exponent $\delta$ $(S\sim N^{\delta })$. For $\gamma \lesssim {\gamma }_c$, $\delta \simeq 1$ ($S\sim N$ is a giant basin), while for large $\gamma$, $\delta$ approaches $1∕(\gamma -1)$.

Figure 6

Hierarcical scale-free $(u,v)$-flowers. Shown are two examples of networks with degree exponent $\gamma =\ln (u+v)∕\ln 2=3$, with (a) $u=1$, $v=3$ and (b) $u=2$, $v=2$. In both cases the top of the figure illustrates the edge replacement scheme: Each edge is replaced by two parallel paths of $u$ and $v$ edges. The bottom of the figure shows flowers obtained in this way to generations $n=1$, 2, and 3.

Figure 7

(Color online) Schematic representation of a random surface in one dimension. Each node is attracted to its shortest neighbor (with periodic boundary conditions). The four highlighted nodes are valleys—their neighbors are taller. All nodes attracted to a valley belong to its basin of attraction. The four basins in the drawing are shown in different background colors.

Figure 8

(Color online) Illustration of the difference between basins of attraction and network communities. In the plotted toy network, the six nodes in the middle are fully connected and clearly form a single community. However, the three nodes on the left-hand side are attracted to the left hub, whereas the three nodes on the right-hand side are attracted to the right hub. Thus, they are split between two different basins of attraction (indicated with different background colors and different orientation of node fill patterns).

Figure 9

(Color online) Basin topology with local vs recursive search. (a) Density of basins and (b) the basin exponent $\alpha$ as a function of $\gamma$, in SF networks with $N=1000$ and $m=1$.

Figure 10

(Color online) Variance in number of basins for SF networks with $N=1000$ and $m=1$. Symbols represent simulation results, and the solid line corresponds to Eq. (B2). The dashed line is obtained by neglecting the covariance term and has the form $⟨n_b⟩(1-⟨n_b⟩)$ [where $⟨n_b⟩$ is calculated from Eq. (2)].