Existence of equilibrium games and resistance to cascading attacks in networks

In the two-player cascading-failure game introduced by Li, Zhang, Pan, and Peng (Physica A, 2014), an attacker Alice infects a small initial set of nodes of a network and a defender Bob protects nodes during the ensuing threshold cascade. The paper established that Erdős–Rényi random networks are resistable, that preferential-attachment power-law networks are non-resistable and admit no equilibrium game for the defender strategies it evaluated, that homophyly-model networks at homophyly exponent $a=1.5$ admit equilibrium games but are not resistable, and that all real networks tested are non-resistable for the strategies considered. It posed two linked open questions that remain open in their core: (1) which mechanisms and mathematical properties of networks guarantee the existence of equilibrium games — in particular, the conjecture that homophyly together with preferential attachment is the underlying mechanism, for which the related provable-security theorems of the authors' successor line cover only a large-exponent regime ($a>4$ uniform thresholds, $a>6$ random thresholds) of a three-mechanism security model and not the empirically relevant regime; and (2) how cascading failures caused by attacks on a small number of nodes can be resisted in power-law networks and real-world network data, where no effective defender strategy has been established and no impossibility result is known.

Background

A threshold cascade on a network $G=(V,E)$ proceeds as follows: each node $v$ has a threshold $\phi(v)$, and $v$ becomes infected (or fails) once at least a $\phi(v)$ fraction of its neighbors are infected; the process starts from an initially attacked set. This is the classic Watts global-cascade mechanism adapted to heterogeneous thresholds, with $\phi(v)$ drawn uniformly from $\{1/d(v),2/d(v),\dots,1\}$, where $d(v)$ is the degree of $v$. Li, Zhang, Pan, and Peng (2014) embedded this cascade in a two-player game: the attacker Alice chooses an initial set $X$ of at most $k$ nodes, where $k$ is bounded by a polynomial in $\log n$ ($n$ is the number of nodes), together with a program for subsequent choices; the defender Bob chooses which nodes to protect, the defender strategies the paper evaluates being budget-$k$ heuristics (for example, $\beta_1$: the $k$ highest-degree neighbors of $X$; $\beta_2$: the $k$ highest-degree nodes influencing nodes likely to be agitated; $\beta_3$: the $k$ highest-degree seed nodes of communities hit or adjacent to the attack). Writing $a_{\mathcal A,\mathcal B}^{G}(\phi,k)$ for the number of nodes agitated (infected) by Alice under Bob's strategy and $b_{\mathcal A,\mathcal B}^{G}(\phi,k)$ for the number of nodes protected by Bob, the network $G$ has an equilibrium game if for every Alice strategy there is a Bob strategy with $a_{\mathcal A,\mathcal B}^{G}-b_{\mathcal A,\mathcal B}^{G}=o(n)$ with high probability over the random thresholds, and is resistable if for every Alice strategy there is a Bob strategy with $a_{\mathcal A,\mathcal B}^{G}=o(n)$ with high probability. The two conditions differ in the defender class they use: the equilibrium-game condition is the weaker balance requirement and is not restricted to budget-$k$ defenders, so the protected count $b$ need not be $o(n)$ and $a_{\mathcal A,\mathcal B}^{G}-b_{\mathcal A,\mathcal B}^{G}=o(n)$ can hold even while Alice still agitates a linear number of nodes, whereas resistability is the strictly stronger demand, met by a budget-$k$ defender, that the agitation $a_{\mathcal A,\mathcal B}^{G}$ itself be $o(n)$. The networks considered are generated by the Erdős–Rényi (ER) random graph model (each edge present independently), the preferential-attachment (PA) model of Barabási and Albert (new nodes attach to high-degree endpoints, producing power-law degree distributions, i.e. the fraction of nodes of degree $d$ decays polynomially), and the homophyly model of Li, Li, and Pan (arXiv:1310.8295), in which a new node created at step $i$ becomes the seed of a new color with probability $1/(\log i)^{a}$ and otherwise attaches preferentially within a uniformly chosen old color (homophyly, the tendency of like nodes to connect, with a homophyly exponent $a$ governing community sizes); this model has exactly two mechanisms, homophyly and preferential attachment, whereas the sibling security model described below adds random seed edges (randomness) as a third mechanism. The paper's conclusions: ER networks (average degree 8–11) have equilibrium games and are resistable; PA networks fail both for the Bob strategies $\mathcal B_1,\mathcal B_2$ considered; homophyly networks at $a=1.5$ have an equilibrium game yet are non-resistable; among real networks, Amazon co-purchase snapshots have equilibrium games while a financial network and four social networks do not, and all real networks tested are non-resistable for the Bob strategies considered. The same group's successor line defined a security model (seed probability $1/(\log i)^{a}$ with homophyly exponent $a$, preferential attachment inside homochromatic sets, and random seed edges) and proved (Li, Li, Pan, Zhang, Sci. China Inf. Sci. 2015; Li, Pan, Internet Mathematics 2016) that for $a>4$ with uniform thresholds, and for $a>6$ with random thresholds, every attack of size $\log^{c}n$ infects only $o(n)$ nodes with high probability, while the network retains a power-law degree distribution, small-world distances, and navigability (meaning that a short path between any two given nodes can be found by a decentralized $O(\log n)$-time algorithm) — provable security by construction, which trivially implies resistability for networks of this model, but only in this large-exponent regime, only for the three-mechanism security model, and in theorems that contain no defender. A four-step augmentation algorithm (partition into communities, designate hub seeds, rewire weak inter-community links to seeds, rebuild) was proposed in that sibling line to harden given networks, without provable guarantees; the sibling line frames network hardening as a separate open problem — modifying a given network $G$ into a more secure network $H$ (arXiv:1310.8388, Section 10, item 4) — distinct from defending the given network inside the game, and the related resistance-metric line (Li, Hu, Liu, Pan, Sci. Rep. 2016; Li, Zhang, Pan, Physica A 2017) developed structural-entropy measures of defendability (structural entropy being an information-theoretic quantity measuring the residual uncertainty of a network's structure) and left the corresponding optimization and characterization problems open.

Problem Statement

Within the two-player cascading-failure game of Li, Zhang, Pan, and Peng (2014) — attacker budget $k$ bounded by a polynomial in $\log n$, node thresholds $\phi(v)$ uniform from $\{1/d(v),\dots,1\}$, equilibrium game meaning that for every Alice strategy some Bob strategy keeps the agitation-minus-protection difference at $o(n)$ with high probability over the random thresholds, and resistable meaning that for every Alice strategy some budget-$k$ Bob strategy keeps the agitation itself at $o(n)$ — the open problem has two jointly posed facets that share one objective, a structure-versus-defendability theory for this game: (1) characterize the mechanisms and mathematical properties of networks that guarantee the existence of equilibrium games, and in particular prove or refute the paper's conjecture that homophyly combined with preferential attachment is the underlying mechanism by which homophyly networks admit equilibrium games — the existing provable-security theorems concern the three-mechanism security model of the sibling line, cover only homophyly exponents $a>4$ (uniform thresholds) and $a>6$ (random thresholds), and are stated for cascades without a defender, whereas the equilibrium-game phenomenon was reported at $a=1.5$, a regime those theorems do not cover; and (2) determine how cascading failures caused by attacks on a small number of nodes can be resisted by the defender in power-law networks and in real-world network data, where no effective defender strategy has been established and no impossibility result is known. The two facets are linked by the common question of which structures make the threshold-cascade game winnable by the defender. Resolving the task means settling both facets: for facet (1) a proof or refutation of the homophyly-plus-preferential-attachment conjecture suffices, a full characterization of the mechanisms that guarantee equilibrium games being a strictly stronger result that subsumes it, and for facet (2) either an effective defender strategy achieving $o(n)$ agitation or an impossibility result ruling one out, in power-law networks and in real-world network data; settling only one facet is a partial contribution and does not by itself resolve the objective.

References

1. Angsheng Li, Xiaohui Zhang, Yicheng Pan, Pan Peng. Equilibrium games in networks. Physica A: Statistical Mechanics and its Applications 416 (2014) 49-60. DOI: 10.1016/j.physa.2014.08.028. https://doi.org/10.1016/j.physa.2014.08.028 (source paper)
2. AngSheng Li, XueChen Li, YiCheng Pan, Wei Zhang. Strategies for network security. Science China Information Sciences 58(1) (2015) 1-14. DOI: 10.1007/s11432-014-5182-9. https://doi.org/10.1007/s11432-014-5182-9
3. Angsheng Li, Yicheng Pan, Wei Zhang. Provable Security of Networks. arXiv:1310.8388 (2013). https://arxiv.org/abs/1310.8388
4. Angsheng Li, Wei Zhang, Yicheng Pan, Xuechen Li. Homophyly and Randomness Resist Cascading Failure in Networks. arXiv:1310.8040 (2013). https://arxiv.org/abs/1310.8040
5. Angsheng Li, Jiankou Li, Yicheng Pan. Homophyly Networks — A Structural Theory of Networks. arXiv:1310.8295 (2013). https://arxiv.org/abs/1310.8295
6. Angsheng Li, Jiankou Li, Yicheng Pan, Xianchen Yin, Xi Yong. Homophyly/Kinship Model: Naturally Evolving Networks. Scientific Reports 5 (2015) 15140. DOI: 10.1038/srep15140. https://doi.org/10.1038/srep15140
7. Angsheng Li, Yicheng Pan. A Theory of Network Security: Principles of Natural Selection and Combinatorics. Internet Mathematics 12(3) (2016) 145-204. DOI: 10.1080/15427951.2015.1098755. https://doi.org/10.1080/15427951.2015.1098755
8. Angsheng Li, Qifu Hu, Jun Liu, Yicheng Pan. Resistance and Security Index of Networks: Structural Information Perspective of Network Security. Scientific Reports 6 (2016) 26810. DOI: 10.1038/srep26810. https://doi.org/10.1038/srep26810
9. Angsheng Li, Xiaohui Zhang, Yicheng Pan. Resistance maximization principle for defending networks against virus attack. Physica A: Statistical Mechanics and its Applications 466 (2017) 211-223. DOI: 10.1016/j.physa.2016.09.009. https://doi.org/10.1016/j.physa.2016.09.009
10. Likang Yin, Yong Deng. Toward uncertainty of weighted networks: An entropy-based model. Physica A: Statistical Mechanics and its Applications 508 (2018) 176-186. DOI: 10.1016/j.physa.2018.05.067. https://doi.org/10.1016/j.physa.2018.05.067