  Borrowing from concepts in expander graphs, we study the expansion properties
of real-world, complex networks (e.g. social networks, unstructured
peer-to-peer or P2P networks) and the extent to which these properties can be
exploited to understand and address the problem of decentralized search. We
first produce samples that concisely capture the overall expansion properties
of an entire network, which we collectively refer to as the expansion
signature. Using these signatures, we find a correspondence between the
magnitude of maximum expansion and the extent to which a network can be
efficiently searched. We further find evidence that standard graph-theoretic
measures, such as average path length, fail to fully explain the level of
"searchability" or ease of information diffusion and dissemination in a
network. Finally, we demonstrate that this high expansion can be leveraged to
facilitate decentralized search in networks and show that an expansion-based
search strategy outperforms typical search methods.
