The Intrinsic Scale of Networks is Small
This provides a new metric for understanding network structure across domains, though it appears incremental to existing network analysis methods.
The authors defined and measured the intrinsic scale at which networks reveal their identity through subgraph distinguishability, finding it to be surprisingly small (7-20 vertices) across various network types, and showed it quantifies network structure and fragility.
We define the intrinsic scale at which a network begins to reveal its identity as the scale at which subgraphs in the network (created by a random walk) are distinguishable from similar sized subgraphs in a perturbed copy of the network. We conduct an extensive study of intrinsic scale for several networks, ranging from structured (e.g. road networks) to ad-hoc and unstructured (e.g. crowd sourced information networks), to biological. We find: (a) The intrinsic scale is surprisingly small (7-20 vertices), even though the networks are many orders of magnitude larger. (b) The intrinsic scale quantifies ``structure'' in a network -- networks which are explicitly constructed for specific tasks have smaller intrinsic scale. (c) The structure at different scales can be fragile (easy to disrupt) or robust.