  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
three shortcomings of the currently popular definition and detection methods
rendering the concept less powerful. First, the classical definition combines
high transitivity with a low average path length in a rather ad-hoc fashion
which confounds the two separate aspects. We find that in several cases,
networks get flagged as "small world" by the current methodology solely because
of their high transitivity. Second, the detection methods lack a formal
statistical inference, and third, the comparison is typically performed against
simplistic random graph models as the baseline which ignores well-known network
characteristics. We propose three innovations to address these issues. First,
we decouple the properties of high transitivity and low average path length as
separate events to test for. Second, we define the property as a statistical
test between a suitable null model and a superimposed alternative model. Third,
the test is performed using parametric bootstrap with several null 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\"{o}s-Ren\'{y}i null model for which we provide theoretical guarantees on
the asymptotic level and power. Applying the proposed methods on a large number
of network datasets, we uncover new insights about their small-world property.
