Cascade dynamics on complex networks.

peer-reviewedThe network topologies on which many natural and synthetic systems are built provide ideal settings for the emergence of complex phenomena. One well-studied manifestation of this, called a cascade or avalanche, is observed when interactions between the components of a system allow an initially localized effect to propagate globally. For example, the malfunction of technological systems like email networks or electrical power grids is often attributable to a cascade of failures triggered by some isolated event. Similarly, the transmission of infectious diseases and the adoption of innovations or cultural fads may induce cascades among people in society. In recent years, it has been extensively demonstrated that the dynamics of cascades depends sensitively on the patterns of interaction laid out in the underlying network. One of the goals of network theory is to provide a solid theoretical basis for this dependence. In order to do this it is necessary, first, to construct network models that are both mathematically sound and capture the salient features of their real-world counterparts. So far, there has been limited success in this direction. The primary shortcoming of most existing network models in this regard is their lack of realistic structural motifs, in particular the absence of significant levels of clustering, which refers to the propensity of triples of connected vertices to form triangles, and is a prominent feature of networked systems across multiple settings. In this thesis we investigate the interplay between network structure and cascade dynamics. Beginning with dynamics, we consider an analytically tractable technique to determine the expected cascade size in a broad range of dynamical models on locally tree-like networks of arbitrary degree distribution. We validate this approach by demonstrating its excellent agreement with the results of extensive numerical simulations, and closely examine its applicability to real socio-technological systems. Here we focus particularly on problems relating to social influence and opinion formation, and we develop a number of important modifications of the basic theory. Following this, we turn our attention to the structural characterization of networks. We investigate the properties of a new generation of network models that incorporate clustering by embedding cliques of fully connected vertices within a locally tree-like topology, and that thus directly extend the classical configuration model construction. In one such model, devised by a member of our group, the sizes of these cliques may vary, allowing one to prescribe a clustering spectrum to match empirically measured values. Finally, we significantly extend the theory of dynamics on tree-like networks to these new, more structurally realistic ones. From this we uncover answers to some important questions, which have earned considerable recent attention, concerning the effects of increased clustering on cascades.SFI grant 06/IN.1/I366MACSI 06/MI/00