Could Any Graph Be Turn Into A Smallworld?.pdf

explores the concept of "navigable small-worlds," graphs where efficient routing can be achieved with limited global knowledge. They build upon previous work by Kleinberg, who demonstrated that a specific lattice network augmented with random edges could support short paths while maintaining local knowledge at each node.

The authors propose a generalized augmentation process applicable to a wide range of graph metrics. They define navigable small-worlds as graphs where a decentralized greedy routing algorithm can find paths of polylogarithmic length between any pair of nodes, using only local knowledge and visiting a limited number of nodes.

Key points:

- Augmentation Process: The process involves adding a controlled amount of random long-range links to an underlying base graph (H) while preserving its inherent properties.
- Greedy Routing Algorithm: A simple greedy algorithm, which forwards messages to the nearest neighbor (in the known metric), is shown to work efficiently in these augmented graphs.
- Generalization: The authors show that this concept can be extended to various graph structures, including trees and group-based structures, by carefully choosing the distribution of random long-range links.
- Dimensional Phenomenon: They introduce a new perspective by studying cartesian products of independent graphs, demonstrating that small-world properties can emerge from multiple underlying structures.
- Applications: This theory encompasses unbalanced grids, toruses, and even Cayley graphs, suggesting that many real-world networks could exhibit small-world characteristics.