Topological Properties of an Exponential Random Geometric Graph Process

Authors: Yilun Shang

Abstract:

In this paper we consider a one-dimensional random geometric graph process with the inter-nodal gaps evolving according to an exponential AR(1) process. The transition probability matrix and stationary distribution are derived for the Markov chains concerning connectivity and the number of components. We analyze the algorithm for hitting time regarding disconnectivity. In addition to dynamical properties, we also study topological properties for static snapshots. We obtain the degree distributions as well as asymptotic precise bounds and strong law of large numbers for connectivity threshold distance and the largest nearest neighbor distance amongst others. Both exact results and limit theorems are provided in this paper.

Keywords: random geometric graph, autoregressive process, degree, connectivity, Markovian, wireless network.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062986

References:

[1] Y. C. Cheng and T. Robertazzi, Critical connectivity phenomena in multihop radio models. IEEE Trans. on Commun., 37(1989) 770-777.
[2] F. Chung, S. Handjani and D. Jungreis, Generalizations of Polya-s urn problem. Annals of Combinatorics, 7(2003) 141-153.
[3] S. Cs┬¿org╦Øo and W.-B. Wu, On the clustering of independent uniform random variables. Random Structures and Algorithms, 25(2004) 396-420.
[4] J. D'─▒az, D. Mitsche and X. P'erez-Gim'enez, On the connectivity of dynamic random geometric graphs. Proc. of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 2008, 601-610.
[5] O. Dousse, P. Thiran and M. Hasler, Connectivity in ad hoc and hybrid networks. Proc. of IEEE Infocom, New York, 2002, 1079-1088.
[6] E. Godehardt and J. Jaworski, On the conncetivity of a random interval graph. Random Structures and Algorithms, 9 (1996) 137-161.
[7] B. Gupta, S. K. Iyer and D. Manjunath, Topological properties of the one dimensional exponential random geometric graph. Random Structures and Algorithms, 32(2008) 181-204.
[8] S. K. Iyer and D. Manjunath, Topological properties of random wireless networks. S¯adhan¯a, 31(2006) 117-139.
[9] K. K. Jose and R. N. Pillai, Geometric infinite divisiblility and its applications in autoregressive time series modeling. In: V. Thankaraj (Ed.)Stochastic Process and its Applications, Wiley Eastern, New Delhi, 1995.
[10] N. Karamchandani, D. Manjunath and S. K. Iyer, On the clustering properties of exponential random networks. IEEE Proc. of 6th WoWMoM, 2005, 177-182.
[11] N. Karamchandani, D. Manjunath, D. Yogeshwaran and S. K. Iyer, Evolving random geometric graph models for mobile wireless networks. IEEE Proc. of the 4th WiOpt, Boston, 2006, 1-7.
[12] V. Kurlin, L. Mihaylova and S. Maskell, How many randomly distributed wireless sensors are enough to make a 1-dimensional network connected with a given probability? Technical Report, arXiv:0710.1001v1
[cs.IT].
[13] A. J. Lawrance and P. A. W. Lewis, A new autoregressive time series model in exponential variables (NEAR(1)). Advances in Applied Probability, 13(1981) 826-845.
[14] D. Miorandi and E. Altman, Connectivity in one-dimensional ad hoc networks: A queueing theoretical approach. Wireless Networks, 12(2006) 573-587.
[15] S. Muthukrishnan and G. Pandurangan, The bin-covering technique for thresholding random geometric graph properties. Proc. of 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, 2005, 989- 998.
[16] M. D. Penrose, Random Geometric Graphs, Oxford University Press, 2003.
[17] S. M. Ross, Introduction to Probability Models. Academic Press, 2006.
[18] V. Seetha Lekshmi and K. K. Jose, Autoregressive processes with Pakes and geometric Pakes generalized Linnik marginals. Statist. Probab. Lett., 76(2006) 318-326.
[19] E. Seneta, Non-negative Matrices and Markov Chains. Springer-Verlag, 1981.
[20] Y. Shang, Exponential random geometric graph process models for mobile wireless networks. International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, Zhangjiajie, 2009, 56- 61.
[21] Y. Shang, Connectivity in a random interval graph with access points. Information Processing Letters, 109(2009), 446-449.
[22] Y. Shang, On the degree sequence of random geometric digraphs. Applied Mathematical Sciences, 4(2010) 2001-2012.
[23] Y. Shang, Laws of large numbers of subgraphs in directed random geometric networks. International Electronic Journal of Pure and Applied Mathematics, 2(2010) 69-79.