The Intrinsic Scale of Networks is Small
  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.
