Polylogarithmic network navigability using compact metrics with small stretch

ABSTRACT

Graph augmentation theory is a general framework for analyzing navigability in social networks. It is known that, for large classes of graphs, there exist augmentations of these graphs such that greedy routing according to the shortest path metric performs in polylogarithmic expected number of steps. However, it is also known that there are classes of graphs for which no augmentations can enable greedy routing according to the shortest path metric to perform better than Ω(n^{1/√log n}) expected number of steps. In fact, the best known universal bound on the greedy diameter of arbitrary graph is essentially n^1/3. That is, for any graph, there is an augmentation such that greedy routing according to the shortest path metric performs in Õ(n^1/3) expected number of steps. Hence, greedy routing according to the shortest path metric has at least two drawbacks. First, it is in general space-consuming to encode locally the shortest path distances to all the other nodes, and, second, greedy routing according to the shortest path metric performs poorly in some graphs.

We prove that, using semimetrics of small stretch results in a huge positive impact, in both encoding space and efficiency of greedy routing. More precisely, we show that, for any connected n-node graph G and any integer k ≥ 1, there exist an augmentation φ of G and a semimetric μ on G with stretch 2/k-1 such that greedy routing according to μ performs in O(k² n^2/klog²n) expected number of steps. As a corollary, we get that for any connected n-node graph G, there exist an augmentation φ of G and a semimetric μ on G with stretch O(log n) such that greedy routing according to μ performs in polylogarithmic expected number of steps. This latter semimetric can be encoded locally at every node using only a polylogarithmic number of bits.

REFERENCES

• 1: Ittai Abraham , Cyril Gavoille, Object location using path separators, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146411]
• 2: James Aspnes , Zoë Diamadi , Gauri Shah, Fault-tolerant routing in peer-to-peer systems, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571862]
• 3: B. Awerbuch , D. Peleg, Sparse partitions, Proceedings of the Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, p.503-513 vol.2, October 22-24, 1990 [doi>10.1109/FSCS.1990.89571]
• 4: Lali Barrière , Pierre Fraigniaud , Evangelos Kranakis , Danny Krizanc, Efficient Routing in Networks with Long Range Contacts, Proceedings of the 15th International Conference on Distributed Computing, p.270-284, October 03-05, 2001
• 5: S. Banerjee, T. Griffin, and M. Pias. The interdomain connectivity of PlanetLab nodes. In 5th Workshop on Passive and Active Measurements,LNCS 3015, pp. 73--82, Springer, 2004.
• 6: D. Barbella, G. Kachergis, D. Liben-Nowell, A. Sallstrom, and B. Sowell. Depth of field and cautious-greedy routing in social networks. In 18th International Symp. on Algo. and Computation (ISAAC), LNCS 4835, pp. 574--586. Springer, 2007.
• 7: A. Clauset and C. Moore How Do Networks Become Navigable? http://arxiv.org/abs/cond-mat/0309415v2.
• 8: P. Dodds, R. Muhamad, and D. Watts. An experimental study of search in global social networks. Science 301, no5634, pp. 827--829, 2003.
• 9: 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]
• 10: Philippe Duchon , Nicolas Hanusse , Emmanuelle Lebhar , Nicolas Schabanel, Towards small world emergence, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148145]
• 11: George Giakkoupis , Vassos Hadzilacos, On the complexity of greedy routing in ring-based peer-to-peer networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281117]
• 12: Cyril Gavoille , Michal Katz , Nir A. Katz , Christophe Paul , David Peleg, Approximate Distance Labeling Schemes, Proceedings of the 9th Annual European Symposium on Algorithms, p.476-487, August 28-31, 2001
• 13: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Journal of Algorithms, v.53 n.1, p.85-112, October 2004 [doi>10.1016/j.jalgor.2004.05.002]
• 14: M. Flammini, L. Moscardelli, A. Navarra, and S. Perennes. Asymptotically optimal solutions for small world graphs. In 19th International Symp. on Distributed Computing (DISC), LNCS 3724, Springer, pp. 414--428, 2005.
• 15: P. Fraigniaud. Greedy Routing in Tree-Decomposed Graphs. In 13th Europ. Symp. on Algo. (ESA), LNCS 3669, Springer, pp. 791--802, 2005.
• 16: P. Fraigniaud. Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation. In 15th Europ. Symp. on Algo. (ESA), LNCS 4698, Springer, pp. 2--11, 2007.
• 17: Pierre Fraigniaud , Cyril Gavoille , Christophe Paul, Eclecticism shrinks even small worlds, 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.1011793]
• 18: Pierre Fraigniaud , Cyril Gavoille , Adrian Kosowski , Emmanuelle Lebhar , Zvi Lotker, Universal augmentation schemes for network navigability: overcoming the √n-barrier, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248379]
• 19: Pierre Fraigniaud , Emmanuelle Lebhar , Zvi Lotker, A doubling dimension threshold θ(loglogn) for augmented graph navigability, Proceedings of the 14th conference on Annual European Symposium, p.376-386, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_35]
• 20: P. Fraigniaud, E. Lebhar, and L. Viennot. The inframetric model for the internet. In 27th IEEE Conference on Computer Communications (INFOCOM), 2008.
• 21: 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]
• 22: J. Kleinberg. Complex networks and decentralized search algorithm. Nevanlinna prize presentation at the International Congress of Mathematicians (ICM), Madrid, 2006.
• 23: E. Lebhar, and N. Schabanel. Searching for Optimal paths in long-range contact networks. In 31st International Colloquium on Automata, Languages andProgramming (ICALP), LNCS 3142, pp. 894--905, 2004.
• 24: Gurmeet Singh Manku , Moni Naor , Udi Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007368]
• 25: 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]
• 26: Van Nguyen , Chip Martel, Analyzing and characterizing small-world graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 27: S. Milgram. The Small-World Problem. Psychology Today, pp. 60--67, 1967.
• 28: D. Peleg. Private communication. Workshop of COST Action 295 "DYNAMO", Les Ménuires, Jan. 2006.
• 29: O. Sandberg. Neighbor Selection and Hitting Probability in Small-World Graphs. Annals of Applied Probability (to appear).
• 30: 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]
• 31: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005 [doi>10.1145/1044731.1044732]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
      C.2.4 Distributed Systems

General Terms:
Algorithms

Keywords:
network navigability, small world phenomenon, social networks