Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMessage-Passing Methods for Complex Contagions
62
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Message-passing methods provide a powerful approach for calculating the expected size of cascades either on random networks (e.g., drawn from a configuration-model ensemble or its generalizations) asymptotically as the number $N$ of nodes becomes infinite or on specific finite-size networks. We review the message-passing approach and show how to derive it for configuration-model networks using the methods of (Dhar et al., 1997) and (Gleeson, 2008). Using this approach, we explain for such networks how to determine an analytical expression for a cascade condition, which determines whether a global cascade will occur. We extend this approach to the message-passing methods for specific finite-size networks (Shrestha and Moore, 2014; Lokhov et al., 2015), and we derive a generalized cascade condition. Throughout this chapter, we illustrate these ideas using the Watts threshold model.
rate research
Read More
Grouping objects into clusters based on similarities or weights between them is one of the most important problems in science and engineering. In this work, by extending message passing algorithms and spectral algorithms proposed for unweighted community detection problem, we develop a non-parametric method based on statistical physics, by mapping the problem to Potts model at the critical temperature of spin glass transition and applying belief propagation to solve the marginals corresponding to the Boltzmann distribution. Our algorithm is robust to over-fitting and gives a principled way to determine whether there are significant clusters in the data and how many clusters there are. We apply our method to different clustering tasks and use extensive numerical experiments to illustrate the advantage of our method over existing algorithms. In the community detection problem in weighted and directed networks, we show that our algorithm significantly outperforms existing algorithms. In the clustering problem when the data was generated by mixture models in the sparse regime we show that our method works to the theoretical limit of detectability and gives accuracy very close to that of the optimal Bayesian inference. In the semi-supervised clustering problem, our method only needs several labels to work perfectly in classic datasets. Finally, we further develop Thouless-Anderson-Palmer equations which reduce heavily the computation complexity in dense-networks but gives almost the same performance as belief propagation.
We investigate critical behaviors of a social contagion model on weighted networks. An edge-weight compartmental approach is applied to analyze the weighted social contagion on strongly heterogenous networks with skewed degree and weight distributions. We find that degree heterogeneity can not only alter the nature of contagion transition from discontinuous to continuous but also can enhance or hamper the size of adoption, depending on the unit transmission probability. We also show that, the heterogeneity of weight distribution always hinder social contagions, and does not alter the transition type.
The problem of targeted network immunization can be defined as the one of finding a subset of nodes in a network to immunize or vaccinate in order to minimize a tradeoff between the cost of vaccination and the final (stationary) expected infection under a given epidemic model. Although computing the expected infection is a hard computational problem, simple and efficient mean-field approximations have been put forward in the literature in recent years. The optimization problem can be recast into a constrained one in which the constraints enforce local mean-field equations describing the average stationary state of the epidemic process. For a wide class of epidemic models, including the susceptible-infected-removed and the susceptible-infected-susceptible models, we define a message-passing approach to network immunization that allows us to study the statistical properties of epidemic outbreaks in the presence of immunized nodes as well as to find (nearly) optimal immunization sets for a given choice of parameters and costs. The algorithm scales linearly with the size of the graph and it can be made efficient even on large networks. We compare its performance with topologically based heuristics, greedy methods, and simulated annealing.
Individuals are always limited by some inelastic resources, such as time and energy, which restrict them to dedicate to social interaction and limit their contact capacity. Contact capacity plays an important role in dynamics of social contagions, which so far has eluded theoretical analysis. In this paper, we first propose a non-Markovian model to understand the effects of contact capacity on social contagions, in which each individual can only contact and transmit the information to a finite number of neighbors. We then develop a heterogeneous edge-based compartmental theory for this model, and a remarkable agreement with simulations is obtained. Through theory and simulations, we find that enlarging the contact capacity makes the network more fragile to behavior spreading. Interestingly, we find that both the continuous and discontinuous dependence of the final adoption size on the information transmission probability can arise. And there is a crossover phenomenon between the two types of dependence. More specifically, the crossover phenomenon can be induced by enlarging the contact capacity only when the degree exponent is above a critical degree exponent, while the the final behavior adoption size always grows continuously for any contact capacity when degree exponent is below the critical degree exponent.
We study secure message-passing in the presence of multiple adversaries in modular networks. We assume a dominant fraction of nodes in each module have the same vulnerability, i.e., the same entity spying on them. We find both analytically and via simulations that the links between the modules (interlinks) have effects analogous to a magnetic field in a spin system in that for any amount of interlinks the system no longer undergoes a phase transition. We then define the exponents $delta$, which relates the order parameter (the size of the giant secure component) at the critical point to the field strength (average number of interlinks per node), and $gamma$, which describes the susceptibility near criticality. These are found to be $delta=2$ and $gamma=1$ (with the scaling of the order parameter near the critical point given by $beta=1$). When two or more vulnerabilities are equally present in a module we find $delta=1$ and $gamma=0$ (with $betageq2$). Apart from defining a previously unidentified universality class, these exponents show that increasing connections between modules is more beneficial for security than increasing connections within modules. We also measure the correlation critical exponent $ u$, and the upper critical dimension $d_c$, finding that $ u d_c=3$ as for ordinary percolation, suggesting that for secure message-passing $d_c =6$. These results provide an interesting analogy between secure message-passing in modular networks and the physics of magnetic spin-systems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
