Topological Properties of an Exponential Random Geometric Graph Process

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.

Authors:

• Yilun Shang

Keywords:

• random geometric graph
• autoregressive process
• degree
• connectivity
• Markovian
• wireless network.

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.