Loading...
Please wait, while we are loading the content...
Similar Documents
A new perspective on the small-world phenomenon: greedy routing in tree-decomposed graphs (2005).
| Content Provider | CiteSeerX |
|---|---|
| Author | Fraigniaud, Pierre |
| Abstract | Milgram’s experiment (1967) demonstrated that there are short chains of acquaintances between individuals, and that these chains 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 to harmonic distributions. In this paper, we propose a new perspective on the small world phenomenon by considering arbitrary graphs augmented according to distributions guided by tree-decompositions of the graphs. We show that, for any n-node graph G of treewidth ≤ k, there exists a tree-decomposition-based distribution D such that greedy routing in the augmented graph (G, D) performs in O(k log 2 n) expected number of steps. We argue that augmenting a graph with long-range links chosen according to a tree-decomposition-based distribution is plausible in the context of social networks. However, social networks can have unbounded treewidth. Nevertheless, we note that these networks have few long chordless cycles because of their high clustering coefficient. We prove that if G has chordality ≤ k, then the tree-decomposition-based distribution D insures that greedy routing in (G, D) performs in O((k + log n)log n) expected number of steps. In particular, for any n-node graph G of chordality O(log n) (e.g., chordal graphs), greedy routing in the augmented graph (G, D) performs in O(log 2 n) expected number of steps. This latter result stresses the fact that our model may well explain why greedy routing is so efficient in social networks, such as observed in Milgram’s experiment. |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Small World Phenomenon Short Chain Long-range Link High Clustering Coefficient Augmented Graph Latter Result Greedy Manner Formal Support Milgram Experiment Greedy Routing Chordal Graph Small-world Phenomenon Social Network Arbitrary Graph So-called Small World Phenomenon Harmonic Distribution New Perspective Tree-decomposed Graph N-node Graph Long Chordless Cycle Tree-decomposition-based Distribution |
| Content Type | Text |
