Self-organisation of small-world networks by adaptive rewiring in response to graph diffusion

Abstract

Complex networks emerging in natural and human-made systems tend to assume small-world structure. Is there a common mechanism underlying their self-organisation? Our computational simulations show that network diffusion (traffic flow or information transfer) steers network evolution towards emergence of complex network structures. The emergence is effectuated through adaptive rewiring: progressive adaptation of structure to use, creating short-cuts where network diffusion is intensive while annihilating underused connections. With adaptive rewiring as the engine of universal small-worldness, overall diffusion rate tunes the systems' adaptation, biasing local or global connectivity patterns. Whereas the former leads to modularity, the latter provides a preferential attachment regime. As the latter sets in, the resulting small-world structures undergo a critical shift from modular (decentralised) to centralised ones. At the transition point, network structure is hierarchical, balancing modularity and centrality - a characteristic feature found in, for instance, the human brain.

Figure 1

(a) Depicts the small-world index S as a function of decreasing random rewiring probability p ∈ {0, 1/30, …, 29/30, 1}: Coloured lines indicate values of heat kernel parameter $\tau \in \mathrm{\{0,}\epsilon ,\mathrm{1,}\mathrm{8,}\delta \}$,  black line indicates the Watts-Strogatz algorithm with random rewiring probability $p\in \mathrm{\{0,}\mathrm{1/500,}\dots ,\mathrm{499/500,}\mathrm{1\}}$. (b) Depicts the average modularity Q as a function of decreasing random rewiring probability $p\in \mathrm{\{0,}\mathrm{1/30,}\dots ,\mathrm{29/30,}\mathrm{1\}}$: Coloured lines indicate values of heat kernel parameter $\tau \in \mathrm{\{0,}\epsilon ,\mathrm{1,}\mathrm{8,}\delta \}$. (c,d) Single trial. Example modular SWN. Adjacency matrices mapped to an n-by-n grid where rows (and columns) represent vertices and white indicates the existence of an edge. Rows and columns of adjacency matrices have been permuted to visualise the modules, in accordance with. (c) $(\tau ,p)=(\epsilon ,\mathrm{0.1)}$; (d) $(\tau ,p)=\mathrm{(1,}\mathrm{0.3)}$.

Figure 2

(a) Depicts the average π - maximum element of PageRank vector normalised by its mean - as a function of decreasing random rewiring probability $p\in \mathrm{\{0,}\mathrm{1/30,}\dots ,\mathrm{29/30,}\mathrm{1\}}$: Coloured lines indicate values of heat kernel parameter $\tau \in \mathrm{\{0,}\epsilon ,\mathrm{1,}\mathrm{8,}\delta \}$. (b) Depicts the bar-plot in which the height of individual bars is the average number of vertices having degree d _v, where $d_v\le 20$. Inset bar-plot for vertex degrees d _v, where 20 ≤ d _v ≤ 70. Probability density function (PDF) curves fitted to d _v: truncated normal PDF for $\tau \in \mathrm{\{0,}\epsilon ,\mathrm{1\}}$ and truncated and normalised lognormal PDF for $\tau \in \mathrm{\{8,}\delta \}$. Coloured bars (and curves) indicate values of heat kernel parameter $\tau$; for each, $p$ is chosen dependent on $\tau$ such that S is at maximum. (c,d) Single trial. Example centralised SWN. Adjacency matrices mapped to an $n$-by-$n$ grid where rows (and columns) represent vertices and white indicates the existence of an edge. Rows and columns of adjacency matrices have been permuted to visualise the modules, in accordance with. (c) Depicts $(\tau ,p)=\mathrm{(8,\; 0.5667)}$; (d) depicts $(\tau ,p)=(\delta \mathrm{,\; 0.5667)}$.

Figure 3

(a,b) In the plane $\tau \in \mathrm{\{4.50,}\mathrm{4.55,}\dots ,\mathrm{5.45,}\mathrm{5.50\}}$ along the horizontal axis and random rewiring probability $p\in \mathrm{\{0,}\mathrm{1/30,}\dots ,\mathrm{29/30,}\mathrm{1\}}$ along the vertical axis. (a) Depicts the modularity index $Q$; (b) Depicts π, the maximum element of the PageRank vector normalised by its mean value. (c) For $\tau =5$, along the horizontal axis random rewiring probability $p\in \mathrm{\{0.400,}\mathrm{0.402,}\dots ,\mathrm{0.598,}\mathrm{0.600\}}$. Along the vertical axis are $Q$ the modularity index (left, blue), and $\pi$ the maximum element of PageRank vector normalised by its mean value (right, red). (d) Single trial. Example critical SWN. Adjacency matrix mapped to an $n$-by-$n$ grid where rows (and columns) represent vertices and white indicates the existence of an edge. Rows and columns of adjacency matrices have been permuted to visualise the modules, in accordance with. Pair $(\tau ,p\mathrm{)\; =\; (5,\; 0.522)}$.