Self-organization of complex networks as a dynamical system

To understand the dynamics of real-world networks, we investigate a mathematical model of the interplay between the dynamics of random walkers on a weighted network and the link weights driven by a resource carried by the walkers. Our numerical studies reveal that, under suitable conditions, the co-evolving dynamics lead to the emergence of stationary power-law distributions of the resource and link weights, while the resource quantity at each node ceaselessly changes with time. We analyze the network organization as a deterministic dynamical system and find that the system exhibits multistability, with numerous fixed points, limit cycles, and chaotic states. The chaotic behavior of the system leads to the continual changes in the microscopic network dynamics in the absence of any external random noises. We conclude that the intrinsic interplay between the states of the nodes and network reformation constitutes a major factor in the vicissitudes of real-world networks.

Figure 1

Schematic illustration of co-evolving network dynamics, combining the dynamics of the resource carried by random walkers and the resource-driven dynamics of the link weights.

Figure 2

Typical behavior of the co-evolving dynamics. At each time, the resource is concentrated into a few nodes, which strengthens the link weights around them. Resource quantities at the nodes and the link weights between them continue to change forever at the microscopic level, whereas they converge to heterogeneous distributions at the macroscopic level. The parameters are as follows: $\kappa$ = 0.05, $D$ = 0.34, and $\epsilon$ = 0.01.

Figure 3

(a) Distribution of the resource quantity $x_i$ in the equilibrium state for a large network. Parameters are the same as in Fig. 2, except that the underlying network is given by an Erdös-Rényi random graph ($N$ = 16 384, $\langle k\rangle$ = 10). (b) Weight distribution. (c) Time developments of the resource quantities for several selected nodes.

Figure 4

Another model parameter with lower $D$ leads to the organization of the homogeneous network. Parameters are the same as in Figs. 2 and 3, except that $D$ = 0.05. (a) Typical behavior of a small network. Changes of the resource quantities at nodes are difficult to see in the scale of the graphs. (b) Time development of the resource at several sampled nodes in a large network (Erdös-Rényi random graph with $N$ = 16 384, $\langle k\rangle$ = 10). Values converge to different constants. (c) Resulting resource distribution in the organized network. (d) Same plot as in (b), except that the underlying network is given by regular random graphs with $k$ = 10.

Figure 5

(a) Exponents of the power-law distributions of the resource, ${\gamma }_x$, in $(D,\kappa )$ space. In the colored area, the distribution takes the form of a power law, whose exponents are indicated with the color coding on the right. In the white area, the distribution does not take the power law form. (b) Exponents of the power-law distributions of the link weights, ${\gamma }_w$, in $(D,\kappa )$ space.

Figure 6

Rate of change of the resource, measured by $log\langle V\rangle$ in Eq. (7), plotted in $(D,\kappa )$ space.

Figure 7

Relationship between the exponents of resource ${\gamma }_x$ and link weights ${\gamma }_w$. Points indicate the numerical results. Lines show the theoretical predictions under two extreme conditions.

Figure 8

$\epsilon$ dependence of the organized network. Graph plots the exponent of the power-law resource distribution as a function of $D$. Parameters are the same as in Fig. 5, except that $\kappa$ = 0.05.

Figure 9

The model exhibits a structurally unstable behavior that only appears if the underlying network is given by the complete graph. In the entire range of the possible parameters, the system always converges to the completely homogeneous state, i.e., $x_i=w_{ij}=1$. (a) On the perfectly complete graph, the resource quantities at all nodes converge to the same value. (b) Slight modification of the complete graph (0.1% of links are removed) destroys the resource configuration in (a), and a heterogeneous resource distribution emerges. (c) Exponents ${\gamma }_x$ of the power-law distributions of the resource in $(D,\kappa )$ space for various connection probabilities $p$ in an Erdös-Rényi random graph. Parameters are the same as in Fig. 5, except for $N$ = 1024.

Figure 10

(a) Liner stability of the homogeneous solution, i.e., $x_i=w_{ij}=1$ for all nodes, in the case of a regular random graph. Solution is stable in the blue region and unstable in the red region. (b) Stable (blue) and unstable (red) regions of the homogenous solution obtained from the full simulation of the model equations.

Figure 11

Three types of microscopic behaviors seen in the case of a small network ($N$ = 512, $k$=5, $\kappa$ = 0.05, $D$ = 0.4, and $\epsilon$ = 0.01). (a) Fixed point with a long relaxation time. (b) Limit-cycle oscillation with a long periodic time. (c) Chaotic state. Graphs in the left column depict the total displacement rate given by $\left|\mathbf{z}\right(t+1)-\mathbf{z}(t\left)\right|$, where $\mathbf{z}\left(t\right)=\{x_i\left(t\right),w_{ij}\left(t\right)\}$, where $\lambda$ is the maximum Lyapunov exponent. Graph in the middle column shows the time development of the resource at several nodes. Graph in the right column indicates the cumulative resource distribution.

Figure 12

Percentages of the fixed, periodic, and chaotic states. (a) Dependence on $T_s$ for $N$ = 512. (b) Dependence on the network size $N$ for $T_s$ = $1.28\times {10}^8$.

Figure 13

Pattern formation on the regular lattices. (a) The destabilization of the homogeneous solution under a regular, ring topology induces a Turing-like wave of the resource distribution. (b) A static spot pattern is observed on a two-dimensional lattice. Other parameters are the same as in Fig. 3.