A New Perspective on the Small-World Phenomenon: Greedy Routing in Tree-Decomposed Graphs

摘要: Milgram’s experiment (1967) demonstrated that there are short chains of acquaintances between individuals, and these can be discovered in a greedy manner. Kleinberg (2000) gave formal support to this so-called “small world phenomenon” by using meshes augmented with long-range links chosen randomly according harmonic distributions. In paper, we propose new perspective on the small phenomenon considering arbitrary graphs distributions guided tree-decompositions graphs. We show that, for any n-node graph G treewidth ≤ k, exists tree-decomposition-based distribution D such routing (G,D) performs O(k log n) expected number steps. argue augmenting is plausible context social networks. However, networks have unbounded treewidth. Nevertheless, note few long chordless cycles because their high clustering coefficient. prove if has chordality then insures O((k + logn) particular, O(log (e.g., chordal graphs), This latter result stresses fact our model may well explain why so efficient networks, as observed experiment.