Ensemble analysis of complex network properties—an MCMC approach

Abstract

What do generic networks that have certain properties look like? We use relative canonical network ensembles as the ensembles that realize a property R while being as indistinguishable as possible from a background network ensemble. This allows us to study the most generic features of the networks giving rise to the property under investigation. To test the approach we apply it to study properties thought to characterize ‘small-world networks’. We consider two different defining properties, the ‘small-world-ness’ of Humphries and Gurney, as well as a geometric variant. Studying them in the context of Erdős-Rényi and Watts-Strogatz ensembles we find that all ensembles studied exhibit phase transitions to systems with large hubs and in some cases cliques. Such features are not present in common examples of small-world networks, indicating that these properties do not robustly capture the notion of small-world networks. We expect the overall approach to have wide applicability for understanding network properties of real world interest, such as optimal ride-sharing designs, the vulnerability of networks to cascades, the performance of communication topologies in coordinating fluctuation response or the ability of social distancing measures to suppress disease spreading.