Luoyi Fu
ABSTRACT
This paper investigates the problem of optimally determining source-destination connectivity in random graphs. We consider the classic Erdos-Renyi (ER) random graph with $n$ nodes, where an edge independently exists between any two nodes with probability p. The problem examined is that of determining whether a given pair of nodes, a source S and a destination D, are connected by a path. Assuming that at each step one edge can be tested to see if it exists or not, we determine an optimal policy that minimizes the total expected number of steps. The optimal policy has several interesting features. In order to establish connectivity of S and D, a policy needs to check all edges on some path to see if they all exist, but to establish disconnectivity it has to check all edges on some cut to see if none of them exists. The optimal policy has the following form. At each step it examines the condensation multigraph formed by contracting each known connected component to a single node, and then checks an edge that is simultaneously on a shortest S-D path as well as in a minimum S-D cut. Among such edges, it chooses that which leads to the most opportunities for connection. Interestingly, the optimal strategy does not depend on p or n, even though the entire graph itself undergoes a sharp transition from disconnectivity to connectivity around p = ln n/n. The policy is efficiently implementable, requiring no more than 30 log2n operations to determine which edge to test next. The result also extends to some more general graphs.
- E. N. Gilbert, "Random Graphs", in Annals of Mathematical Statistics 30 (4), pp. 1141--1144, 1959.Google Scholar
Cross Ref
- P. Erdos, A. Renyi, "On Random Graphs. I", in Publicationes Mathematicae 6: pp. 290--297, 1959.Google Scholar
- P. Erdos, A. Renyi, "On the evolution of random graphs", in the Mathematical Institute of the Hungarian Academy of Sciences 5, pp. 17--61, 1960.Google Scholar
- P. Erdos, E. M. Palmer and R. W. Robinson, "Local Connectivity of A Random Graph", in J. of Graph Theory, Vol. 7, No. 4, pp. 411--417, 1983.Google ScholarCross Ref
- B. Bollobas, S. Janson and O. Riordan, "The Phase Transition in Inhomogeneous Random Graphs", in J. Random Structures and Algorithms, Vol. 31, No. 1, pp. 3--122, 2007. Google ScholarDigital Library
- G. Han and A. M. Makowski, "One-dimensional Geometric Random Graphs with Nonvanishing Densities: Part I: A Strong Zero-one Law for Connectivity", in J. IEEE. Trans. on Inform. Theory, Vol. 55, No. 12, pp. 5832--5839, 2009. Google ScholarDigital Library
- M. D. Penrose. "On K-connectivity for a Geometric Random Graph," Random Structure and Algorithms, Vol. 15, No. 2, pp. 145--164, Sept. 1999. Google ScholarDigital Library
- C. Hirsch, D. Neuhauser and V. Schmidt, "Connectivity of Random Geometric Graphs Related to Minimal Spanning Forests", in Advances in Applied Probability, Vol. 45, Issue 1, 2013.Google Scholar
- L. Devroye and N. Fraiman, "Connectivity of Inhomogeneous Random Graphs", in J. Random Structures and Algorithms, 2013.Google Scholar
- E. N. Gilbert, "Random Plane Networks," in J. SIAM, 9, pp. 533--543, Dec. 1961.Google Scholar
- M. D. Penrose, "The Longest Edge of the Random Minimal Spanning Tree," in The Annals of Probability, Vol. 7, No. 2, pp. 340--361, 1997.Google ScholarCross Ref
- P. Gupta and P. R. Kumar, "Critical Power for Asymptotic Connectivity in Wireless Networks," in Stochastic Analysis, Control, Optimization and Applications, pp. 547--566, Birkhauser, 1998.Google Scholar
- C. Bettstetter, "On the Minimum Node Degree and Connectivity of a Wireless Multihop Network", in Proc. of ACM MobiHoc, 2002. Google ScholarDigital Library
- F. Xue and P. R. Kumar, "The Number of Neighbors Needed for Connectivity of Wireless Networks," in Wireless Networks, Vol.10, No. 2, pp. 169--181, Mar. 2004. Google ScholarDigital Library
- F. Xue and P. R. Kumar, "On the Theta-coverage and Connectivity of Large Random Networks," in Joint Special Issue of IEEE Trans. on Inform. Theory and IEEE/ACM Trans.s on Netw. and Inform. Theory, pp. 2289--2399, Vol. 52, No. 6, June 2006.Google Scholar
- P. Balister, B. Bollobas, A. Sarkar and M. Walters, ''Connectivity of Random k-nearest-neighbour Graphs",in Advances in Applied Probability, Vol. 37, No. 1, pp.1--24, 2005.Google ScholarCross Ref
- O. Dousse, P. Mannersalo, P. Thiran, "Latency of Wireless Sensor Networks with Uncoordinated Power Saving Mechanisms," in Proc. of ACM MobiHoc'04, Roppongi, Japan, May 2004. Google ScholarDigital Library
- H. M. Ammari and S. K. Das, "Critical Density for Coverage and Connectivity in Three-dimensional Wireless Sensor Networks using Continuum Percolation," in IEEE Trans. Para. and Dis. System, Vol. 20, No. 6, pp. 872--885, 2009. Google ScholarDigital Library
- P. J. Wan and C. W. Yi, "Asymptotic Critical Transmission Radius for $k$-Connectivity in Wireless Ad Hoc Networks," in IEEE Trans. Infomation Theory, Vol. 56, No. 6, pp. 2867--2874, May 2010. Google ScholarDigital Library
- X. L. Bai, C. Zhang, D. Xuan and W. J. Jia, "Full-Coverage and k-Connectivity ($k=14,6$) Three Dimensional Networks", in Proc. of IEEE INFOCOM, Shanghai, China, July 2009.Google ScholarCross Ref
- X. Wang, X. Lin, Q. Wang and W. Luan, "Mobility Increases the Connectivity of Wireless Networks" in IEEE/ACM Trans. on Netw., Vol. 21, No. 2, pp. 440--454, Apr. 2012. Google ScholarDigital Library
Index Terms
- Optimal determination of source-destination connectivity in random graphs
Recommendations
Are We Connected? Optimal Determination of Source–Destination Connectivity in Random Networks
This paper investigates the problem of optimally determining source-destination connectivity in random networks. Viewing the network as a random graph, we start by investigating the Erdos–Renyi ER graph, as well as a structured graph where, interesting, ...
On the connectivity of random graphs from addable classes
A class A of graphs is called weakly addable (or bridge-addable) if for any G@?A and any two distinct components C"1 and C"2 in G, any graph that can be obtained by adding an edge between C"1 and C"2 is also in A. McDiarmid, Steger and Welsh (2006) ...
Hamiltonian and long paths in bipartite graphs with connectivity
AbstractLet G be a graph, ν ( G ) the order of G, κ ( G ) the connectivity of G and k a positive integer such that k ≤ ( ν ( G ) − 2 ) / 2. Then G is said to be k-extendable if it has a matching of size k and every matching of size k extends ...
Comments