The spectra of small-world random networks

Small-world networks are characterized by highly clustered nodes and a small characteristic path length. They appear in various contexts; notable examples include biological systems such as neural networks and societal infrastructure such as airport networks. Since their identification in 1998 by Watts and Strogatz, small-world networks have been studied with numerous qualitative and quantitative measures. Traditional methods of identifying whether or not a network is a small-world rely on comparisons between its characteristic path length and local cliquishness with values for a purely random or purely regular graph of the same dimensions. The effectiveness of each of these measures is highly dependent on the specific aspects of a small-world network of interest in a given context. Here we present a practical tool to verify whether a network can be considered a small-world based on its eigenvalue spectrum properties. We introduce an ensemble of small-world matrices and apply the Rogers-Pastur formula for computing the spectra of non-Hermitian matrices. Next, we analyze the spectra's main features and compare our results to other common measures employed to describe small-world networks. Finally, we illustrate our results on several well-known examples of small-world networks.