Message-passing approach for threshold models of behavior in networks

Dynamical phase transitions in graph cellular automata

Discrete dynamical systems can exhibit complex behavior from the iterative application of straightforward local rules. A famous class of examples comes from cellular automata whose global dynamics are notoriously challenging to analyze. To address this, we relax the regular connectivity grid of cellular automata to a random graph, which gives the class of graph cellular automata. Using the dynamical cavity method and its backtracking version, we show that this relaxation allows us to derive asymptotically exact analytical results on the global dynamics of these systems on sparse random graphs. Concretely, we showcase the results on a specific subclass of graph cellular automata with "conforming nonconformist" update rules, which exhibit dynamics akin to opinion formation. Such rules update a node's state according to the majority within their own neighborhood. In cases where the majority leads only by a small margin over the minority, nodes may exhibit nonconformist behavior. Instead of following the majority, they either maintain their own state, switch it, or follow the minority. For configurations with different initial biases towards one state we identify sharp dynamical phase transitions in terms of the convergence speed and attractor types. From the perspective of opinion dynamics this answers when consensus will emerge and when two opinions coexist almost indefinitely.

Aging in binary-state models: The Threshold model for complex contagion

We study the non-Markovian effects associated with aging for binary-state dynamics in complex networks. Aging is considered as the property of the agents to be less prone to change their state the longer they have been in the current state, which gives rise to heterogeneous activity patterns. In particular, we analyze aging in the Threshold model, which has been proposed to explain the process of adoption of new technologies. Our analytical approximations give a good description of extensive Monte Carlo simulations in Erdős-Rényi, random-regular and Barabási-Albert networks. While aging does not modify the cascade condition, it slows down the cascade dynamics towards the full-adoption state: the exponential increase of adopters in time from the original model is replaced by a stretched exponential or power law, depending on the aging mechanism. Under several approximations, we give analytical expressions for the cascade condition and for the exponents of the adopters' density growth laws. Beyond random networks, we also describe by Monte Carlo simulations the effects of aging for the Threshold model in a two-dimensional lattice.

Microscopic edge-based compartmental modeling method for analyzing the susceptible-infected-recovered epidemic spreading on networks

The edge-based compartmental modeling (EBCM) approach has been used widely to characterize the nonrecurrent epidemic spreading dynamics (e.g., the susceptible-infected-recovered model) in complex networks. By using the probability theory, we derived an individual-based formulation for this approach, which we herein refer to as the microscopic EBCM method. We found that both for small and large initial infection numbers, the epidemic evolution agreed well with the ensemble averages of our stochastic simulations on different complex networks. Moreover, we showed that the dynamical message passing model, the standard EBCM system, and the pair quenched mean-field equations can be deduced by our microscopic EBCM method. In addition, the microscopic EBCM method was used to analyze the effect of epidemic awareness on networks. Importantly, the simple EBCM model for exponential awareness was developed. Our method provides a way for handling nontrivial disease transmission processes with irreversible dynamics.

Simplicial SIRS epidemic models with nonlinear incidence rates

Mathematical epidemiology that describes the complex dynamics on social networks has become increasingly popular. However, a few methods have tackled the problem of coupling network topology with complex incidence mechanisms. Here, we propose a simplicial susceptible-infected-recovered-susceptible (SIRS) model to investigate the epidemic spreading via combining the network higher-order structure with a nonlinear incidence rate. A network-based social system is reshaped to a simplicial complex, in which the spreading or infection occurs with nonlinear reinforcement characterized by the simplex dimensions. Compared with the previous simplicial susceptible-infected-susceptible (SIS) models, the proposed SIRS model can not only capture the discontinuous transition and the bistability of a complex system but also capture the periodic phenomenon of epidemic outbreaks. More significantly, the two thresholds associated with the bistable region and the critical value of the reinforcement factor are derived. We further analyze the stability of equilibrium points of the proposed model and obtain the condition of existence of the bistable states and limit cycles. This work expands the simplicial SIS models to SIRS models and sheds light on a novel perspective of combining the higher-order structure of complex systems with nonlinear incidence rates.

Heterogeneous node responses to multi-type epidemics on networks

Having knowledge of the contact network over which an infection is spreading opens the possibility of making individualized predictions for the likelihood of different nodes to become infected. When multiple infective strains attempt to spread simultaneously we may further ask which strain, or strains, are most likely to infect a particular node. In this article we investigate the heterogeneity in likely outcomes for different nodes in two models of multi-type epidemic spreading processes. For models allowing co-infection we derive message-passing equations whose solution captures how the likelihood of a given node receiving a particular infection depends on both the position of the node in the network and the interaction between the infection types. For models of competing epidemics in which co-infection is impossible, a more complicated analysis leads to the simpler result that node vulnerability factorizes into a contribution from the network topology and a contribution from the infection parameters.

Impact of contact preference on social contagions on complex networks

Preferential contact process limited by contact capacity remarkably affects the spreading dynamics on complex networks, but the influence of this preferential contact in social contagions has not been fully explored. To this end, we propose a behavior spreading model based on the mechanism of preferential contact. The probability in the model that an adopted individual contacts and tries to transmit the behavioral information to one of his/her neighbors depends on the neighbor's degree. Besides, a preferential exponent determines the tendency to contact with either small-degree or large-degree nodes. We use a dynamic messaging method to describe this complex contagion process and verify that the method is accurate to predict the spreading dynamics by numerical simulations on strongly heterogeneous networks. We find that the preferential contact mechanism leads to a crossover phenomenon in the growth of final adoption size. By reducing the preferential exponent, we observe a change from a continuous growth to an explosive growth and then to a continuous growth with the transmission rate of behavioral information. Moreover, we find that there is an optimal preferential exponent which maximizes the final adoption size at a fixed information transmission rate, and this optimal preferential exponent decreases with the information transmission rate. The used theory can be extended to other types of dynamics, and our findings provide useful and general insights into social contagion processes in the real world.

Reversible bootstrap percolation: Fake news and fact checking

Bootstrap percolation has been used to describe opinion formation in society and other social and natural phenomena. The formal equation of the bootstrap percolation may have more than one solution, corresponding to several stable fixed points of the corresponding iteration process. We construct a reversible bootstrap percolation process, which converges to these extra solutions displaying a hysteresis typical of discontinuous phase transitions. This process provides a reasonable model for fake news spreading and the effectiveness of fact checking. We show that sometimes it is not sufficient to discard all the sources of fake news in order to reverse the belief of a population that formed under the influence of these sources.

Predicting the Speed of Epidemics Spreading in Networks

Global transport and communication networks enable information, ideas, and infectious diseases to now spread at speeds far beyond what has historically been possible. To effectively monitor, design, or intervene in such epidemic-like processes, there is a need to predict the speed of a particular contagion in a particular network, and to distinguish between nodes that are more likely to become infected sooner or later during an outbreak. Here, we study these quantities using a message-passing approach to derive simple and effective predictions that are validated against epidemic simulations on a variety of real-world networks with good agreement. In addition to individualized predictions for different nodes, we find an overall sudden transition from low density to almost full network saturation as the contagion progresses in time. Our theory is developed and explained in the setting of simple contagions on treelike networks, but we are also able to show how the method extends remarkably well to complex contagions and highly clustered networks.

Exact analytical solution of irreversible binary dynamics on networks

In binary cascade dynamics, the nodes of a graph are in one of two possible states (inactive, active), and nodes in the inactive state make an irreversible transition to the active state, as soon as their precursors satisfy a predetermined condition. We introduce a set of recursive equations to compute the probability of reaching any final state, given an initial state, and a specification of the transition probability function of each node. Because the naive recursive approach for solving these equations takes factorial time in the number of nodes, we also introduce an accelerated algorithm, built around a breath-first search procedure. This algorithm solves the equations as efficiently as possible in exponential time.

Complex contagions with timers

There has been a great deal of effort to try to model social influence-including the spread of behavior, norms, and ideas-on networks. Most models of social influence tend to assume that individuals react to changes in the states of their neighbors without any time delay, but this is often not true in social contexts, where (for various reasons) different agents can have different response times. To examine such situations, we introduce the idea of a timer into threshold models of social influence. The presence of timers on nodes delays adoptions-i.e., changes of state-by the agents, which in turn delays the adoptions of their neighbors. With a homogeneously-distributed timer, in which all nodes have the same amount of delay, the adoption order of nodes remains the same. However, heterogeneously-distributed timers can change the adoption order of nodes and hence the "adoption paths" through which state changes spread in a network. Using a threshold model of social contagions, we illustrate that heterogeneous timers can either accelerate or decelerate the spread of adoptions compared to an analogous situation with homogeneous timers, and we investigate the relationship of such acceleration or deceleration with respect to the timer distribution and network structure. We derive an analytical approximation for the temporal evolution of the fraction of adopters by modifying a pair approximation for the Watts threshold model, and we find good agreement with numerical simulations. We also examine our new timer model on networks constructed from empirical data.

Matrix product algorithm for stochastic dynamics on networks applied to nonequilibrium Glauber dynamics

We introduce and apply an efficient method for the precise simulation of stochastic dynamical processes on locally treelike graphs. Networks with cycles are treated in the framework of the cavity method. Such models correspond, for example, to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, our approach is based on a matrix product approximation of the so-called edge messages-conditional probabilities of vertex variable trajectories. Computation costs and accuracy can be tuned by controlling the matrix dimensions of the matrix product edge messages (MPEM) in truncations. In contrast to Monte Carlo simulations, the algorithm has a better error scaling and works for both single instances as well as the thermodynamic limit. We employ it to examine prototypical nonequilibrium Glauber dynamics in the kinetic Ising model. Because of the absence of cancellation effects, observables with small expectation values can be evaluated accurately, allowing for the study of decay processes and temporal correlations.

Optimal deployment of resources for maximizing impact in spreading processes

The effective use of limited resources for controlling spreading processes on networks is of prime significance in diverse contexts, ranging from the identification of "influential spreaders" for maximizing information dissemination and targeted interventions in regulatory networks, to the development of mitigation policies for infectious diseases and financial contagion in economic systems. Solutions for these optimization tasks that are based purely on topological arguments are not fully satisfactory; in realistic settings, the problem is often characterized by heterogeneous interactions and requires interventions in a dynamic fashion over a finite time window via a restricted set of controllable nodes. The optimal distribution of available resources hence results from an interplay between network topology and spreading dynamics. We show how these problems can be addressed as particular instances of a universal analytical framework based on a scalable dynamic message-passing approach and demonstrate the efficacy of the method on a variety of real-world examples.

Exotic phase transitions of k-cores in clustered networks

The giant k-core-maximal connected subgraph of a network where each node has at least k neighbors-is important in the study of phase transitions and in applications of network theory. Unlike Erdős-Rényi graphs and other random networks where k-cores emerge discontinuously for k≥3, we show that transitive linking (or triadic closure) leads to 3-cores emerging through single or double phase transitions of both discontinuous and continuous nature. We also develop a k-core calculation that includes clustering and provides insights into how high-level connectivity emerges.

Bootstrap percolation on spatial networks

Bootstrap percolation is a general representation of some networked activation process, which has found applications in explaining many important social phenomena, such as the propagation of information. Inspired by some recent findings on spatial structure of online social networks, here we study bootstrap percolation on undirected spatial networks, with the probability density function of long-range links' lengths being a power law with tunable exponent. Setting the size of the giant active component as the order parameter, we find a parameter-dependent critical value for the power-law exponent, above which there is a double phase transition, mixed of a second-order phase transition and a hybrid phase transition with two varying critical points, otherwise there is only a second-order phase transition. We further find a parameter-independent critical value around -1, about which the two critical points for the double phase transition are almost constant. To our surprise, this critical value -1 is just equal or very close to the values of many real online social networks, including LiveJournal, HP Labs email network, Belgian mobile phone network, etc. This work helps us in better understanding the self-organization of spatial structure of online social networks, in terms of the effective function for information spreading.

Message-passing approach for recurrent-state epidemic models on networks

Epidemic processes are common out-of-equilibrium phenomena of broad interdisciplinary interest. Recently, dynamic message-passing (DMP) has been proposed as an efficient algorithm for simulating epidemic models on networks, and in particular for estimating the probability that a given node will become infectious at a particular time. To date, DMP has been applied exclusively to models with one-way state changes, as opposed to models like SIS and SIRS where nodes can return to previously inhabited states. Because many real-world epidemics can exhibit such recurrent dynamics, we propose a DMP algorithm for complex, recurrent epidemic models on networks. Our approach takes correlations between neighboring nodes into account while preventing causal signals from backtracking to their immediate source, and thus avoids "echo chamber effects" where a pair of adjacent nodes each amplify the probability that the other is infectious. We demonstrate that this approach well approximates results obtained from Monte Carlo simulation and that its accuracy is often superior to the pair approximation (which also takes second-order correlations into account). Moreover, our approach is more computationally efficient than the pair approximation, especially for complex epidemic models: the number of variables in our DMP approach grows as 2mk where m is the number of edges and k is the number of states, as opposed to mk^{2} for the pair approximation. We suspect that the resulting reduction in computational effort, as well as the conceptual simplicity of DMP, will make it a useful tool in epidemic modeling, especially for high-dimensional inference tasks.

Network cloning unfolds the effect of clustering on dynamical processes

We introduce network L-cloning, a technique for creating ensembles of random networks from any given real-world or artificial network. Each member of the ensemble is an L-cloned network constructed from L copies of the original network. The degree distribution of an L-cloned network and, more importantly, the degree-degree correlation between and beyond nearest neighbors are identical to those of the original network. The density of triangles in an L-cloned network, and hence its clustering coefficient, is reduced by a factor of L compared to those of the original network. Furthermore, the density of loops of any fixed length approaches zero for sufficiently large values of L. Other variants of L-cloning allow us to keep intact the short loops of certain lengths. As an application, we employ these network cloning methods to investigate the effect of short loops on dynamical processes running on networks and to inspect the accuracy of corresponding tree-based theories. We demonstrate that dynamics on L-cloned networks (with sufficiently large L) are accurately described by the so-called adjacency tree-based theories, examples of which include the message passing technique, some pair approximation methods, and the belief propagation algorithm used respectively to study bond percolation, SI epidemics, and the Ising model.

Dynamic message-passing equations for models with unidirectional dynamics

Understanding and quantifying the dynamics of disordered out-of-equilibrium models is an important problem in many branches of science. Using the dynamic cavity method on time trajectories, we construct a general procedure for deriving the dynamic message-passing equations for a large class of models with unidirectional dynamics, which includes the zero-temperature random-field Ising model, the susceptible-infected-recovered model, and rumor spreading models. We show that unidirectionality of the dynamics is the key ingredient that makes the problem solvable. These equations are applicable to single instances of the corresponding problems with arbitrary initial conditions and are asymptotically exact for problems defined on locally treelike graphs. When applied to real-world networks, they generically provide a good analytic approximation of the real dynamics.