Global cascades model

Last updated

Global cascades models are a class of models aiming to model large and rare cascades that are triggered by exogenous perturbations which are relatively small compared with the size of the system. The phenomenon occurs ubiquitously in various systems, like information cascades in social systems, stock market crashes in economic systems, and cascading failure in physics infrastructure networks. The models capture some essential properties of such phenomenon.

Contents

Model description

To describe and understand global cascades, a network-based threshold model has been proposed by Duncan J. Watts in 2002. [1] The model is motivated by considering a population of individuals who must make a decision between two alternatives, and their choices depend explicitly on other people's states or choices. The model assumes that an individual will adopt a new particular opinion (product or state) if a threshold fraction of his/her neighbors have adopted the new one, else he would keep his original state. To initiate the model, a new opinion will be randomly distributed among a small fraction of individuals in the network. If the fraction satisfies a particular condition, a large cascades can be triggered.(see Global Cascades Condition) A phase transition phenomenon has been observed: when the network of interpersonal influences is sparse, the size of the cascades exhibits a power law distribution, the most highly connected nodes are critical in triggering cascades, and if the network is relatively dense, the distribution shows a bimodal form, in which nodes with average degree show more importance by serving as triggers.

Several generalizations of the Watt's threshold model have been proposed and analyzed in the following years. For example, the original model has been combined with independent interaction models to provide a generalized model of social contagion, which classifies the behavior of the system into three universal classes. [2] It has also been generalized on modular networks [3] degree-correlated networks [4] and to networks with tunable clustering. [5] The role of the initiators has also been studied recently, shows that different initiator would influence the size of the cascades. [6] Watt's threshold model is one of the few models that shows qualitative differences on multiplex networks and single layer networks. [7] It can furthermore exhibit broad and multi-modal cascade size distributions on finite networks. [8]

Global cascades condition

To derive the precise cascade condition in the original model, a generating function method could be applied. [1] The generating function for vulnerable nodes in the network is:

where pk is the probability a node has degree k, and

and f is the distribution of the threshold fraction of individuals. The average vulnerable cluster size can be derived as:

where z is the average degree of the network. The Global cascades occur when the average vulnerable cluster size ⟨n⟩ diverges [1]

The equation could be interpreted as: When , the clusters in the network is small and global cascades will not happen since the early adopters are isolated in the system, thus no enough momentum could be generated. When , the typical size of the vulnerable cluster is infinite, which implies presence of global cascades.

Relations with other contagion models

The Model considers a change of state of individuals in different systems which belongs to a larger class of contagion problems. However it differs with other models in several aspects: Compared with 1) epidemic model: where contagion events between individual pairs are independent, the effect a single infected node having on an individual depends on the individual's other neighbors in the proposed model. Unlike 2) percolation or self-organized criticality models, the threshold is not expressed as the absolute number of "infected" neighbors around an individual, instead, a corresponding fraction of neighbors is selected. It is also different from 3) random-field ising model and majority voter model, which are frequently analyzed on regular lattices, here, however the heterogeneity of the network plays a significant role.

See also

Related Research Articles

Percolation theory Mathematical theory on behavior of connected clusters in a random graph

In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected clusters merge into significantly larger connected, so-called spanning cluster. The applications of percolation theory to materials science and in many other disciplines are discussed here and in the articles network theory and percolation.

Scale-free network Network whose degree distribution follows a power law

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as

Network theory Study of graphs as a representation of relations between discrete objects

Network theory is the study of graphs as a representation of either symmetric relations or asymmetric relations between discrete objects. In computer science and network science, network theory is a part of graph theory: a network can be defined as a graph in which nodes and/or edges have attributes.

Small-world network Mathematical graph where most nodes can be reached by a small number of steps

A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other and most nodes can be reached from every other node by a small number of hops or steps. Specifically, a small-world network is defined to be a network where the typical distance L between two randomly chosen nodes grows proportionally to the logarithm of the number of nodes N in the network, that is:

In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties; this likelihood tends to be greater than the average probability of a tie randomly established between two nodes.

Complex network Network with non-trivial topological features

In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real systems. The study of complex networks is a young and active area of scientific research inspired largely by empirical findings of real-world networks such as computer networks, biological networks, technological networks, brain networks, climate networks and social networks.

In network theory, a giant component is a connected component of a given random graph that contains a finite fraction of the entire graph's vertices.

Barabási–Albert model

The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the world wide web, citation networks, and some social networks are thought to be approximately scale-free and certainly contain few nodes with unusually high degree as compared to the other nodes of the network. The BA model tries to explain the existence of such nodes in real networks. The algorithm is named for its inventors Albert-László Barabási and Réka Albert and is a special case of an earlier and more general model called Price's model.

Community structure

In the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into sets of nodes such that each set of nodes is densely connected internally. In the particular case of non-overlapping community finding, this implies that the network divides naturally into groups of nodes with dense connections internally and sparser connections between groups. But overlapping communities are also allowed. The more general definition is based on the principle that pairs of nodes are more likely to be connected if they are both members of the same community(ies), and less likely to be connected if they do not share communities. A related but different problem is community search, where the goal is to find a community that a certain vertex belongs to.

In complex network theory, the fitness model is a model of the evolution of a network: how the links between nodes change over time depends on the fitness of nodes. Fitter nodes attract more links at the expense of less fit nodes.

Erdős–Rényi model Two closely related models for generating random graphs

In the mathematical field of graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs or the evolution of a random network. They are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who first introduced one of the models in 1959, while Edgar Gilbert introduced the other model contemporaneously and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely; in the model introduced by Gilbert, also called the Erdős–Rényi–Gilbert model, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

The percolation threshold is a mathematical concept in percolation theory that describes the formation of long-range connectivity in random systems. Below the threshold a giant connected component does not exist; while above it, there exists a giant component of the order of system size. In engineering and coffee making, percolation represents the flow of fluids through porous media, but in the mathematics and physics worlds it generally refers to simplified lattice models of random systems or networks (graphs), and the nature of the connectivity in them. The percolation threshold is the critical value of the occupation probability p, or more generally a critical surface for a group of parameters p1, p2, ..., such that infinite connectivity (percolation) first occurs.

Network science

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

Modularity (networks) Measure of network community structure

Modularity is a measure of the structure of networks or graphs which measures the strength of division of a network into modules. Networks with high modularity have dense connections between the nodes within modules but sparse connections between nodes in different modules. Modularity is often used in optimization methods for detecting community structure in networks. However, it has been shown that modularity suffers a resolution limit and, therefore, it is unable to detect small communities. Biological networks, including animal brains, exhibit a high degree of modularity.

The clique percolation method is a popular approach for analyzing the overlapping community structure of networks. The term network community has no widely accepted unique definition and it is usually defined as a group of nodes that are more densely connected to each other than to other nodes in the network. There are numerous alternative methods for detecting communities in networks, for example, the Girvan–Newman algorithm, hierarchical clustering and modularity maximization.

In the context of the physical and mathematical theory of percolation, a percolation transition is characterized by a set of universal critical exponents, which describe the fractal properties of the percolating medium at large scales and sufficiently close to the transition. The exponents are universal in the sense that they only depend on the type of percolation model and on the space dimension. They are expected to not depend on microscopic details such as the lattice structure, or whether site or bond percolation is considered. This article deals with the critical exponents of random percolation.

Hierarchical network model

Hierarchical network models are iterative algorithms for creating networks which are able to reproduce the unique properties of the scale-free topology and the high clustering of the nodes at the same time. These characteristics are widely observed in nature, from biology to language to some social networks.

Interdependent networks Subfield of network science

The study of interdependent networks is a subfield of network science dealing with phenomena caused by the interactions between complex networks. Though there may be a wide variety of interactions between networks, dependency focuses on the scenario in which the nodes in one network require support from nodes in another network. For an example of infrastructure dependency see Fig. 1.

In mathematical modeling of social networks, link-centric preferential attachment is a node's propensity to re-establish links to nodes it has previously been in contact with in time-varying networks. This preferential attachment model relies on nodes keeping memory of previous neighbors up to the current time.

Robustness, the ability to withstand failures and perturbations, is a critical attribute of many complex systems including complex networks.

References

  1. 1 2 3 Watts, D. J. (2002). "A simple model of global cascades on random networks". Proceedings of the National Academy of Sciences. 99 (9): 5766–5771. Bibcode:2002PNAS...99.5766W. doi: 10.1073/pnas.082090499 . PMC   122850 . PMID   16578874.
  2. ↑ Dodds, P.; Watts, D. (2004). "Universal Behavior in a Generalized Model of Contagion". Physical Review Letters. 92 (21): 218701. arXiv: cond-mat/0403699 . Bibcode:2004PhRvL..92u8701D. doi:10.1103/PhysRevLett.92.218701. PMID   15245323. S2CID   2450776.
  3. ↑ Gleeson, James.P (2008). "Cascades on correlated and modular random networks". Physical Review E. 77 (4): 046117. Bibcode:2008PhRvE..77d6117G. doi:10.1103/PhysRevE.77.046117. PMID   18517700.
  4. ↑ Dodds, Peter Sheridan; Payne, Joshua L. (2009). "Analysis of a threshold model of social contagion on degree-correlated networks". Physical Review E. 79 (6): 066115. arXiv: 0903.0597 . Bibcode:2009PhRvE..79f6115D. doi:10.1103/PhysRevE.79.066115. PMID   19658572. S2CID   14185789.
  5. ↑ Hackett, Adam; Melnik, Sergey; Gleeson, James.P (2011). "Cascades on a class of clustered random networks". Physical Review E. 83 (5): 056107. arXiv: 1012.3651 . Bibcode:2011PhRvE..83e6107H. doi:10.1103/PhysRevE.83.056107. PMID   21728605. S2CID   18071422.
  6. ↑ Singh, P.; Sreenivasan, S.; Szymanski, B.K; Korniss, G. (2013). "Threshold-limited spreading in social networks with multiple initiators". Scientific Reports. 387 (11): 2637–2652. Bibcode:2008PhyA..387.2637K. doi:10.1016/j.physa.2008.01.015.
  7. ↑ Burkholz, R.; Leduc, M. V.; Garas, A.; Schweitzer, F. (2016). "Systemic risk in multiplex networks with asymmetric coupling and threshold feedback". Physica D: Nonlinear Phenomena. 323–324: 64–72. arXiv: 1506.06664 . Bibcode:2016PhyD..323...64B. doi:10.1016/j.physd.2015.10.004. S2CID   53126169.
  8. ↑ Burkholz, R.; Herrmann, H. J.; Schweitzer, F. (2018). "Explicit size distributions of failure cascades redefine systemic risk on finite networks". Scientific Reports. 8 (1): 6878. arXiv: 1802.03286 . Bibcode:2018NatSR...8.6878B. doi:10.1038/s41598-018-25211-3. PMC   5932047 . PMID   29720624.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.