Expansion and search in networks

Arun S. Maiya, Tanya Y. Berger-Wolf

Abstract

Traditional network analysis often focuses on "minimum expansion" to identify bottlenecks. This paper shifts the focus to maximum expansion to understand how information spreads and how networks can be efficiently searched. By introducing "expansion signatures" and a novel decentralized search strategy called Expansion Search (XS), the authors demonstrate that targeting high-expansion nodes significantly improves searchability across diverse network topologies.

Introduction

In massive, decentralized networks like peer-to-peer (P2P) systems or the World Wide Web, navigating without a global map is a fundamental challenge. This "decentralized search" problem—starting from one node and reaching a target using only local information—has traditionally been studied through the lens of "small-world" properties like average path length. However, these metrics fail to explain why networks with similar path lengths can have vastly different search efficiencies. The authors argue that the missing link is expansion: the capacity of a set of nodes to reach a large number of new neighbors.

Characterizing Networks via Expansion Signatures

To visualize a network's inherent searchability, the authors propose Expansion Signatures. These signatures are generated using a greedy approximation algorithm (GreedyAPX) that identifies sets of nodes maximizing expansion at various scales. By plotting "expansion quality" (normalized expansion) against sample size, these signatures reveal how quickly a network can be covered.

Expansion signatures for real-world networks showing the significant gap between maximum and minimum expansion.

As shown in the signatures above, there is a stark contrast between maximum and minimum expansion. While theoretical computer science often focuses on the "bottleneck" (minimum expansion), search and diffusion processes are primarily driven by the maximum expansion potential of the network's most influential clusters.

Expansion Search (XS)

Building on these insights, the authors introduce Expansion Search (XS), a decentralized search heuristic. Unlike GreedyAPX, which requires global knowledge, XS operates step-by-step using only local information. At each hop, the current node examines its neighbors' neighbors (two-hop knowledge) and moves to the neighbor that would most increase the total number of unique nodes "seen" by the search path so far. This strategy explicitly avoids redundancy by seeking out new expansion rather than just high-degree nodes.

Key Results and Performance

The study evaluated XS against standard baselines—including Degree Search (DS), Random Walks (RW), and Breadth-First Search (BFS)—across ten diverse datasets ranging from biological neural networks to social trust networks.

Comparison of cumulative nodes discovered by the decentralized XS algorithm versus the global GreedyAPX baseline across various network types.

XS Dominance

In almost every dataset, XS required the fewest steps to discover significant portions of the network. For instance, in the Enron email network, XS discovered 50% of the nodes in just 49 steps, compared to 559 steps for a Random Walk. As illustrated in the performance plots, the decentralized XS algorithm closely tracks the performance of the global GreedyAPX baseline, proving it to be a highly effective local approximation of an optimal global strategy.

The Searchability Spectrum

The research revealed a wide spectrum of searchability. Social networks like Enron and biological networks like C. elegans were highly searchable due to their high expansion. Conversely, the Western US Power Grid proved the least searchable; its sparse, "stringy" structure resists efficient discovery, requiring XS over 8,000 steps to find 50% of the nodes. Interestingly, the Gnutella P2P network—designed for search—was among the least searchable real-world networks studied, highlighting a potential misalignment between its intended function and its topological reality.

Conclusion and Future Work

Expansion signatures provide a more accurate "fingerprint" for network searchability than traditional path-length metrics. While XS requires two-hop local knowledge—a higher overhead than simple degree search—its efficiency gains are substantial. Future research will focus on adapting expansion-based strategies for finding specific target nodes and extending the framework to directed networks where reachability is inherently asymmetric.

Summary updated

BibTeX
@inproceedings{maiya2010expansion,
  author = {Arun S. Maiya and Tanya Y. Berger-Wolf},
  title = {{Expansion and search in networks}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {2010},
  doi = {10.1145/1871437.1871471},
}
Figure