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