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 $N{ensuremath{mu}}_{1}^{2}/{ensuremath{mu}}_{2}$, where ${ensuremath{mu}}_{k}$ is the $k$th moment of the degree distribution. For a power-law degree distribution ${n}_{k}ensuremath{sim}{k}^{ensuremath{-}ensuremath{nu}}$, ${T}_{N}$ thus scales as $N$ for $ensuremath{nu}>3$, as $N/mathrm{ln}N$ for $ensuremath{nu}=3$, as ${N}^{(2ensuremath{nu}ensuremath{-}4)/(ensuremath{nu}ensuremath{-}1)}$ for $2<ensuremath{nu}<3$, as $(mathrm{ln}N{)}^{2}$ for $ensuremath{nu}=2$, and as $mathcal{O}(1)$ for $ensuremath{nu}<2$. These results agree with simulation data for networks with both uncorrelated and correlated node degrees.