Could any graph be turned into a small-world?
作者： Philippe Duchon , Nicolas Hanusse , Emmanuelle Lebhar , Nicolas Schabanel
DOI: 10.1016/J.TCS.2005.12.008
关键词: Combinatorics 、 Strength of a graph 、 Mathematics 、 Null graph 、 Graph property 、 Random geometric graph 、 Lattice graph 、 Planar graph 、 Butterfly graph 、 Line graph
摘要: In addition to statistical graph properties (diameter, degree, clustering, etc.), Kleinberg [The small-world phenomenon: an algorithmic perspective, in: Proc. 32nd ACM Symp. on Theory of Computing (STOC), 2000, pp. 163-170] showed that a can also be seen as in which the routing task efficiently and easily done spite lack global knowledge. More precisely, lattice network augmented by extra random edges (but not chosen uniformly), short path polylogarithmic expected length found using greedy algorithm with local knowledge nodes. We call such navigable since paths exist followed partial network. this paper, we show wide class graphs into small-worlds.
archives-ouvertes.fr
elsevier.com
sci-hub.se 参考文章(14)
Pierre Fraigniaud, A New Perspective on the Small-World Phenomenon: Greedy Routing in Tree-Decomposed Graphs ,(2005)
Lali Barriére, Pierre Fraigniaud, Evangelos Kranakis, Danny Krizanc, Efficient Routing in Networks with Long Range Contacts international symposium on distributed computing. pp. 270- 284 ,(2001) , 10.1007/3-540-45414-4_19
S. Milgram, The Small World Problem Psychology today. ,vol. 1, pp. 60- 67 ,(1967)
Emmanuelle Lebhar, Nicolas Schabanel, Close to optimal decentralized routing in long-range contact networks Theoretical Computer Science. ,vol. 348, pp. 294- 310 ,(2005) , 10.1016/J.TCS.2005.09.019
Pierre Fraigniaud, Cyril Gavoille, Christophe Paul, Eclecticism shrinks even small worlds Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing - PODC '04. pp. 169- 178 ,(2004) , 10.1145/1011767.1011793
M. E. J. Newman, D. J. Watts, Scaling and percolation in the small-world network model Physical Review E. ,vol. 60, pp. 7332- 7342 ,(1999) , 10.1103/PHYSREVE.60.7332
Chip Martel, Van Nguyen, Analyzing Kleinberg's (and other) small-world Models Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing - PODC '04. pp. 179- 188 ,(2004) , 10.1145/1011767.1011794
Don Coppersmith, David Gamarnik, Maxim Sviridenko, The diameter of a long-range percolation graph Random Structures and Algorithms. ,vol. 21, pp. 1- 13 ,(2002) , 10.1002/RSA.10042
Duncan J. Watts, Steven H. Strogatz, Collective dynamics of small-world networks Nature. ,vol. 393, pp. 440- 442 ,(1998) , 10.1038/30918
Jon Kleinberg, The small-world phenomenon: an algorithmic perspective symposium on the theory of computing. pp. 163- 170 ,(2000) , 10.1145/335305.335325