The effect of power-law degrees on the navigability of small worlds: [extended abstract]

ABSTRACT

We analyze decentralized routing in small-world networks that combine a wide variation in node degrees with a notion of spatial embedding. Specifically, we consider a variation of Kleinberg's augmented-lattice model (STOC 2000), where the number of long-range contacts for each node is drawn from a power-law distribution. This model is motivated by the experimental observation that many "real-world" networks have power-law degrees. In such networks, the exponent α of the power law is typically between 2 and 3. We prove that, in our model, for this range of values, 2 < α < 3, the expected number of steps of greedy routing from any source to any target is O(log^α-1 n) steps. This bound is tight in a strong sense. Indeed, we prove that the expected number of steps of greedy routing for a uniformly-random pair of source-target nodes is Ω(log^α-1 n) steps. We also show that for α < 2 or α ≥ 3, greedy routing performs in Θ(log² n) xexpected steps, and for α = 2, Θ(log^1+ε n) expected steps are required, where 1/3 ≤ ε ≤ 1/2. To the best of our knowledge, these results are the first to formally quantify the effect of the power-law degree distribution on the navigability of small worlds. Moreover, they show that this effect is significant. In particular, as α approaches 2 from above, the expected number of steps of greedy routing in the augmented lattice with power-law degrees approaches the square-root of the expected number of steps of greedy routing in the augmented lattice with fixed degrees, although both networks have the same average degree.

REFERENCES

• 1: L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman. Search in power-law networks. Phys. Rev. E, 64:46135, 2001.
• 2: R. Albert and A.-L. Barab&#225;si. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47--97, 2002.
• 3: Bélaa Bollobás , Oliver Riordan, The Diameter of a Scale-Free Random Graph, Combinatorica, v.24 n.1, p.5-34, January 2004 [doi>10.1007/s00493-004-0002-2]
• 4: Augustin Chaintreau , Pierre Fraigniaud , Emmanuelle Lebhar, Networks Become Navigable as Nodes Move and Forget, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_12]
• 5: F. R. K. Chung and L. Lu. The average distance in a random graph with given expected degrees. Internet Mathematics, 1(1):91--113, 2003.
• 6: A. Clauset and C. Moore. How do networks become navigable? preprint at arxiv.org, 2003.
• 7: Martin Dietzfelbinger , Philipp Woelfel, Tight lower bounds for greedy routing in uniform small world rings, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536494]
• 8: P. S. Dodds, R. Muhamad, and D. J. Watts. An experimental study of search in global social networks. Science, 301(5634):827--829, 2003.
• 9: S. N. Dorogovtsev , J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW (Physics), Oxford University Press, Inc., New York, NY, 2003
• 10: Philippe Duchon , Nicolas Hanusse , Emmanuelle Lebhar , Nicolas Schabanel, Could any graph be turned into a small-world?, Theoretical Computer Science, v.355 n.1, p.96-103, 6 April 2006 [doi>10.1016/j.tcs.2005.12.008]
• 11: P. Fraigniaud, P. Gauron, and M. Latapy. Combining the use of clustering and scale-free nature of user exchanges into a simple and efficient P2P system. In Proc. 11th European Conf. on Parallel Computing (Euro-Par), pages 1163--1172, 2005.
• 12: B. Kim, C. Yoon, S. Han, and H. Jeong. Path finding strategies in scale-free networks. Phys. Rev. E, 65:027103, 2002.
• 13: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 14: J. Kleinberg. Complex networks and decentralized search algorithms. In Proc. International Congress of Mathematicians (ICM), 2006.
• 15: Ravi Kumar , David Liben-Nowell , Andrew Tomkins, Navigating low-dimensional and hierarchical population networks, Proceedings of the 14th conference on Annual European Symposium, p.480-491, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_44]
• 16: D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. Proc. National Academy of Sciences of the USA, 102(33):11623--11628, 2005.
• 17: 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, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011794]
• 18: S. Milgram. The small world problem. Psychology Today, 67(1):60--67, 1967.
• 19: M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45(2):167--256, 2003.
• 20: O. Sandberg and I. Clarke. The evolution of navigable small-world networks. preprint at arxiv.org, 2006.
• 21: Nima Sarshar , P. Oscar Boykin , Vwani P. Roychowdhury, Percolation Search in Power Law Networks: Making Unstructured Peer-to-Peer Networks Scalable, Proceedings of the Fourth International Conference on Peer-to-Peer Computing, p.2-9, August 25-27, 2004 [doi>10.1109/P2P.2004.39]
• 22: &#214;. Simsek and D. Jensen. Decentralized search in networks using homophily and degree disparity. In Proc. 19th Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 304--310, 2005.
• 23: Aleksandrs Slivkins, Distance estimation and object location via rings of neighbors, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073823]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Algorithms, Performance, Theory

Keywords:
greedy routing, power-law degrees, small-world graphs