Comparison of voter and Glauber ordering dynamics on networks

Ordering dynamics of nonlinear voter models

We study the ordering dynamics of nonlinear voter models with multiple states, also providing a discussion of the two-state model. The rate with which an individual adopts an opinion scales as the qth power of the number of the individual's neighbors in that state. For q>1 the dynamics favor the opinion held by the most agents. The ordering to consensus is driven by deterministic drift, and noise plays only a minor role. For q<1 the dynamics favors minority opinions, and for multistate models the ordering proceeds through a noise-driven succession of metastable states. Unlike linear multistate systems, the nonlinear model cannot be reduced to an effective two-state model. We find that the average density of active interfaces in the model with multiple opinion states does not show a single exponential decay in time for q<1, again at variance with the linear model. This highlights the special character of the conventional (linear) voter model, in which deterministic drift is absent. As part of our analysis, we develop a pair approximation for the multistate model on graphs, valid for any positive real value of q, improving on previous approximations for nonlinear two-state voter models.

Evaluating potential effects of distress symptoms' interventions on suicidality: Analyses of in silico scenarios

BACKGROUND

Complexity science perspectives like the network approach to psychopathology have emerged as a prominent methodological toolkit to generate novel hypotheses on complex etiologies surrounding various mental health problems and inform intervention targets. Such approach may be pivotal in advancing early intervention of suicidality among the younger generation (10-35 year-olds), the increasing burden of which needs to be reversed within a limited window of opportunity to avoid massive long-term repercussions. However, the network approach currently lends limited insight into the potential extent of proposed intervention targets' effectiveness, particularly for target outcomes in comorbid conditions.

METHODS

This paper proposes an in silico (i.e., computer-simulated) intervention approach that maps symptoms' complex interactions onto dynamic processes and analyzes their evolution. The proposed methodology is applied to investigate potential effects of changes in 1968 community-dwelling individuals' distress symptoms on their suicidal ideation. Analyses on specific subgroups were conducted. Results were also compared with centrality indices employed in typical network analyses.

RESULTS

Findings concur with symptom networks' centrality indices in suggesting that timely deactivating hopelessness among distressed individuals may be instrumental in preventing distress to develop into suicidal ideation. Additionally, however, they depict nuances beyond those provided by centrality indices, e.g., among young adults, reducing nervousness and tension may have similar effectiveness as deactivating hopeless in reducing suicidal ideation.

LIMITATIONS

Caution is warranted when generalizing findings here to the general population.

CONCLUSION

The proposed methodology may help facilitate timely agenda-setting in population mental health measures, and may also be augmented for future co-creation projects.

Discord in the voter model for complex networks

Online social networks have become primary means of communication. As they often exhibit undesirable effects such as hostility, polarization, or echo chambers, it is crucial to develop analytical tools that help us better understand them. In this paper we are interested in the evolution of discord in social networks. Formally, we introduce a method to calculate the probability of discord between any two agents in the multistate voter model with and without zealots. Our work applies to any directed, weighted graph with any finite number of possible opinions, allows for various update rates across agents, and does not imply any approximation. Under certain topological conditions, the opinions are independent and the joint distribution can be decoupled. Otherwise, the evolution of discord probabilities is described by a linear system of ordinary differential equations. We prove the existence of a unique equilibrium solution, which can be computed via an iterative algorithm. The classical definition of active links density is generalized to take into account long-range, weighted interactions. We illustrate our findings on real-life and synthetic networks. In particular, we investigate the impact of clustering on discord and uncover a rich landscape of varied behaviors in polarized networks. This sheds lights on the evolution of discord between, and within, antagonistic communities.

Order-disorder transition in the zero-temperature Ising model on random graphs

The zero-temperature Ising model is known to reach a fully ordered ground state in sufficiently dense random graphs. In sparse random graphs, the dynamics gets absorbed in disordered local minima at magnetization close to zero. Here, we find that the nonequilibrium transition between the ordered and the disordered regime occurs at an average degree that slowly grows with the graph size. The system shows bistability: The distribution of the absolute magnetization in the reached absorbing state is bimodal, with peaks only at zero and unity. For a fixed system size, the average time to absorption behaves nonmonotonically as a function of average degree. The peak value of the average absorption time grows as a power law of the system size. These findings have relevance for community detection, opinion dynamics, and games on networks.

Nonequilibrium dynamics in a three-state opinion-formation model with stochastic extreme switches

We investigate the nonequilibrium dynamics of a three-state kinetic exchange model of opinion formation, where switches between extreme states are possible, depending on the value of a parameter q. The mean field dynamical equations are derived and analyzed for any q. The fate of the system under the evolutionary rules used in S. Biswas et al. [Physica A 391, 3257 (2012)0378-437110.1016/j.physa.2012.01.046] shows that it is dependent on the value of q and the initial state in general. For q=1, which allows the extreme switches maximally, a quasiconservation in the dynamics is obtained which renders it equivalent to the voter model. For general q values, a "frozen" disordered fixed point is obtained which acts as an attractor for all initially disordered states. For other initial states, the order parameter grows with time t as exp[α(q)t] where α=1-q/3-q for q≠1 and follows a power law behavior for q=1. Numerical simulations using a fully connected agent-based model provide additional results like the system size dependence of the exit probability and consensus times that further accentuate the different behavior of the model for q=1 and q≠1. The results are compared with the nonequilibrium phenomena in other well-known dynamical systems.

Local and global ordering dynamics in multistate voter models

We investigate the time evolution of the density of active links and of the entropy of the distribution of agents among opinions in multistate voter models with all-to-all interaction and on uncorrelated networks. Individual realizations undergo a sequence of eliminations of opinions until consensus is reached. After each elimination the population remains in a metastable state. The density of active links and the entropy in these states varies from realization to realization. Making some simple assumptions we are able to analytically calculate the average density of active links and the average entropy in each of these states. We also show that, averaged over realizations, the density of active links decays exponentially, with a timescale set by the size and geometry of the graph, but independent of the initial number of opinion states. The decay of the average entropy is exponential only at long times when there are at most two opinions left in the population. Finally, we show how metastable states comprising only a subset of opinions can be artificially engineered by introducing precisely one zealot in each of the prevailing opinions.

Finite-size effects on the convergence time in continuous-opinion dynamics

We study finite-size effects on the convergence time in a continuous-opinion dynamics model. In the model, each individual's opinion is represented by a real number on a finite interval, e.g., [0,1], and a uniformly randomly chosen individual updates its opinion by partially mimicking the opinion of a uniformly randomly chosen neighbor. We numerically find that the characteristic time to the convergence increases as the system size increases according to a particular functional form in the case of lattice networks. In contrast, unless the individuals perfectly copy the opinion of their neighbors in each opinion updating, the convergence time is approximately independent of the system size in the case of regular random graphs, uncorrelated scale-free networks, and complete graphs. We also provide a mean-field analysis of the model to understand the case of the complete graph.

Parity and time reversal elucidate both decision-making in empirical models and attractor scaling in critical Boolean networks

We present new applications of parity inversion and time reversal to the emergence of complex behavior from simple dynamical rules in stochastic discrete models. Our parity-based encoding of causal relationships and time-reversal construction efficiently reveal discrete analogs of stable and unstable manifolds. We demonstrate their predictive power by studying decision-making in systems biology and statistical physics models. These applications underpin a novel attractor identification algorithm implemented for Boolean networks under stochastic dynamics. Its speed enables resolving a long-standing open question of how attractor count in critical random Boolean networks scales with network size and whether the scaling matches biological observations. Via 80-fold improvement in probed network size (N = 16,384), we find the unexpectedly low scaling exponent of 0.12 ± 0.05, approximately one-tenth the analytical upper bound. We demonstrate a general principle: A system's relationship to its time reversal and state-space inversion constrains its repertoire of emergent behaviors.

Non-Markovian majority-vote model

Non-Markovian dynamics pervades human activity and social networks and it induces memory effects and burstiness in a wide range of processes including interevent time distributions, duration of interactions in temporal networks, and human mobility. Here, we propose a non-Markovian majority-vote model (NMMV) that introduces non-Markovian effects in the standard (Markovian) majority-vote model (SMV). The SMV model is one of the simplest two-state stochastic models for studying opinion dynamics, and displays a continuous order-disorder phase transition at a critical noise. In the NMMV model we assume that the probability that an agent changes state is not only dependent on the majority state of his neighbors but it also depends on his age, i.e., how long the agent has been in his current state. The NMMV model has two regimes: the aging regime implies that the probability that an agent changes state is decreasing with his age, while in the antiaging regime the probability that an agent changes state is increasing with his age. Interestingly, we find that the critical noise at which we observe the order-disorder phase transition is a nonmonotonic function of the rate β of the aging (antiaging) process. In particular the critical noise in the aging regime displays a maximum as a function of β while in the antiaging regime displays a minimum. This implies that the aging/antiaging dynamics can retard/anticipate the transition and that there is an optimal rate β for maximally perturbing the value of the critical noise. The analytical results obtained in the framework of the heterogeneous mean-field approach are validated by extensive numerical simulations on a large variety of network topologies.

Long route to consensus: Two-stage coarsening in a binary choice voting model

Formation of consensus, in binary yes-no type of voting, is a well-defined process. However, even in presence of clear incentives, the dynamics involved can be incredibly complex. Specifically, formations of large groups of similarly opinionated individuals could create a condition of "support-bubbles" or spontaneous polarization that renders consensus virtually unattainable (e.g., the question of the UK exiting the EU). There have been earlier attempts in capturing the dynamics of consensus formation in societies through simple Z_{2}-symmetric models hoping to capture the essential dynamics of average behavior of a large number of individuals in a statistical sense. However, in absence of external noise, they tend to reach a frozen state with fragmented and polarized states, i.e., two or more groups of similarly opinionated groups with frozen dynamics. Here we show in a kinetic exchange opinion model considered on L×L square lattices, that while such frozen states could be avoided, an exponentially slow approach to consensus is manifested. Specifically, the system could either reach consensus in a time that scales as L^{2} or a long-lived metastable state (termed a "domain-wall state") for which formation of consensus takes a time scaling as L^{3.6}. The latter behavior is comparable to some voterlike models with intermediate states studied previously. The late-time anomaly in the timescale is reflected in the persistence probability of the model. Finally, the interval of zero crossing of the average opinion, i.e., the time interval over which the average opinion does not change sign, is shown to follow a scale-free distribution, which is compared with that seen in the opinion surveys regarding Brexit and associated issues since the late 1970s. The issue of minority spreading is also addressed by calculating the exit probability.

Coupling of link- and node-ordering in the coevolving voter model

We consider the process of reaching the final state in the coevolving voter model. There is a coevolution of state dynamics, where a node can copy a state from a random neighbor with probabilty 1-p and link dynamics, where a node can rewire its link to another node of the same state with probability p. That exhibits an absorbing transition to a frozen phase above a critical value of rewiring probability. Our analytical and numerical studies show that in the active phase mean values of magnetization of nodes n and links m tend to the same value that depends on initial conditions. In a similar way mean degrees of spins up and spins down become equal. The system obeys a special statistical conservation law since a linear combination of both types magnetizations averaged over many realizations starting from the same initial conditions is a constant of motion: Λ≡(1-p)μm(t)+pn(t)=const., where μ is the mean node degree. The final mean magnetization of nodes and links in the active phase is proportional to Λ while the final density of active links is a square function of Λ. If the rewiring probability is above a critical value and the system separates into disconnected domains, then the values of nodes and links magnetizations are not the same and final mean degrees of spins up and spins down can be different.

Interactional dynamics of same-sex marriage legislation in the United States

Understanding how people form opinions and make decisions is a complex phenomenon that depends on both personal practices and interactions. Recent availability of real-world data has enabled quantitative analysis of opinion formation, which illuminates phenomena that impact physical and social sciences. Public policies exemplify complex opinion formation spanning individual and population scales, and a timely example is the legalization of same-sex marriage in the United States. Here, we seek to understand how this issue captures the relationship between state-laws and Senate representatives subject to geographical and ideological factors. Using distance-based correlations, we study how physical proximity and state-government ideology may be used to extract patterns in state-law adoption and senatorial support of same-sex marriage. Results demonstrate that proximal states have similar opinion dynamics in both state-laws and senators' opinions, and states with similar state-government ideology have analogous senators' opinions. Moreover, senators' opinions drive state-laws with a time lag. Thus, change in opinion not only results from negotiations among individuals, but also reflects inherent spatial and political similarities and temporal delays. We build a social impact model of state-law adoption in light of these results, which predicts the evolution of state-laws legalizing same-sex marriage over the last three decades.

Interacting opinion and disease dynamics in multiplex networks: Discontinuous phase transition and nonmonotonic consensus times

Opinion formation and disease spreading are among the most studied dynamical processes on complex networks. In real societies, it is expected that these two processes depend on and affect each other. However, little is known about the effects of opinion dynamics over disease dynamics and vice versa, since most studies treat them separately. In this work we study the dynamics of the voter model for opinion formation intertwined with that of the contact process for disease spreading, in a population of agents that interact via two types of connections, social and contact. These two interacting dynamics take place on two layers of networks, coupled through a fraction q of links present in both networks. The probability that an agent updates its state depends on both the opinion and disease states of the interacting partner. We find that the opinion dynamics has striking consequences on the statistical properties of disease spreading. The most important is that the smooth (continuous) transition from a healthy to an endemic phase observed in the contact process, as the infection probability increases beyond a threshold, becomes abrupt (discontinuous) in the two-layer system. Therefore, disregarding the effects of social dynamics on epidemics propagation may lead to a misestimation of the real magnitude of the spreading. Also, an endemic-healthy discontinuous transition is found when the coupling q overcomes a threshold value. Furthermore, we show that the disease dynamics delays the opinion consensus, leading to a consensus time that varies nonmonotonically with q in a large range of the model's parameters. A mean-field approach reveals that the coupled dynamics of opinions and disease can be approximately described by the dynamics of the voter model decoupled from that of the contact process, with effective probabilities of opinion and disease transmission.

Phase transitions in Ising models on directed networks

We examine Ising models with heat-bath dynamics on directed networks. Our simulations show that Ising models on directed triangular and simple cubic lattices undergo a phase transition that most likely belongs to the Ising universality class. On the directed square lattice the model remains paramagnetic at any positive temperature as already reported in some previous studies. We also examine random directed graphs and show that contrary to undirected ones, percolation of directed bonds does not guarantee ferromagnetic ordering. Only above a certain threshold can a random directed graph support finite-temperature ferromagnetic ordering. Such behavior is found also for out-homogeneous random graphs, but in this case the analysis of magnetic and percolative properties can be done exactly. Directed random graphs also differ from undirected ones with respect to zero-temperature freezing. Only at low connectivity do they remain trapped in a disordered configuration. Above a certain threshold, however, the zero-temperature dynamics quickly drives the model toward a broken symmetry (magnetized) state. Only above this threshold, which is almost twice as large as the percolation threshold, do we expect the Ising model to have a positive critical temperature. With a very good accuracy, the behavior on directed random graphs is reproduced within a certain approximate scheme.

Ising model in clustered scale-free networks

The Ising model in clustered scale-free networks has been studied by Monte Carlo simulations. These networks are characterized by a degree distribution of the form P(k)∼k(-γ) for large k. Clustering is introduced in the networks by inserting triangles, i.e., triads of connected nodes. The transition from a ferromagnetic (FM) to a paramagnetic (PM) phase has been studied as a function of the exponent γ and the triangle density. For γ>3 our results are in line with earlier simulations, and a phase transition appears at a temperature T(c)(γ) in the thermodynamic limit (system size N→∞). For γ≤3, a FM-PM crossover appears at a size-dependent temperature T(co), so the system remains in a FM state at any finite temperature in the limit N→∞. Thus, for γ=3, T(co) scales as lnN, whereas for γ<3, we find T(co)∼JN(z), where the exponent z decreases for increasing γ. Adding motifs (triangles in our case) to the networks causes an increase in the transition (or crossover) temperature for exponent γ>3 (or ≤3). For γ>3, this increase is due to changes in the mean values 〈k〉 and 〈k(2)〉, i.e., the transition is controlled by the degree distribution (nearest-neighbor connectivities). For γ≤3, however, we find that clustered and unclustered networks with the same size and distribution P(k) have different crossover temperature, i.e., clustering favors FM correlations, thus increasing the temperature T(co). The effect of a degree cutoff k(cut) on the asymptotic behavior of T(co) is discussed.

The structure and dynamics of multilayer networks

In the past years, network theory has successfully characterized the interaction among the constituents of a variety of complex systems, ranging from biological to technological, and social systems. However, up until recently, attention was almost exclusively given to networks in which all components were treated on equivalent footing, while neglecting all the extra information about the temporal- or context-related properties of the interactions under study. Only in the last years, taking advantage of the enhanced resolution in real data sets, network scientists have directed their interest to the multiplex character of real-world systems, and explicitly considered the time-varying and multilayer nature of networks. We offer here a comprehensive review on both structural and dynamical organization of graphs made of diverse relationships (layers) between its constituents, and cover several relevant issues, from a full redefinition of the basic structural measures, to understanding how the multilayer nature of the network affects processes and dynamics.

Opinion dynamics and influencing on random geometric graphs

We investigate the two-word Naming Game on two-dimensional random geometric graphs. Studying this model advances our understanding of the spatial distribution and propagation of opinions in social dynamics. A main feature of this model is the spontaneous emergence of spatial structures called opinion domains which are geographic regions with clear boundaries within which all individuals share the same opinion. We provide the mean-field equation for the underlying dynamics and discuss several properties of the equation such as the stationary solutions and two-time-scale separation. For the evolution of the opinion domains we find that the opinion domain boundary propagates at a speed proportional to its curvature. Finally we investigate the impact of committed agents on opinion domains and find the scaling of consensus time.

Networks maximizing the consensus time of voter models

We explore the networks that yield the largest mean consensus time of voter models under different update rules. By analytical and numerical means, we show that the so-called lollipop graph, barbell graph, and double-star graph maximize the mean consensus time under the update rules called the link dynamics, voter model, and invasion process, respectively. For each update rule, the largest mean consensus time scales as O(N^{3}), where N is the number of nodes in the network.

Fragmentation transition in a coevolving network with link-state dynamics

We study a network model that couples the dynamics of link states with the evolution of the network topology. The state of each link, either A or B, is updated according to the majority rule or zero-temperature Glauber dynamics, in which links adopt the state of the majority of their neighboring links in the network. Additionally, a link that is in a local minority is rewired to a randomly chosen node. While large systems evolving under the majority rule alone always fall into disordered topological traps composed by frustrated links, any amount of rewiring is able to drive the network to complete order, by relinking frustrated links and so releasing the system from traps. However, depending on the relative rate of the majority rule and the rewiring processes, the system evolves towards different ordered absorbing configurations: either a one-component network with all links in the same state or a network fragmented in two components with opposite states. For low rewiring rates and finite-size networks there is a domain of bistability between fragmented and nonfragmented final states. Finite-size scaling indicates that fragmentation is the only possible scenario for large systems and any nonzero rate of rewiring.

Evolutionary origin of asymptotically stable consensus

Consensus is widely observed in nature as well as in society. Up to now, many works have focused on what kind of (and how) isolated single structures lead to consensus, while the dynamics of consensus in interdependent populations remains unclear, although interactive structures are everywhere. For such consensus in interdependent populations, we refer that the fraction of population adopting a specified strategy is the same across different interactive structures. A two-strategy game as a conflict is adopted to explore how natural selection affects the consensus in such interdependent populations. It is shown that when selection is absent, all the consensus states are stable, but none are evolutionarily stable. In other words, the final consensus state can go back and forth from one to another. When selection is present, there is only a small number of stable consensus state which are evolutionarily stable. Our study highlights the importance of evolution on stabilizing consensus in interdependent populations.

Slow dynamics and rare-region effects in the contact process on weighted tree networks

We show that generic, slow dynamics can occur in the contact process on complex networks with a tree-like structure and a superimposed weight pattern, in the absence of additional (nontopological) sources of quenched disorder. The slow dynamics is induced by rare-region effects occurring on correlated subspaces of vertices connected by large weight edges and manifests in the form of a smeared phase transition. We conjecture that more sophisticated network motifs could be able to induce Griffiths phases, as a consequence of purely topological disorder.

Absorbing states of zero-temperature Glauber dynamics in random networks

We study zero-temperature Glauber dynamics for Ising-like spin variable models in quenched random networks with random zero-magnetization initial conditions. In particular, we focus on the absorbing states of finite systems. While it has quite often been observed that Glauber dynamics lets the system be stuck into an absorbing state distinct from its ground state in the thermodynamic limit, very little is known about the likelihood of each absorbing state. In order to explore the variety of absorbing states, we investigate the probability distribution profile of the active link density after saturation as the system size N and (k) vary. As a result, we find that the distribution of absorbing states can be split into two self-averaging peaks whose positions are determined by (k), one slightly above the ground state and the other farther away. Moreover, we suggest that the latter peak accounts for a nonvanishing portion of samples when N goes to infinity while (k) stays fixed. Finally, we discuss the possible implications of our results on opinion dynamics models.

Voter model with non-Poissonian interevent intervals

Recent analysis of social communications among humans has revealed that the interval between interactions for a pair of individuals and for an individual often follows a long-tail distribution. We investigate the effect of such a non-Poissonian nature of human behavior on dynamics of opinion formation. We use a variant of the voter model and numerically compare the time to consensus of all the voters with different distributions of interevent intervals and different networks. Compared with the exponential distribution of interevent intervals (i.e., the standard voter model), the power-law distribution of interevent intervals slows down consensus on the ring. This is because of the memory effect; in the power-law case, the expected time until the next update event on a link is large if the link has not had an update event for a long time. On the complete graph, the consensus time in the power-law case is close to that in the exponential case. Regular graphs bridge these two results such that the slowing down of the consensus in the power-law case as compared to the exponential case is less pronounced as the degree increases.

High-accuracy approximation of binary-state dynamics on networks

Binary-state dynamics (such as the susceptible-infected-susceptible (SIS) model of disease spread, or Glauber spin dynamics) on random networks are accurately approximated using master equations. Standard mean-field and pairwise theories are shown to result from seeking approximate solutions of the master equations. Applications to the calculation of SIS epidemic thresholds and critical points of nonequilibrium spin models are also demonstrated.

Update rules and interevent time distributions: slow ordering versus no ordering in the voter model

We introduce a general methodology of update rules accounting for arbitrary interevent time (IET) distributions in simulations of interacting agents. We consider in particular update rules that depend on the state of the agent, so that the update becomes part of the dynamical model. As an illustration we consider the voter model in fully connected, random, and scale-free networks with an activation probability inversely proportional to the time since the last action, where an action can be an update attempt (an exogenous update) or a change of state (an endogenous update). We find that in the thermodynamic limit, at variance with standard updates and the exogenous update, the system orders slowly for the endogenous update. The approach to the absorbing state is characterized by a power-law decay of the density of interfaces, observing that the mean time to reach the absorbing state might be not well defined. The IET distributions resulting from both update schemes show power-law tails.

Social influencing and associated random walk models: Asymptotic consensus times on the complete graph

We investigate consensus formation and the asymptotic consensus times in stylized individual- or agent-based models, in which global agreement is achieved through pairwise negotiations with or without a bias. Considering a class of individual-based models on finite complete graphs, we introduce a coarse-graining approach (lumping microscopic variables into macrostates) to analyze the ordering dynamics in an associated random-walk framework. Within this framework, yielding a linear system, we derive general equations for the expected consensus time and the expected time spent in each macro-state. Further, we present the asymptotic solutions of the 2-word naming game and separately discuss its behavior under the influence of an external field and with the introduction of committed agents.

Study and characterization of interfaces in a two-dimensional generalized voter model

We propose and study, by means of numerical simulations, the time evolution of interfaces in a generalized voter model in d=2 dimensions. In this model, a randomly selected voter can change his or her opinion (state) with a certain probability that is an algebraic function of the average opinion of his or her nearest neighbors. By starting with well-defined (sharp) interfaces between two different states of opinion, we measure the time dependence of the interface width (w), which behaves as a power law, i.e., w α t(δ). In this way we characterized three different types of interfaces: (i) between an ordered phase (consensus) and a disordered one (δ=1/2); (ii) between ordered phases having different states of opinion (δ=1/2), which corresponds to interface coarsening without surface tension; and (iii) as in (ii) but considering surface tension. Here, we observe a finite-size induced crossover with exponents δ=1/4 and δ=1/2 for early and longer times, respectively. So, our study allows for the characterization of interfaces of quite different nature in a unified fashion, providing insight into the understanding of interface coarsening with and without surface tension.

Effective multidimensional crossover behavior in a one-dimensional voter model with long-range probabilistic interactions

A variant of the standard voter model, where a randomly selected site of a one-dimensional lattice (d=1) adopts the state of another site placed at a distance r from the previous one, is proposed and studied by means of numerical simulations that are rationalized with the aid of dynamical and finite-size scaling arguments. The distance between the two sites is also selected randomly with a probability given by P(r)∝r(-(d+σ)), where σ is a control parameter. In this way one can study how the introduction of these long-range interactions influences the dynamic behavior of the standard voter model with nearest-neighbor interactions. It is found that the dynamics strongly depends on the range of the interactions, which is parameterized by σ, leading to an interesting effective multidimensional crossover behavior, as follows. (a) For σ<1 ordering is no longer observed and the average interface density [ρ(t)] assumes a steady state in the thermodynamic limit. Instead, for finite-size systems an exponential decay with a characteristic time (τ) that increases with the size is observed. This behavior resembles the scenario corresponding to the short-range voter model for d>2, as well as the case of both scale-free and small-world networks. (b) For σ>1, an ordering dynamics is observed, such that ρ(t)∝t(-α), where the exponent α increases with σ until it reaches the value α=1/2 for σ≥5, which corresponds to the behavior of the standard voter model with short-range interactions in d=1. (c) Finally, for σ≈1 we show evidence of a critical-type behavior as in the case of the critical dimension (d(c)=2) of the standard voter model.

Voter model on a directed network: role of bidirectional opinion exchanges

The voter model with the node update rule is numerically investigated on a directed network. We start from a directed hierarchical tree, and split and rewire each incoming arc at the probability p . In order to discriminate the better and worse opinions, we break the Z2 symmetry (σ=±1) by giving a little more preference to the opinion σ=1 . It is found that as p becomes larger, introducing more complicated pattern of information flow channels, and as the network size N becomes larger, the system eventually evolves to the state in which more voters agree on the better opinion, even though the voter at the top of the hierarchy keeps the worse opinion. We also find that the pure hierarchical tree makes opinion agreement very fast, while the final absorbing state can easily be influenced by voters at the higher ranks. On the other hand, although the ordering occurs much slower, the existence of complicated pattern of bidirectional information flow allows the system to agree on the better opinion.

Effects of social diversity on the emergence of global consensus in opinion dynamics

We propose a variant of the voter model by introducing the social diversity in the evolution process. Each individual is assigned a weight that is proportional to the power of its degree, where the power exponent alpha is an adjustable parameter that controls the level of diversity among individuals in the network. At each time step, a pair of connected individuals, say i and j , are randomly selected to update their opinions. The probability p(i) of choosing is opinion as their common opinion is proportional to i s weight. We consider the scale-free topology and concentrate on the efficiency of reaching the final consensus, which is significant in characterizing the self-organized systems. Interestingly, it is found that there exists an optimal value of alpha, leading to the shortest consensus time. This phenomenon indicates that, although a strong influence of high-degree individuals is helpful for quick consensus achievement, over strong influence inhibits the convergence process. Other quantities, such as the probability of an individual's initial opinion becomes the final opinion as a function of degree, the evolution of the number of opinion clusters, as well as the relationship between average consensus time and the network size, are also studied. Our results are helpful for better understanding the role of degree heterogeneity of the individuals in the opinion dynamics.

Nonequilibrium phase transition due to isolation of communities

We introduce a simple model of a growing system with m competing communities. The model corresponds to the phenomenon of defeats suffered by social groups living in isolation. A nonequilibrium phase transition is observed when at critical time tc the first isolated cluster occurs. In the one-dimensional system the volume of the new phase, i.e., the number of the isolated individuals, increases with time as Z approximately t3. For a large number of possible communities, the critical density of filled space is equal to rho(c)=(m/N)1/3, where N is the system size. A similar transition is observed for Erdos-Rényi random graphs and Barabási-Albert scale-free networks. Analytical results are in agreement with numerical simulations.

Functional models for large-scale gene regulation networks: realism and fiction

High-throughput experiments are shedding light on the topology of large regulatory networks and at the same time their functional states, namely the states of activation of the nodes (for example transcript or protein levels) in different conditions, times, environments. We now possess a certain amount of information about these two levels of description, stored in libraries, databases and ontologies. A current challenge is to bridge the gap between topology and function, i.e. developing quantitative models aimed at characterizing the expression patterns of large sets of genes. However, approaches that work well for small networks become impossible to master at large scales, mainly because parameters proliferate. In this review we discuss the state of the art of large-scale functional network models, addressing the issue of what can be considered as "realistic" and what the main limitations may be. We also show some directions for future work, trying to set the goals that future models should try to achieve. Finally, we will emphasize the possible benefits in the understanding of biological mechanisms underlying complex multifactorial diseases, and in the development of novel strategies for the description and the treatment of such pathologies.

Decelerating microdynamics can accelerate macrodynamics in the voter model

For the voter model, we study the effect of a memory-dependent transition rate. We assume that the transition of a spin into the opposite state decreases with the time it has been in its current state. Counterintuitively, we find that the time to reach a macroscopically ordered state can be accelerated by slowing down the microscopic dynamics in this way. This holds for different network topologies, including fully connected ones. We find that the ordering dynamics is governed by two competing processes which either stabilize the majority or the minority state. If the first one dominates, it accelerates the ordering of the system. The conclusions of this Letter are not restricted to the voter model, but remain valid to many other spin systems as well.

Random walks on complex trees

We study the properties of random walks on complex trees. We observe that the absence of loops is reflected in physical observables showing large differences with respect to their looped counterparts. First, both the vertex discovery rate and the mean topological displacement from the origin present a considerable slowing down in the tree case. Second, the mean first passage time (MFPT) displays a logarithmic degree dependence, in contrast to the inverse degree shape exhibited in looped networks. This deviation can be ascribed to the dominance of source-target topological distance in trees. To show this, we study the distance dependence of a symmetrized MFPT and derive its logarithmic profile, obtaining good agreement with simulation results. These unique properties shed light on the recently reported anomalies observed in diffusive dynamical systems on trees.

Coherence thresholds in models of language change and evolution: the effects of noise, dynamics, and network of interactions

A simple model of language evolution proposed by Komarova, Niyogi, and Nowak is characterized by a payoff in communicative function and by an error in learning that measure the accuracy in language acquisition. The time scale for language change is generational, and the model's equations in the mean-field approximation are a particular case of the replicator-mutator equations of evolutionary dynamics. In well-mixed populations, this model exhibits a critical coherence threshold; i.e., a minimal accuracy in the learning process is required to maintain linguistic coherence. In this work, we analyze in detail the effects of different fitness-based dynamics driving linguistic coherence and of the network of interactions on the nature of the coherence threshold by performing numerical simulations and theoretical analyses of three different models of language change in finite populations with two types of structure: fully connected networks and regular random graphs. We find that although the threshold of the original replicator-mutator evolutionary model is robust with respect to the structure of the network of contacts, the coherence threshold of related fitness-driven models may be strongly affected by this feature.

Generic absorbing transition in coevolution dynamics

We study a coevolution voter model on a complex network. A mean-field approximation reveals an absorbing transition from an active to a frozen phase at a critical value [see text for formula] that only depends on the average degree micro of the network. In finite-size systems, the active and frozen phases correspond to a connected and a fragmented network, respectively. The transition can be seen as the sudden change in the trajectory of an equivalent random walk at the critical point, resulting in an approach to the final frozen state whose time scale diverges as tau approximately |p(c) - p|(-)} near p(c).

Naming games in two-dimensional and small-world-connected random geometric networks

We investigate a prototypical agent-based model, the naming game, on two-dimensional random geometric networks. The naming game [Baronchelli, J. Stat. Mech.: Theory Exp. (2006) P06014] is a minimal model, employing local communications that captures the emergence of shared communication schemes (languages) in a population of autonomous semiotic agents. Implementing the naming games with local broadcasts on random geometric graphs, serves as a model for agreement dynamics in large-scale, autonomously operating wireless sensor networks. Further, it captures essential features of the scaling properties of the agreement process for spatially embedded autonomous agents. Among the relevant observables capturing the temporal properties of the agreement process, we investigate the cluster-size distribution and the distribution of the agreement times, both exhibiting dynamic scaling. We also present results for the case when a small density of long-range communication links are added on top of the random geometric graph, resulting in a "small-world"-like network and yielding a significantly reduced time to reach global agreement. We construct a finite-size scaling analysis for the agreement times in this case.

Consensus formation on adaptive networks

The structure of a network can significantly influence the properties of the dynamical processes that take place on them. While many studies have been paid to this influence, much less attention has been devoted to the interplay and feedback mechanisms between dynamical processes and network topology on adaptive networks. Adaptive rewiring of links can happen in real life systems such as acquaintance networks, where people are more likely to maintain a social connection if their views and values are similar. In our study, we consider different variants of a model for consensus formation. Our investigations reveal that the adaptation of the network topology fosters cluster formation by enhancing communication between agents of similar opinion, although it also promotes the division of these clusters. The temporal behavior is also strongly affected by adaptivity: while, on static networks, it is influenced by percolation properties, on adaptive networks, both the early and late time evolutions of the system are determined by the rewiring process. The investigation of a variant of the model reveals that the scenarios of transitions between consensus and polarized states are more robust on adaptive networks.

Unanimity rule on networks

We present a model for innovation, evolution, and opinion dynamics whose spreading is dictated by a unanimity rule. The underlying structure is a directed network, the state of a node is either activated or inactivated. An inactivated node will change only if all of its incoming links come from nodes that are activated, while an activated node will remain activated forever. It is shown that a transition takes place depending on the initial condition of the problem. In particular, a critical number of initially activated nodes is necessary for the whole system to get activated in the long-time limit. The influence of the degree distribution of the nodes is naturally taken into account. For simple network topologies we solve the model analytically; the cases of random and small world are studied in detail. Applications for food-chain dynamics and viral marketing are discussed.

Effect of initial conditions on Glauber dynamics in complex networks

The effect of initial spin configurations on zero-temperature Glauber spin dynamics in complex networks is investigated. In a system in which the initial spins are defined by centrality measures at the vertices of a network, a variety of nontrivial diffusive behaviors arise, particularly in relation to functional relationships between the initial and final fractions of positive spins, some of which exhibit a critical point. Notably, the majority spin in the initial state is not always dominant in the final state and the phenomena that occur as a result of the dynamics differ according to the initial condition, even for the same network. It is thus concluded that the initial condition of a complex network exerts an influence on spin dynamics that is equally as strong as that exerted by the network structure.

Nonequilibrium dynamics of language games on complex networks

The naming game is a model of nonequilibrium dynamics for the self-organized emergence of a linguistic convention or a communication system in a population of agents with pairwise local interactions. We present an extensive study of its dynamics on complex networks, that can be considered as the most natural topological embedding for agents involved in language games and opinion dynamics. Except for some community structured networks on which metastable phases can be observed, agents playing the naming game always manage to reach a global consensus. This convergence is obtained after a time generically scaling with the population's size N as t(conv) approximately N(1.4+/-0.1), i.e., much faster than for agents embedded on regular lattices. Moreover, the memory capacity required by the system scales only linearly with its size. Particular attention is given to heterogeneous networks, in which the dynamical activity pattern of a node depends on its degree. High-degree nodes have a fundamental role, but require larger memory capacity. They govern the dynamics acting as spreaders of (linguistic) conventions. The effects of other properties, such as the average degree and the clustering, are also discussed.

Effects of substrate network topologies on competition dynamics

We study a competition dynamics, based on the minority game, endowed with various substrate network structures. We observe the effects of the network topologies by investigating the volatility of the system and the structure of follower networks. The topology of substrate structures significantly influences the system efficiency represented by the volatility and such substrate networks are shown to amplify the herding effect and cause inefficiency in most cases. The follower networks emerging from the leadership structure show a power-law incoming degree distribution. This study shows the emergence of scale-free structures of leadership in the minority game and the effects of the interaction among players on the networked version of the game.

Domain motion in the voter model with noise

We study the voter model with noise on one-dimensional chains using Monte Carlo simulations and finite-size scaling techniques. We observe that the system evolution toward consensus is deeply affected by the addition of noise, and that the time to reach complete ordering increases with the noise parameter q. In particular, the simulations show that the average domain size scales as xi approximately q(-1/2) whereas the magnetization scales with the number of nodes as m approximately N(-1/2).

Voter model dynamics in complex networks: Role of dimensionality, disorder, and degree distribution

We analyze the ordering dynamics of the voter model in different classes of complex networks. We observe that whether the voter dynamics orders the system depends on the effective dimensionality of the interaction networks. We also find that when there is no ordering in the system, the average survival time of metastable states in finite networks decreases with network disorder and degree heterogeneity. The existence of hubs, i.e., highly connected nodes, in the network modifies the linear system size scaling law of the survival time. The size of an ordered domain is sensitive to the network disorder and the average degree, decreasing with both; however, it seems not to depend on network size and on the heterogeneity of the degree distribution.