The Intrinsic Scale Of Networks is Small
abstract, paper and talk
Abstract
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.
Intuition
Intrinsic scale:
- Grab a chunk C from network N
- Make some changes to network N to obtain network N˙
- Now grab another chunk C˙ from N˙
- The largest number of nodes at which C and C˙ cannot be distinguished from each other is defined as the intrinsic scale of the network
- This, as it turns out, is very small (7 - 20 nodes) for many day-to-day networks
Talk
Slides
Download here
Paper
Download here