We study the voter model on heterogeneous graphs. We exploit the nonconservation of the magnetization to characterize how consensus is reached. For a network of N nodes with an arbitrary but uncorrelated degree distribution, the mean time to reach consensus T N scales as N 2 1 = 2 , where k is the kth moment of the degree distribution. For a power-law degree distribution n k k ÿ , T N thus scales as N for > 3, as N= lnN for 3, as N 2ÿ4=ÿ1 for 2 < < 3, as lnN 2 for 2, and as O1 for < 2. These results agree with simulation data for networks with both uncorrelated and correlated node degrees. DOI: 10.1103/PhysRevLett.94.178701 PACS numbers: 89.75.Fb, 02.50.2r, 05.40.2a In this Letter we study the voter model [1] on heterogeneous networks and show that its behavior is dramatically different from that on regular lattices. Many recent studies of basic statistical mechanical models on heterogeneous graphs have begun to elucidate how the dispersity in node degree (the number of links attached to a node) affects critical behavior. A representative but incomplete set of examples include percolation [2], the Ising model [3] [4] [5] [6] [7] , diffusion and random walks [8] [9] [10] [11] , as well as the voter model itself [12 -15]. The voter model is perhaps the simplest and most completely solved example of cooperative behavior. For these reasons, our analytical predictions for the voter model on heterogeneous networks should provide new insights into the role of underlying heterogeneity on dynamical cooperative behavior. In the model, each node of a graph is endowed with two states-spin up and spin down. The evolution consists of (i) picking a random voter; (ii) the selected voter adopts the state of a randomly chosen neighbor. These steps are repeated until a finite system necessarily reaches consensus. One basic property of the voter model is the exit probability, namely, the probability that the system ends with all spins up, E 0 , as a function of the initial density of up spins 0 . Because the mean magnetization (averaged over all realizations and all histories) is conserved on regular lattices, and because the only possible final states are consensus, E 0 0 [1]. A second basic property is the mean time to reach consensus, T N . For regular lattices in d dimensions, it is known that T N scales with the number of nodes N as N 2 in d 1, as N lnN in d 2, and as N in d > 2 [1,16]. For heterogeneous networks, we find that T N grows as N 2 1 = 2 , where k is the kth moment of the degree distribution of the network [Eq. (14)]. In contrast to lattice systems, the N dependence of T N can be sublinear. To understand how dispersity in node degree affects voter model dynamics, we first examine the illustrative example of the complete bipartite graph. We then extend this approach to determine the behavior of the voter model on networks with power-law degree distributions, but with no correlations between node degrees. Finally, we validate our theoretical results by simulations of the voter model on networks with power-law degree distributions, both with and without node degree correlations. Consider the voter model on the complete bipartite graph K a;b of N a b nodes that are partitioned into two subgraphs a and b (Fig. 1) . Each node in the a subgraph is connected to all nodes in the b subgraph, and vice versa. Let N a;b be the respective number of up spins on each subgraph. In an update event, these numbers change according to For dN a , the gain term accounts for flipping a down spin in subgraph a due to its interaction with an up spin in b, while the loss term accounts for flipping an up spin in subgraph a.  While the sum of the subgraph densities a b is conserved, the magnetization m a a b b =a b is not [14] . However, the bias in the rate equations for a
In REF the pure voter model on heterogeneous graphs is solved under the mean-field assumption.
Voter Model on Heterogeneous Graphs.
Phys. Rev. Lett. 94, 178701 (2005).
Physics Computer Science Medicine