Testing for the Network Small-World Property

Abstract

Researchers have long observed that the ``small-world" property, which combines the concepts of high transitivity or clustering with a low average path length, is ubiquitous for networks obtained from a variety of disciplines, including social sciences, biology, neuroscience, and ecology. However, we find several shortcomings of the currently prevalent definition and detection methods rendering the concept less powerful. First, the widely used \textit{small world coefficient} metric combines high transitivity with a low average path length in a single measure that confounds the two separate aspects. We find that the value of the metric is dominated by transitivity, and in several cases, networks get flagged as ``small world" solely because of their high transitivity. Second, the detection methods lack a formal statistical inference. Third, the comparison is typically performed against simplistic random graph models as the baseline, ignoring well-known network characteristics and risks confounding the small world property with other network properties. We decouple the properties of high transitivity and low average path length as separate events to test for. Then we define the property as a statistical test between a suitable null hypothesis and a superimposed alternative hypothesis. We propose a parametric bootstrap test with several null hypothesis models to allow a wide range of background structures in the network. In addition to the bootstrap tests, we also propose an asymptotic test under the Erdös-Renýi null model for which we provide theoretical guarantees on the asymptotic level and power. Our theoretical results include asymptotic distributions of clustering coefficient for various asymptotic growth rates on the probability of an edge. Applying the proposed methods to a large number of network datasets, we uncover new insights about their small-world property.

References in corpus (14)

• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Community detection in graphs
• Lethality and centrality in protein networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Nonoptimal Component Placement, but Short Processing Paths, due to Long-Distance Projections in Neural Systems
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• A small-world of weak ties provides optimal global integration of self-similar modules in functional brain networks
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Constrained Randomisation of Weighted Networks
• Higher-Order Spectral Clustering under Superimposed Stochastic Block Model