Research Article

Resilience of networks with community structure behaves as if under an external field

Gaogao Dong, Jingfang Fan, Louis M. Shekhtman, Saray Shai, Ruijin Du, Lixin Tian, Xiaosong Chen, H. Eugene Stanley, and Shlomo Havlin
PNAS July 3, 2018 115 (27) 6911-6915; first published June 20, 2018; https://doi.org/10.1073/pnas.1801588115

  1. Contributed by H. Eugene Stanley, May 24, 2018 (sent for review February 1, 2018; reviewed by Antonio Coniglio and Igor M. Sokolov)

Significance

Much work has focused on phase transitions in complex networks in which the system transitions from a resilient to a failed state. Furthermore, many of these networks have a community structure, whose effects on resilience have not yet been fully understood. Here, we show that the community structure can significantly affect the resilience of the system in that it removes the phase transition present in a single module, and the network remains resilient at this transition. In particular, we show that the effect of increasing interconnections is analogous to increasing external magnetic field in spin systems. Our findings provide insight into the resilience of many modular complex systems and clarify the important effects that community structure has on network resilience.

Abstract

Although detecting and characterizing community structure is key in the study of networked systems, we still do not understand how community structure affects systemic resilience and stability. We use percolation theory to develop a framework for studying the resilience of networks with a community structure. We find both analytically and numerically that interlinks (the connections among communities) affect the percolation phase transition in a way similar to an external field in a ferromagnetic– paramagnetic spin system. We also study universality class by defining the analogous critical exponents δ and γ, and we find that their values in various models and in real-world coauthor networks follow the fundamental scaling relations found in physical phase transitions. The methodology and results presented here facilitate the study of network resilience and also provide a way to understand phase transitions under external fields.

Network science has opened new perspectives in the study of complex networks in social, technological, biological, and climatic systems (1⇓⇓⇓⇓–7). System resilience (robustness) plays a crucial role in reducing risk and mitigating damage (8, 9). Percolation theory is a useful tool for understanding and evaluating resilience in terms of topological and structural properties (10⇓⇓⇓–14). It analyzes the connectivity of network components and has been applied to many natural and man-made systems (15). Critical phenomena in social and complex networks have attracted the attention of researchers in a number of different disciplines (16). In particular, researchers have studied the existence of phase transitions in connectivity (percolation) (3, 4), stringent k-core percolation (17, 18), epidemic spreading (19⇓–21), condensation transitions, and the Ising model in complex networks (22). A random network undergoes a continuous percolation phase transition as the fraction of random node failures increases (23). The question of whether there are discontinuous percolation transitions in networks has attracted much attention (24⇓–26). Buldyrev et al. (27) developed an interdependent network model and found analytically that cascading failures among networks cause the percolation transition to be discontinuous. A framework for understanding the robustness of interdependent networks was then developed, and it was found that a system of interdependent networks undergoes an abrupt first-order percolation phase transition (27⇓⇓⇓⇓⇓⇓–34).

In addition to these advances in understanding network resilience, much work has focused on such interconnected networks (35) as those formed by connecting several communities (or modules) (36, 37). This community structure is ubiquitous in many real-world networks, including brain (38⇓–40), infrastructure (41, 42), and social networks (43⇓–45), among others (46⇓⇓–49). Despite these advances, we still do not understand how a small fraction of nodes can sustain intermodule connections in real-world networks. This feature dramatically affects network resilience. The small fraction of interconnecting nodes often provide special resources and infrastructure support. For example, only some airports have the longer runways, customs administration, and passport control required for international flights (41), and when an airport node already has interconnections, the cost of adding additional interconnections is significantly lower. Similarly, only some individuals in social networks are able to bridge between communities (50), and only some power stations in a power grid are able to supply distant stations. We use here the methods of statistical physics to develop a model that incorporates these realistic features, and we develop an analytic solution that demonstrates that these interconnections have effects analogous to those of an external field on a spin system. This gives us a fundamental understanding of the effects of adding interconnections and enables us to predict systemic resilience.

Model

Our model is based on the modular structure present in many real-world networks, where a number of well-connected groups of nodes (modules) have only some nodes with connections to other modules, as shown in Fig. 1A. We show here that these “interconnected nodes” act in a manner analogous to an external field from physics (51⇓–53). For simplicity, we demonstrate this with a network of two modules i and j with the same number of nodes N. Our theory is general for m communities. Nodes within module i [j] are randomly connected with a degree distribution Pi(k) [Pj(k)], where the degree k is the number of links a node has to other nodes in module i [j]. Between modules i and j, we randomly select a fraction, r, of nodes as interconnected nodes and randomly assign Minter interconnected links among pairs of nodes (one in i and the other in j). A network generated from this model can be seen in Fig. 1B. The generalization to m modules is straightforward. To quantify the resilience of our model, we study analytically and via simulations the size of the giant connected component S(r,p) after randomly removing a fraction 1−p of the nodes.

Fig. 1.
Fig. 1.

(A) Demonstration of two interconnected modules from the coauthor collaboration network (dblp). Nodes are authors, and a link between two nodes exists if two authors have published at least one paper together. (B) Demonstration of the model. We assume two modules i and j and connect a fraction r of nodes. Red nodes denote interconnected nodes, and the fraction of interconnected nodes here is r = 1/2.

Theory

We develop a theoretical framework for studying the robustness of our interconnected community network model. To obtain an analytic solution, we adopt the generating function framework of ref. 4 and define the generating function of the degree distribution for each module i to beGi(x)=(1−ri)Gii(xii)+riGii(xii)∏j≠imGij(xij),[1]where Gii(xii) and Gij(xij) are the generating functions of the intraconnections in module i and the interconnections between modules i and j, respectively, i,j=1,2,…,m, and m is the number of modules. The generating functions of the excess degree distribution are in SI Appendix, Eq. 1. After randomly removing a fraction 1−p of nodes, the size of the giant component within module i isSi=p(1−Gi(1−p(1−fii),1−p(1−fij))),[2]where xii=1−p(1−fii) and xij=1−p(1−fij).

When m=2, the Erdős–Rényi (ER) (54) modules have an average intradegree k and an interdegree K. Eq. 2 becomese−Sk(r−1)+1−Sp=r⁡expKp(e−Sk(r−1)+1−Sp−r)r− Sk,[3]where K=2Minter/rN and N is the size of network. For r=0, our model is equivalent to the ER model, and we obtain S=p(1−e−kS), in agreement with the well-known result (54). For a single ER network [N→∞], the size of the giant component is zero at the percolation threshold pc=1/k, yet for our model with r>0, we have a nonzero giant component at that point. We obtain a percolation threshold for our model that is proportional to r, which is assumed to be small (SI Appendix).

We also examine scale-free (SF) modules with power-law degree distribution P(k)∼k−λ. The same generating function framework is used to obtain the giant component and percolation threshold (SI Appendix).

Results

We analyze our analytical solution above, Eq. 3, and find that the r interconnected nodes have effects analogous to those caused by a magnetic field in a spin system. This is because (i) for any nonzero fraction of interconnected nodes, the system no longer undergoes a phase transition of the single module; and (ii) field-type critical exponents characterize the effect of r. Fig. 2A shows our analytic and simulation results for the giant component in two ER modules with an average degree k=4 and several r values. Note that although the percolation threshold is pc=1/k=1/4 for a single ER module, the size of the giant component is above zero at pc when r>0. The theoretical and simulation results are in excellent agreement. Fig. 3 A–C shows a similar phenomenon in modules with a SF distribution with different λ values.

Fig. 2.
Fig. 2.

(A) Comparison of analytical and simulation results for ER networks for the size of the giant component S(r,p) as a function of p with r=0 (red), r=0.0001 (blue), r=0.0055 (purple), and r=0.001 (magenta). Lines and symbols denote analytical and simulation results, respectively. (B) S(r,pc) as a function of r. (C) ∂S(r,p)∂r as a function of pc−p with r=0.0001. C, Left and C, Right show the numerical and simulation results, respectively. The parameters are k=4, Minter=N1, and for simulation results we chose the size of modules to be N1=N2=108, Minter=N2=N1 and averaged over 1,000 realizations. The slopes of red dashed lines are equal to −γ. Similar results for different parameters are given in SI Appendix, Fig. S4.

Fig. 3.
Fig. 3.

The size of the giant component S(r,p) in SF networks as a function of p for different r. (A–C) λ=4.5 with r=0.0001 (blue), r=0.0005 (green), and r=0.001 (orange) (A); λ=3.35 for which pc≈0.149 with r=0.0001 (blue), r=0.0005 (green), and r=0.001 (orange) (B); and λ=2.8 with r=0.0005 (blue), r=0.0007 (green), and r=0.001 (orange) (C). Lines and symbols denote analytical and simulation results, respectively, in which a red line denotes a single SF network. (D) S(r,pc) as a function of r for different λ. Numerical and simulation results are denoted by circles and squares, respectively. The simulation results were averaged over 1,000 realizations with kmin=2, kmax=106, N1=N2=108, and Minter=N1.

We now investigate the scaling relations and critical exponents of our model, with S(r,p), p, and r, serving as the analogues of magnetization, temperature, and external field, respectively. To quantify how the external field affects the percolation phase transition, we define the critical exponent δ that relates the order parameter at the critical point to the magnitude of the field,S(r,pc)∼r1/δ,[4]and γ, which describes the susceptibility near criticality,∂S(r,p)∂rr→0∼p−pc−γ.[5]We first measure δ. For ER modules, we obtain δ=2 from both theory and simulations (Fig. 2B), which is the same as the known value for mean-field random percolation (51). For SF modules, we find that the value of δ varies with λ as shown in Fig. 3D. When λ>4 the critical exponents are the expected mean-field values for regular percolation in infinite dimensions, and the universality class is the same as ER modules (55). When 2<λ<3, SF networks undergo a transition for p→0, and the critical exponents depend on λ. When 3<λ<4, it is known that pc>0, and the critical exponents vary with λ (55). We find analytically and via simulations that δ changes with λ, i.e., δ=1.28 for λ=3.35 and δ=1.06 for λ=2.8.

We next examine the analogue of magnetic susceptibility, which has the scaling relation Eq. 5. Fig. 2C presents the analytical (Left) and simulation (Right) results. For ER modules, we find γ=1 for both p<pc and p>pc (see SI Appendix, Fig. S3A for details). We find in both simulations and theory that in SF modules, γ depends on λ, with γ=1 for λ=4.5, γ=0.8 for λ=3.35, and γ=0.3 for λ=2.8, as shown in Fig. 4.

Fig. 4.
Fig. 4.

∂S(r,p)∂r as a function of pc−p with r=0.0001 for λ=4.5, r=0.0001 for λ=3.35, and r=0.0005 for λ=2.8, Left and Right show numerical and simulation results. The slopes of red dashed lines are equal to −γ. The simulation results were averaged over 1,000 realizations with kmin=2, kmax=106, N1=N2=108, and Minter=N1.

In testing the scaling relations between the exponents, we find that in a single network (m=1), the order parameter follows S∼(p−pc)β in the critical region with β=1 for ER networks. In SF networks, we find that β=1 for λ>4, β=1/(λ−3) for 3<λ<4, and β=1/(3−λ) for 2<λ<3 (55). These values for β and the δ and γ values found above fulfill the well-known universal scaling relation in physical phase transitions (51).

The universality class of a system’s phase transition is characterized by a set of critical exponents. Because the thermodynamic quantities are related, these critical exponents are not independent and can be expressed in terms of only two exponents (14, 51, 56). We find that this universal scaling hypothesis is also valid for our community model, both in ER and SF modules, based on the above values found for β,δ and γ. Specifically, note that our values for these exponents are consistent with Widom’s identity δ−1=γ/β (14).

We now test our framework on two real-world examples, (i) the coauthor collaboration network (dblp) (57, 58) and (ii) the coauthorship MathSciNet (58⇓–60) network built from the mathematical review collection of the American Mathematical Society (for details, see Data and Methods). We use a greedy algorithm to detect the community structure (61) and keep the largest two communities with the same parameter λ (the degree distribution for each community is given in SI Appendix, Fig. S7). Fig. 5 shows the numerical results for modules of real networks with λ=2.8,3.35, respectively. We find that the values of critical exponents δ and γ for the real networks are also consistent with theoretical results. One should note that pc of each of the real modules are not identical, i.e., each real module has a different value of pc (for r=0), as shown in SI Appendix.

Fig. 5.
Fig. 5.

Critical scaling and exponents for two modules in each of two real-world networks with λ=2.8, Minter=4×105 (A and B) and λ=3.35, Minter=5×105 (C and D). (A and B) ∂S(r,p)∂r as a function of pc−p (A) and S(r,pc) as a function of r (B) for the coauthor dblp collaboration network. (C and D) ∂S(r,p)∂r as a function of pc−p (C) and S(r,pc) as a function of r (D) for the coauthor MathSciNet collaboration network. The slopes of red dashed lines are equal to −γ. The parameters of each community and network are summarized in SI Appendix. We average over 2,000 realizations for each network.

Discussion

We have introduced a network model of community structure and have shown that the fraction of nodes with interconnections is analogous to an external field in a physical phase transition. We solve the resilience of this system both numerically and analytically with excellent agreement. Our results show that a system becomes more stable and resilient as the fraction of nodes with interconnections increases. In particular, we find that by defining critical exponents δ and γ based on S, p, and r, the scaling relations governing the external field are analogues to macroscopic magnetization, temperature, and the external field, respectively, near criticality. The values of the critical exponents are equivalent to high-dimensional values of the magnetization transition in infinite dimensions for communities with a degree distribution that is Poisson or SF with λ>4. For SF degree distributions and λ<4, we find that δ and γ depend on λ. Furthermore, we find that these critical exponents obey the universal scaling relations of physical systems near a phase transition. We also find similar results for real social networks.

Our findings not only offer guidance on designing robust systems, but also make predictions about the nature of system failures. Our theory and model provide understanding of how to make the network more resilient by increasing the number of interconnected nodes as well as predicting its robustness.

In addition, we have extended percolation theory on networks by defining the critical exponents for an external field. Our goal is to inspire further theoretical analysis and to identify additional system properties that are analogous to external fields. Although our theory is applied here to study the resilience of modules within a single network, it can be extended to study resilience of interdependent networks and multiplex networks.

Data and Methods

We apply the external field model on two real collaboration networks: (i) the coauthor collaboration network (DBLP) (57, 58) and (ii) the coauthorship MathSciNet network of mathematical review collections of the American Mathematical Society (58⇓–60). In both networks, nodes are authors, and an undirected edge between two authors exists if they have published at least one paper together. The community structure of the networks is detected by using a fast greedy algorithm (61). General information and statistical features of these networks are summarized in SI Appendix, Table S1. To analyze the external field effects in real networks with finite sizes, we choose the largest two modules with the same scaling exponents and add nonduplicate interconnected links randomly among a fraction r of nodes in both modules. The critical exponents of the external field for different λ are analyzed in the critical region, as shown in Fig. 5. And the values of pc are determined by Scutoff=0.0001 (the critical relationships for different Scutoff are shown in SI Appendix), where S is smaller than or equal to Scutoff for each individual module.

Acknowledgments

We thank Dr. Lucas Daniel Valdez for useful discussions. The Boston University Center for Polymer Studies is supported by NSF Grants PHY-1505000, CMMI-1125290, and CHE-1213217; and by Defense Threat Reduction Agency Grant HDTRA1-14-1-0017. We acknowledge the Israel–Italian collaborative project Network Aware Cyber Security (NECST); the Israel Science Foundation; Major Program of National Natural Science Foundation of China Grants 71690242 and 91546118; the Office of Naval Research; the Japan Science Foundation; and US–Israel Binational Science Foundation–NSF. This work was partially supported by National Natural Science Foundation of China Grants 61403171, 71403105, 2015M581738, and 1501100B; and Key Research Program of Frontier Sciences, Chinese Academy of Sciences Grant QYZDJ-SSW-SYS019. J.F. thanks the fellowship program funded by the Planning and Budgeting Committee of the Council for Higher Education of Israel.

Footnotes

  • ↵1G.D., J.F., L.M.S., and S.S. contributed equally to this work.

  • ↵2To whom correspondence may be addressed. Email: hes{at}bu.edu or tianlixin{at}njnu.edu.cn.

  • Author contributions: G.D., J.F., L.M.S., S.S., R.D., L.T., X.C., H.E.S., and S.H. designed research; G.D., J.F., and L.M.S. performed research; G.D., J.F., L.M.S., S.S., R.D., L.T., X.C., H.E.S., and S.H. analyzed data; and G.D., J.F., L.M.S., S.S., R.D., L.T., X.C., H.E.S., and S.H. wrote the paper.

  • Reviewers: A.C., Napoli University Federico II; and I.M.S., Humboldt University.

  • The authors declare no conflict of interest.

  • This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1801588115/-/DCSupplemental.

Published under the PNAS license.

View Abstract
Back to top
Article Alerts
Email Article
Citation Tools
Request Permissions
Resilience of networks with community structure behaves as if under an external field
Gaogao Dong, Jingfang Fan, Louis M. Shekhtman, Saray Shai, Ruijin Du, Lixin Tian, Xiaosong Chen, H. Eugene Stanley, Shlomo Havlin
Proceedings of the National Academy of Sciences Jul 2018, 115 (27) 6911-6915; DOI: 10.1073/pnas.1801588115
Digg logo Reddit logo Twitter logo Facebook logo Google logo Mendeley logo
Proceedings of the National Academy of Sciences: 115 (27)
Table of Contents

Submit

Article Classifications

Jump to section

You May Also be Interested in

Large piece of gold
News Feature: Tracing gold's cosmic origins
Astronomers thought they’d finally figured out where gold and other heavy elements in the universe came from. In light of recent results, they’re not so sure.
Image credit: Science Source/Tom McHugh.

Similar Articles