Voter Model on Heterogeneous Graphs

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 Nmu(2)1/mu(2), where mu(k) is the kth moment of the degree distribution. For a power-law degree distribution n(k) approximately k(-nu), T(N) thus scales as N for nu > 3, as N/ln(N for nu = 3, as N((2nu-4)/(nu-1)) for 2 < nu < 3, as (lnN)2 for nu = 2, and as omicron(1) for nu < 2. These results agree with simulation data for networks with both uncorrelated and correlated node degrees.