Spectral perturbation and reconstructability of complex networks

In recent years, many network perturbation techniques, such as topological perturbations and service perturbations, were employed to study and improve the robustness of complex networks. However, there is no general way to evaluate the network robustness. In this paper, we propose a global measure for a network, the reconstructability coefficient $\theta$, defined as the maximum number of eigenvalues that can be removed, subject to the condition that the adjacency matrix can be reconstructed exactly. Our main finding is that a linear scaling law, $E\left[\theta \right]=aN$, seems universal in that it holds for all networks that we have studied.

Figure 1

(Color online) Histograms of the entries of $A_{\left(5\right)}$, $A_{\left(10\right)}$, $A_{\left(15\right)}$, and $A_{\left(20\right)}$. The matrix $A\left(A=A_{\left(0\right)}\right)$ is the adjacency matrix of an Erdős-Rényi random graph with 36 nodes and link density of 0.5.

Figure 2

(Color online) Probability density function $f\left(\theta \right)$ for $N=200$ and $p=0.2,0.5,0.8$. For each $p$, 5000 samples of $\theta$ are computed and the histograms are fitted by Weibull distribution.

Figure 3

(Color online) Mean of reconstructability coefficient $E\left[\theta \right]$ of ER random graphs $G_{0.5}\left(N\right)$ with standard deviation ${\sigma }_{\theta }$ shown as Y-error bar. $E\left[\theta \right]$, which is fitted linearly in the figure, is computed from $10000$ samples for each $N$.

Figure 4

(Color online) Scaling law for random graphs with $p=0.1,0.2,\dots ,0.9$. We compute $10000$ samples of $\theta$ to get the mean $E\left[\theta \right]$.

Figure 5

(Color online) Curve fitting of the slope $a\left(p\right)$.

Figure 6

(Color online) $E\left[\theta \right]$ of Erdős-Rényi random graphs $G_p\left(200\right)$ for $p$. $E\left[\theta \right]$ is computed by $10000$ samples of $\theta$. The function $E\left[\theta \right]$ of $p$, where $p∊\left[0.09,0.91\right]$, is fitted by a parabola.

Figure 7

(Color online) Linear scaling law for $E\left[\theta \right]$ of Barabási-Albert networks. $E\left[\theta \right]$ is obtained by $10000$ samples. $m_0$ is the number of nodes of the initial graph and for each time step, the coming node can add $m$ links to the current graph.

Figure 8

(Color online) Linear scaling law for $E\left[\theta \right]$ of Watts-Strogatz networks. $E\left[\theta \right]$ is obtained by $10000$ samples. For the initial ring lattice graph, every node has links with its $k$ nearest nodes and $p_r$, defined as the randomness, is the probability with which each link is rewired.

Figure 9

(Color online) Linear scaling law for $E\left[\theta \right]$ of six special deterministic types of graphs. For path graph, ring graph, and wheel graphs, $N=100,200,300,\dots ,800$. We take $N=25,100,225,400,625,900$, $N=8,27,64,125,216,343,512,729$, and $N=16,81,256,625$ for grid graphs, cubic graphs, and four-dimensional lattice graphs, respectively.

Figure 10

(Color online) Linear scaling law with normalized eigenvector perturbation for Erdős-Rényi random graphs. $E\left[\theta \right]$ is the mean of $10000$ samples of $\theta$. The scaling factors $\epsilon$ are shown in the legend. The link density $p=0.5$.