Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCoordination problems on networks revisited: statics and dynamics
72
0
0.0
(
0
)
Authors
Luca DallAsta
Ask ChatGPT about the research
No Arabic abstract
Simple binary-state coordination models are widely used to study collective socio-economic phenomena such as the spread of innovations or the adoption of products on social networks. The common trait of these systems is the occurrence of large-scale coordination events taking place abruptly, in the form of a cascade process, as a consequence of small perturbations of an apparently stable state. The conditions for the occurrence of cascade instabilities have been largely analysed in the literature, however for the same coordination models no sufficient attention was given to the relation between structural properties of (Nash) equilibria and possible outcomes of dynamical equilibrium selection. Using methods from the statistical physics of disordered systems, the present work investigates both analytically and numerically, the statistical properties of such Nash equilibria on networks, focusing mostly on random graphs. We provide an accurate description of these properties, which is then exploited to shed light on the mechanisms behind the onset of coordination/miscoordination on large networks. This is done studying the most common processes of dynamical equilibrium selection, such as best response, bounded-rational dynamics and learning processes. In particular, we show that well beyond the instability region, full coordination is still globally stochastically stable, however equilibrium selection processes with low stochasticity (e.g. best response) or strong memory effects (e.g. reinforcement learning) can be prevented from achieving full coordination by being trapped into a large (exponentially in number of agents) set of locally stable Nash equilibria at low/medium coordination (inefficient equilibria). These results should be useful to allow a better understanding of general coordination problems on complex networks.
rate research
Read More
A wide class of binary-state dynamics on networks---including, for example, the voter model, the Bass diffusion model, and threshold models---can be described in terms of transition rates (spin-flip probabilities) that depend on the number of nearest neighbors in each of the two possible states. High-accuracy approximations for the emergent dynamics of such models on uncorrelated, infinite networks are given by recently-developed compartmental models or approximate master equations (AME). Pair approximations (PA) and mean-field theories can be systematically derived from the AME. We show that PA and AME solutions can coincide under certain circumstances, and numerical simulations confirm that PA is highly accurate in these cases. For monotone dynamics (where transitions out of one nodal state are impossible, e.g., SI disease-spread or Bass diffusion), PA and AME give identical results for the fraction of nodes in the infected (active) state for all time, provided the rate of infection depends linearly on the number of infected neighbors. In the more general non-monotone case, we derive a condition---that proves equivalent to a detailed balance condition on the dynamics---for PA and AME solutions to coincide in the limit $t to infty$. This permits bifurcation analysis, yielding explicit expressions for the critical (ferromagnetic/paramagnetic transition) point of such dynamics, closely analogous to the critical temperature of the Ising spin model. Finally, the AME for threshold models of propagation is shown to reduce to just two differential equations, and to give excellent agreement with numerical simulations. As part of this work, Octave/Matlab code for implementing and solving the differential equation systems is made available for download.
Comparing with single networks, the multiplex networks bring two main effects on the spreading process among individuals. First, the pathogen or information can be transmitted to more individuals through different layers at one time, which enlarges the spreading scope. Second, through different layers, an individual can also transmit the pathogen or information to the same individuals more than once at one time, which makes the spreading more effective. To understand the different roles of the spreading scope and effectiveness, we propose an epidemic model on multiplex networks with link overlapping, where the spreading effectiveness of each interaction as well as the variety of channels (spreading scope) can be controlled by the number of overlapping links. We find that for Poisson degree distribution, increasing the epidemic scope (the first effect) is more efficient than enhancing epidemic probability (the second effect) to facilitate the spreading process. However, for power-law degree distribution, the effects of the two factors on the spreading dynamics become complicated. Enhancing epidemic probability makes pathogen or rumor easier to outbreak in a finite system. But after that increasing epidemic scopes is still more effective for a wide spreading. Theoretical results along with reasonable explanation for these phenomena are all given in this paper, which indicates that the epidemic scope could play an important role in the spreading dynamics.
We introduce the sandpile model on multiplex networks with more than one type of edge and investigate its scaling and dynamical behaviors. We find that the introduction of multiplexity does not alter the scaling behavior of avalanche dynamics; the system is critical with an asymptotic power-law avalanche size distribution with an exponent $tau = 3/2$ on duplex random networks. The detailed cascade dynamics, however, is affected by the multiplex coupling. For example, higher-degree nodes such as hubs in scale-free networks fail more often in the multiplex dynamics than in the simplex network counterpart in which different types of edges are simply aggregated. Our results suggest that multiplex modeling would be necessary in order to gain a better understanding of cascading failure phenomena of real-world multiplex complex systems, such as the global economic crisis.
For many complex networks present in nature only a single instance, usually of large size, is available. Any measurement made on this single instance cannot be repeated on different realizations. In order to detect significant patterns in a real--world network it is therefore crucial to compare the measured results with a null model counterpart. Here we focus on dense and weighted networks, proposing a suitable null model and studying the behaviour of the degree correlations as measured by the rich-club coefficient. Our method solves an existing problem with the randomization of dense unweighted graphs, and at the same time represents a generalization of the rich--club coefficient to weighted networks which is complementary to other recently proposed ones.
Extreme events are emergent phenomena in multi-particle transport processes on complex networks. In practice, such events could range from power blackouts to call drops in cellular networks to traffic congestion on roads. All the earlier studies of extreme events on complex networks have focused only on the nodal events. If random walks are used to model transport process on a network, it is known that degree of the nodes determines the extreme event properties. In contrast, in this work, it is shown that extreme events on the edges display a distinct set of properties from that of the nodes. It is analytically shown that the probability for the occurrence of extreme events on an edge is independent of the degree of the nodes linked by the edge and is dependent only on the total number of edges on the network and the number of walkers on it. Further, it is also demonstrated that non-trivial correlations can exist between the extreme events on the nodes and the edges. These results are in agreement with the numerical simulations on synthetic and real-life networks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
