Distance graphs: from random geometric graphs to Bernoulli graphs and between

ABSTRACT

We introduce and study random distance graph. A random distance, D(n,g) results from placing n points uniformly at random on the unit area disk and connecting every two points independently with probability g(d), where d is the distance between the nodes and g is the connection function. We give a connection function g(r,a,d) with parameters r and a and show the following: (a) D(n,g(r,a)) captures as special cases both the standard random geometric graph G(n,r) and the Bernoulli random graph B(n,p) (a.k.a. Erdos-Renyi graph). (b) Using results from continuum percolation we are able to bound the connectivity threshold of D(n,g(r,a)), with G(n,r) and B(n,p) as special (previously known) cases. (c) Contrary to G(n,r) and B(n,p), for a wide range of r and α a is, in fact, a "Small World" graph with high clustering coefficient of about 0.5865a and diameter of Θ({log n}/{log log n}). As opposed to previous Small World models that rely on deterministic sub-structures to grantee connectivity, random distance graphs offer a completely randomized model with a proved bounds for connectivity threshold, clustering coefficient and diameter.

REFERENCES

• 1: Chen Avin , Judea Pearl , Deborah Estrin, Random geometric graphs: an algorithmic perspective, University of California at Los Angeles, Los Angeles, CA, 2006
• 2: AVIN, C., AND ERCAL, G. On the cover time of random geometric graphs. In Proc. Automata, Languages and Programming, 32nd International Colloquium, ICALP05 (2005), pp. 677--689.
• 3: BOLLOBÁS, B. Random Graphs. Academic Press, Orlando, FL, 1985.
• 4: Fan Chung , Linyuan Lu, The diameter of sparse random graphs, Advances in Applied Mathematics, v.26 n.4, p.257-279, May 2001 [doi>10.1006/aama.2001.0720]
• 5: Colin Cooper , Alan Frieze, The cover time of sparse random graphs., Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 6: DÍAZ, J., PETIT, J., AND SERNA, M. Random geometric problems on {0; 1}2. Lecture Notes in Computer Science 1518 (1998).
• 7: ERDOS, P., AND RÉNYI, A. On random graphs. Publicationes Mathemticae (Debrecen) 6 (1959), 290--297.
• 8: James Allen Fill , Edward R. Scheinerman , Karen B. Singer-Cohen, Random intersection graphs when m= w(n): an equivalence theorem relating the evolution of the G(n, m, p) and G(n,P<>/italic>) models, Random Structures & Algorithms, v.16 n.2, p.156-176, March 2000 [doi>10.1002/(SICI)1098-2418(200003)16:2<156::AID-RSA3>3.0.CO;2-H]
• 9: FRAIGNIAUD, P. Small worlds as navigable augmented networks: Model, analysis, and validation. In Algorithms U ESA 2007 (2007), pp. 2--11.
• 10: Pierre Fraigniaud , Emmanuelle Lebhar , Zvi Lotker, Recovering the Long-Range Links in Augmented Graphs, Proceedings of the 15th international colloquium on Structural Information and Communication Complexity, June 17-20, 2008, Villars-sur-Ollon, Switzerland [doi>10.1007/978-3-540-69355-0_10]
• 11: GILBERT, E. N. Random graphs. The Annals of Mathematical Statistics 30, 4 (Dec. 1959), 1141--1144.
• 12: GILBERT, E. N. Random plane networks. Journal of the Society for Industrial and Applied Mathematics 9, 4 (Dec. 1961), 533--543.
• 13: Ashish Goel , Sanatan Rai , Bhaskar Krishnamachari, Sharp thresholds For monotone properties in random geometric graphs, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007441]
• 14: GUPTA, P., AND KUMAR, P. R. Critical power for asymptotic connectivity in wireless networks. In Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming (1998), 547--566.
• 15: 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]
• 16: MEESTER, R., PENROSE, M. D., AND SARKAR, A. The random connection model in high dimensions. Statistics & Probability Letters 35, 2 (1997), 145--153.
• 17: MEESTER, R., AND ROY, R. Continuum percolation. Cambridge Univesity Press, Cambridge, UK., 1996.
• 18: MILGRAM, S. The small world problem. Psychology today 2 (1967), 60--67.
• 19: NEWMAN, M. The Structure and Function of Complex Networks. SIAM Review 45, 2 (2003), 167--256.
• 20: NEWMAN, M., WATTS, D., AND STROGATZ, S. Random graph models of social networks. In Proc. Natl. Acad. Sci (2002), vol. 99, pp. 2566--2572.
• 21: Edgar M. Palmer, Graphical evolution: an introduction to the theory of random graphs, John Wiley & Sons, Inc., New York, NY, 1985
• 22: PENROSE, M. D. On a continuum percolation model. Advances in Applied Probability 23, 3 (Sep 1991), 536--556.
• 23: PENROSE, M. D. The longest edge of the random minimal spanning tree. The Annals of Applied Probability 7, 2 (1997), 340--361.
• 24: PENROSE, M. D. Random Geometric Graphs, vol. 5 of Oxford Studies in Probability. Oxford University Press, May 2003.
• 25: SINGER, K. B. Random intersection graphs. PhD thesis, Johns Hopkins University, 1995.
• 26: 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]
• 27: WATTS, D. J., AND STROGATZ, S. H. Collective dynamics of 'small-world' networks. Nature 393, 4 (June 1998), 440--442.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
bernoulli graphs, connectivity, distance graphs, random geometric graphs, small world