Roughness scaling for Edwards-Wilkinson relaxation in small-world networks

Motivated by a fundamental synchronization problem in scalable parallel computing and by a recent criterion for "mean-field" synchronizability in interacting systems, we study the Edwards-Wilkinson model on two variations of a small-world network. In the first version each site has exactly one random link of strength p, while in the second one each site on average has p links of unit strength. We construct a perturbative description for the width of the stationary-state surface (a measure of synchronization), in the weak- and sparse-coupling limits, respectively, and verify the results by performing exact numerical diagonalization. The width remains finite in the limit of infinite system size for both cases, but exhibits anomalous scaling with p in the latter for d< or =2.