Voter Model on Heterogeneous Graphs

Abstract

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}^{(2\ensuremath{\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.