University of North Carolina at Chapel Hill (Kenan-Flagler)
Social networks tend to contain some amount of randomness and some amount of non-randomness. The amount of randomness versus non-randomness affects the properties of a social network. In this paper, the authors theoretically analyze graph randomness and present a framework which provides a series of non-randomness measures at levels of edge, node, and the overall graph. They show that graph non-randomness can be obtained mathematically from the spectra of the adjacency matrix of the network. They also derive the upper bound and lower bound of non-randomness value of the overall graph. They conduct both theoretical and empirical studies in spectral geometries of social networks and show their proposed non-randomness measures can better characterize and capture graph randomness than previous measures.