> home > Feature Articles
 
Statistical Physics of Real-world Complexity: Multiplex Networks and Beyond
Kwang-Il Goh
File 1 : Vol29_No1_Feature Articles-3.pdf (0 byte)

DOI: 10.22661/AAPPSBL.2019.29.1.15

Statistical Physics of Real-world Complexity:
Multiplex Networks and Beyond

KWANG-IL GOH
DEPARTMENT OF PHYSICS, KOREA UNIVERSITY, SEOUL 02841, KOREA
(DATED: DECEMBER 14, 2018)

ABSTRACT

An overview of recent developments in complex networks theory, termed multiplex network theory, is presented, focusing on work by the author's group. Multiplex network theory deals with multiplex networks composed of multiple interacting network layers. Studies have proven that the multiplexity has a broad impact on the structure and function of complex systems. Major problems in the field are surveyed and the challenges and future prospects will be proposed.

INTRODUCTION

At the brink of the 21st century, two seminal papers appeared [1, 2], transforming the scientific understanding of complex systems from a statistical physics perspective. The resulting discipline, now known as network science [3], has developed for the last twenty-or-so years to provide a new framework and toolkits, both conceptual and methodological, for complex systems research.

The basic rationale of the network science approach to complex system research is to focus on how the patterns of interactions between constituents of the system underlie the emergent large-scale structural and dynamical properties of the complex system. To this end, one may ignore the details of the constituents and their interactions in the particular complex system, leaving only its scaffold in the form of the set of nodes (constituents) and links (interactions) among them. In this way, the complex system is represented by a graph or network. This simplified approach helps identify the "universal" properties, stripped of compounding context-specific details, much in line with the statistical physics approach to phase transitions and critical phenomena. As such, numerous tools and concepts from statistical physics could be employed to form a theoretical framework, now known as complex network theory [4]. Moreover, it could furnish a versatile platform applicable to problems in academic fields across domains as diverse as natural, social, and information sciences, becoming a part of standard toolkits for multidisciplinary research [3].

As complex network theory matured during the last two decades, more sophisticated concepts and elaborate analytical tools have continually been developed. One of the most fast-developing of them is the so-called multiplex network or multilayer network theory [5-9]. This framework is motivated by the observations that many real-world complex systems ranging from living organisms to human society operate through the interplay between multiple network layers to fulfill their emergent function. In multiplex network theory, we model the complex system by a network in which the same set of nodes are connected via more than one type of link, each type of link forming the individual network layer (Fig. 1). Examples of multiplex networks abound, from human society networking through numerous social relationships to the critical infrastructure providing multiple essential resources through concerted operations of multiple interlinked and interrelated supply layers.

 



Fig. 1: An example of the multiplex network of nine nodes with two layers. Adapted from Ref. [8]

The introduction of manifold layers in multiplex networks necessitated new conceptual, as well as computational developments beyond the standard single-network theoretic framework that has been well-established during the last fifteen or so years [4]. In this feature article, I will present a brief overview of such developments, focusing on the works done by my group at Korea University for the last several years. This feature article is a condensed version of our previous review [8] amended by some newest developments. A reader with deeper interest is invited to the more detailed review published several years ago [8].

GROWING MULTIPLEX NETWORK MODEL

The layers coexisting in a multiplex system may also coevolve, in the sense that the evolution of one layer is dependent not only on the state of the current layer but also on those of other layers. This idea has been implemented using the preferential attachment scheme [10, 11].

In the coevolving multiplex network growth model, a node is newly added to the system in each step and connects to existing nodes following the growth kernel Π. The coevolution property is implemented in such a way that the growth kernel Πa of a node's degree in layer a depends not only on its degree in that layer but also its degrees in other layers,

(1)

where superscripted layer indices are used. A simple example for a two-layer network [Fig. 2(a)] is provided by growth kernels in the form of coupled linear preferential attachment, given by

(2)

where the constant ϵ is the so-called coevolution parameter and a is the constant determining the layer's native degree exponent.

 

Fig. 2: (a) Schematic illustration for the coevolution model. (b) Joint degree distribution P(kA, kB) for different values of the coevolution parameter ϵ. Adapted from Ref. [10].

The degree distribution of each layer is shown to be independent of the value of ϵ and becomes P(k) ~ k-(3+a) for both layers. However, the degree correlation between layers is strongly affected by the coevolution parameter ϵ [Fig. 2(b)], revealing that the interlayer degree correlation increases with increasing strength of coupling between the layers.

PERCOLATION

The percolation problem is a cornerstone of the statistical physics approach to complex network research. In this problem, one is primarily interested in the existence of the giant component, that is the extensive subset of nodes which are connected to one another. Different models of the percolation problem are defined by different notions of connectivity. For multiplex networks having more than one layer, two fundamentally different notions can be defined. One is generalized ordinary percolation, concerning the connectivity through links of any type (layers). The second one is the so-called mutual percolation, concerning the existence of the giant mutual component, a set of nodes connected in each and every layer separately and simultaneously. The former approach was initiated in [12], and the latter in [13].

Generalizing the generating-function-based or message-passing-type analytic frameworks as in [12, 14], one can study these percolation problems on multiplex networks with correlations between degrees of node across layers [16]. For example, the sizes of giant component S and giant bicomponent B of a multiplex network with l layers are given by

(3)

where G0(x) is the generating function of the joint degree distribution P(k) with k = {k1, k2, …, kl},
G
0(x)=∑k P(k) ∏la=1 and G1(a)(x) = G0(x). u = {u1, u2, …, ul} is the set of probabilities ua that a node reached by following a randomly chosen a-layer edge does not belong to the giant component, satisfying the coupled self-consistency equations,

(4)

As the mean degree z of the network layer increases, the percolation phase transition occurs at the critical mean degree zc. The condition for existence of the giant component S > 0 and that for the giant bicomponent B > 0 coincide and is that the largest eigenvalue of the Jacobian matrix J of Eq. (24) for the trivial solution u = {1, …, 1} be larger than unity [16]. Illustrative results for S and B for duplex ER networks with mean degree z in each layer are shown in Fig. 3(a). It can be seen that both percolation and biconnectivity transitions occur at z = 0 for the maximally-positive-correlated case, while for the maximally-negative-correlated case the transition is delayed to a higher value zc = 0.838587… than the uncorrelated case for which zc = 1/2.

 

Fig. 3: (a) Percolation and (b) mutual percolation results for duplex ER networks with interlayer degree correlations. (a) Sizes of the giant component S (solid lines) and the giant bicomponent B (dotted lines) for the MP (red), the uncorrelated (black), and the MN (blue) couplings of duplex ER networks. (b) Mutual component size M for the MP, uncorrelated, and MN couplings. Adapted from Refs. [16].

A similar procedure can be applied to the mutual percolation problem. The giant mutual component size M is given by

(5)

where wa denotes the probability that the node reached by following a randomly chosen a-layer edge does not belong to the giant mutual component, satisfying the coupled self-consistency equations,

(6)

Again illustrative results for duplex ER networks are shown in Fig. 3(b). Duplex ER networks of two layers of equal mean degree z undergoe a discontinuous transition from unpercolated (M = 0) to mutualpercolated phase (M > 0) at the critical layer mean degree zc = 2.455407…, which is significantly higher than that of ordinary (single-layer) percolation, zc (1) = 1, and the jump in the giant component size at the critical point Mc (2) = 0.511699… [13, 14]. This discontinuous mutual percolation transition is of the so-called hybrid type, showing a discontinuous jump in the order parameter followed by the critical scaling, M - Mc ~ (z - zc)β with β = 1/2, above the transition point. This unusual transition behavior is understood as the transition through the spinodal point. For correlated multiplex networks, the transition remains discontinuous.

 

Fig. 4: (a) Illustrations of the CA and the CD algorithms for viability. (b) Hysteresis curve of the viability V with ρ0 =0.02. The dashed line indicates the l = 1 case for comparison, without hysteresis. Adapted from Ref. [17].

Percolation is inherently a geometric problem but one can formulate the problem dynamically in terms of the percolation processes. Multiplex viability problem models percolation processes for the system's viability subject to multiple resource demand, each supplied through its own dedicated network layer [17]. Two percolation processes, called the cascade of activations (CA) and deactivations (CD), can be formulated by modeling the building up and sustaining viability, respectively [Fig. 4(a)]. The problem is found to be closely related to mutual percolation. It is found that the viability of a system depends also on the way it reached its current state, that is, whether one considers the CA or CD process [Fig. 4(b)]. In other words, the viability exhibits hysteresis-like behavior between two discontinuous transitions in the CA and CD processes.

MULTIPLEX CASCADE DYNAMICS

The multiplex structure of complex networks also underpins the patterns of dynamic processes in complex systems. As a case study, the threshold cascade model originally formulated by [18] has been generalized [19, 20] for multiplex networks, in which the social influences from different layers are integrated non-additively and nonlinearly. One is primarily interested in the global cascade size ρ, resulting from random-distributed initially-active seeds of fraction ρ0. It can be calculated as

(7)

where B(q) is shorthand notation for the binomial distribution, ()qm(1-q)k-m. The quantity {q} is the fix point of the coupled recursion relation,

(8)

starting from every q0(a) = p0. (m,k) is the response function encoding the activation rule, giving the probability that the node with m = {ma} active neighbors among its multiplex degree k will activate.

 

Fig. 5: (a) An example multiplex configuration illustrating the two response rules. Green (dark) circles denote active nodes and the light (white, orange) ones the inactive nodes. For R = 1/2, the orange node will activate itself under the OR rule, but will remain inactive under the AND rule. (b) The cascade size ρ as a function of z, for three different values of ε: 0.2 (green dotted), 0.5 (orange dashed), and 1.0 (red solid). Adapted from Ref. [20].

Two simple yet representative activation rules are considered as illustrated in Fig. 5(a): i) the OR rule, in which the node activates once the threshold is met in at least one layer, and ii) the AND rule, in which the node activates only after the threshold is met in all its social layers. For a population of a mixture of people following the AND- and OR-rule, as the fraction ε of nodes following the AND rule increases, there exists a critical fraction above which the transition to a global cascade becomes discontinuous, compared to the continuous transition below this fraction as showcased in Fig. 5(b).

This is an example in which the cooperative layer coupling driven by dynamics induces a discontinuous transition in multiplex systems. A discontinuous transition has recently been observed for the consensus transition in a multiplex majority-vote model with a strong conjunctive decision rule [21]. A multiplex cascading failure model has also been formulated as a model for crisis spreading in the multiplex global economic network [22].

EPIDEMIC SPREADING

Epidemic spreading is another classic topic of dynamical processes in networks. It models how the infectious entities spread over the network and the way in which the infection is transmitted to other nodes over the links defines a specific model. As the infection proceeds, it is not uncommon that agents in the network can be exposed to infectious entities through many different channels of interaction, which can have vastly different spatiotemporal characteristics. To handle such a scenario, the multiplex framework would not only be more straightforward conceptually but also more transparent methodologically than its single-layer counterpart.

 

Fig. 6: (a) Schematic illustration of the two-layer Twitter network over which the information spreading model with layer-switching cost is simulated. (b) Plots of the prevalence ρ on the Twitter network for various values of the cost parameter δλ. (inset) A close-up of the prevalence plot for the range of small λ (0 ≤ λ ≤ 0.5). Adapted from Ref. [23].

Consider for example the spreading of information over the Twitter network not only through retweet but also via reply as shown in Fig. 6(a). As information spreads across these layers, there exists an effective layerswitching cost, explicitly or implicitly due to the disparity of communication characteristics among different channels. In [23], an SIR-type model of information spreading incorporating such a layer-switching cost has been studied. In that model, the layer-switching cost generates a difference in the rates of across-the-layer and along-the-layer infections, leading to path-dependent transmissibility even for the same link. It was found that the layer-crossing overhead confers nontrivial effects on spreading dynamics, viz., the epidemic prevalence ρ measuring the degree of epidemic outbreak becomes dependent on the layer-switching cost as illustrated in Fig. 6(b). A novel analytical method tailored to deal with the path-dependent transmissibility had also to be developed [23]. In this sense, it can be said that even the simple contagion model (like classical SIR model) can turn out to be not so simple for multiplex networks.

CONCLUSION AND OUTLOOK

In this feature article, we have presented a condensed overview of recent developments in multiplex networks from the viewpoint of statistical physics. Various statistical physics problems on the structure and dynamics of multiplex networks ranging from percolation to cascade dynamics and epidemic spreading are showcased. Multiplex frameworks are not only useful but crucial in elevating the level of our understanding of complex systems. Novel phenomena unforeseen in a traditional single-layer framework can arise as a consequence of the coupling of network layers, especially when the layers are coupled in a cooperative or competitive manner, in which cases the multiplex is not reducible to an equivalent single-layer system. It remains to be seen what other exciting new physics can emerge in this field.

Acknowledgements: I would like to thank B. Min, K.-M. Lee, J. Y. Kim, C. D. Brummitt, J. Choi, S.-H. Gwak and all the current and former members of my group at Korea University for fruitful collaborations for the works outlined in this article.

References

[1] D. J. Watts, and S. H. Strogatz, Nature (London) 393, 440 (1998).
[2] A.-L. Barabási, and R. Albert, Science 286, 509 (1999).
[3] A.-L. Barabási, Network Science (Cambridge University Press, Cambridge, 2016).
[4] M. E. J. Newman, Networks (2nd Ed.) (Oxford University Press, 2018).
[5] G. D'Agostino and A. Scala (Eds.), Networks of networks: The last frontier of complexity (Springer, 2014).
[6] M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno and M. A. Porter, J. Compl. Netw. 2, 203 (2014).
[7] S. Boccaletti, G. Bianconi, R. Criado, C. I. del Genio, J. Gómez-Gardeñes, M. Romance, I. Sendiña-Nadal, Z. Wang, and M. Zanin, Phys. Rep. 544, 1 (2014).
[8] K.-M. Lee, B. Min, and K.-I. Goh, Eur. Phys. J. B 88, 48 (2015).
[9] G. Bianconi, Multilayer Networks (Cambridge University Press, 2018).
[10] J. Y. Kim and K.-I. Goh, Phys. Rev. Lett. 111, 058702 (2013).
[11] V. Nicosia, G. Bianconi, V. Latora, and M. Barthelemy, Phys. Rev. Lett. 111, 058701 (2013).
[12] E. A. Leicht, and R. M. D'Souza, arXiv:0907.0894v1.
[13] S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanely and S. Havlin, Nature 464, 1025 (2010).
[14] S.-W. Son, G. Bizhani, C. Christensen, P. Grassberger, M. Paczuski, EPL 97, 16006 (2012).
[15] K.-M. Lee, J. Y. Kim, W.-k. Cho, K.-I. Goh, and I.-M. Kim, New. J. Phys. 14, 033027 (2012).
[16] B. Min, S. D. Yi, K.-M. Lee, and K.-I. Goh, Phys. Rev. E 89, 042811 (2014).
[17] B. Min, and K.-I. Goh, Phys. Rev. E 89, 040802(R) (2014).
[18] D. J. Watts, Proc. Natl. Acad. Sci. USA 99, 5766 (2002).
[19] C. D. Brummit, K.-M. Lee, and K.-I. Goh, Phys. Rev. E 85, 045102(R) (2012).
[20] K.-M. Lee, C. D. Brummitt, and K.-I. Goh, Phys. Rev. E 90, 062816 (2014).
[21] J. Choi and K.-I. Goh, arXiv:1812.03488 (2018).
[22] K.-M. Lee and K.-I. Goh, Sci. Rep. 6, 26346 (2016).
[23] B. Min, S.-H. Gwak, N. Lee, and K.-I. Goh, Sci. Rep. 6, 21392 (2016).

 

Kwang-Il Goh is a professor of physics at Korea University. After receiving a PhD from Seoul National University, he worked at the University of Notre Dame and Dana-Farber Cancer Institute/Harvard Medical School, before joining Korea University in 2007. His research field is theoretical statistical physics.

 
AAPPS Bulletin        ISSN: 0218-2203
Copyright © 2018 Association of Asia Pacific Physical Societies. All Rights Reserved.
Hogil Kim Memorial Building #501 POSTECH, 67 Cheongam-ro, Nam-gu, Pohang-si, Gyeongsangbuk-do, 37673, Korea
Tel: +82-54-279-8663 Fax: +82-54-279-8679 e-mail: aapps@apctp.org