Structure Entropy and Resistor Graphs

Abstract

We propose the notion of {\it resistance of a graph} as an accompanying notion of the structure entropy to measure the force of the graph to resist cascading failure of strategic virus attacks. We show that for any connected network $G$, the resistance of $G$ is $\mathcal{R}(G)=\mathcal{H}^1(G)-\mathcal{H}^2(G)$, where $\mathcal{H}^1(G)$ and $\mathcal{H}^2(G)$ are the one- and two-dimensional structure entropy of $G$, respectively. According to this, we define the notion of {\it security index of a graph} to be the normalized resistance, that is, $θ(G)=\frac{\mathcal{R}(G)}{\mathcal{H}^1(H)}$. We say that a connected graph is an $(n,θ)$-{\it resistor graph}, if $G$ has $n$ vertices and has security index $θ(G)\geqθ$. We show that trees and grid graphs are $(n,θ)$-resistor graphs for large constant $θ$, that the graphs with bounded degree $d$ and $n$ vertices, are $(n,\frac{2}{d}-o(1))$-resistor graphs, and that for a graph $G$ generated by the security model \cite{LLPZ2015, LP2016}, with high probability, $G$ is an $(n,θ)$-resistor graph, for a constant $θ$ arbitrarily close to $1$, provided that $n$ is sufficiently large. To the opposite side, we show that expander graphs are not good resistor graphs, in the sense that, there is a global constant $θ_0<1$ such that expander graphs cannot be $(n,θ)$-resistor graph for any $θ\geqθ_0$. In particular, for the complete graph $G$, the resistance of $G$ is a constant $O(1)$, and hence the security index of $G$ is $θ(G)=o(1)$. Finally, we show that for any simple and connected graph $G$, if $G$ is an $(n, 1-o(1))$-resistor graph, then there is a large $k$ such that the $k$-th largest eigenvalue of the Laplacian of $G$ is $o(1)$, giving rise to an algebraic characterization for the graphs that are secure against intentional virus attack.