Luận án tiến sĩ - Đồ thị hình học ngẫu nhiên: Phân tích thuật toán

UNIVERSITY OF CALIFORNIA Los Angeles Random Geometric Graphs: An Algorithmic Perspective A dissertation submitted in partial satisfaction of the requirements for the degree Doctor of Philosophy in Computer Science by Chen Avin 2006 UMI Number: 3240866 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion.

® UMI UMI Microform 3240866 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.

Box 1346 Ann Arbor, MI 48106-1346 © Copyright by Chen Avin 2006 _ The dissertation of Chen Avin is approved. Mr Vogue Adnan Darwiche LE Deborah Estrin, Committee Co-chair Judea Pearl, Committee Co-chair University of California, Los Angeles 2006 il To my family 1H TABLE OF CONTENTS 1 Introduction.2 Random Geometric Graphs .3 Questions of Interest and Overview of Results .1 Random Walks in Random Geometric Graphs .2 Restricted Delaunay Triangulation in Random Geometric Oraph§S.3 Random Distance Graphs. 11 2 Random Walks on Random Geometric CGraphs.1 Markov chains and the Simple Random Walk .2 Mixing Time and the Spectral Gap (1—Àj) .3 Cover Time, Partial Cover Time and Blanket Time .5 Bounding The Cover Time via Resistance .3 Geo-dense Geometric Graphs .1 Geo-dense Random Geometric Graphs .4 The Mixing Time of Random Geometric Graphs .41 Bounding the Conductance of G(n,r) .2 Continuous Approximation of Conductance.5 The Cover Time of Random Geometric Graphs .1 The Cover Time and Resistance of Geometric Graphs.2 Cover Time and Resistance of G(n,r).3 The Threshold Width of Optimal Cover Time .4 Optimal Cover Time is not Monotone.5 Cover Time and Resistance of Deterministic Geometric Graphs 44 2.6 Notes and Related Work. ees 50 3 Efficient Restricted Delaunay Triangulation in Random Geomet- ric Graphs.

nà gà gà gà gà và Và 52 3.4 Properties of LocalDel(G) .1 Well-distributed Geometric Graphs .2 Bounding the number of messages.5 Notes and Related Work. es 68 4 Random Distance Graphs .2 Definitions and Statement of Results .1 Proof of Theorem 4.2 Proof of Theorem 4.3 Proof of Theorem 4.4 Proof of Theorem 4.4 Notes and Related Work. ee 84 Experimental Results. ee ee ee ee 86 5.2 Efficiency of Random Walk.1 Biased Random Walk.38 Quality of Random Walk.1 Partial Cover Quality.

cu uy và 91 5.2 Robustness to Dynamics. kg ko 97 vi LIST OF FIGURES 1. (C) typical D(n, g#) case for rr?<a<1,0<68 <r. 10 21 Unit flow for upper bound on the 2—dimension grid resistance .3 Approximating the Conductance in RGG.4 Tíu, 0) and the flow c between w and vin G(n,r) .0 Lower bound for Ry, on the (HT).1 Different Graphs over a set V of 50 random nodes in the unit square with r = 0.

(D) The edges in Del(V) that are longer than r (E) Local Del(G) where consistent edges are in dots and inconsistent edges are in solid lines.2 A case where edges {w, z} and {u,v} are consistent and intersect in LocalDel(G)).3 A disk D that must be included in the area disk(u, v, w)N(disk(u)U disk(v)) 0.4 An example where inconsistent edge {u, v} exist next to the border of the unit square 2. HQ ng gà và 63 3.5 Average number of messages in Algorithm 1 for different size ran- dom networks.1 Computing the conditional probability P({2, 7} | {k,¢}, {k,7}) .2 an area that is proportional to x? when local routing from i to j with w=d(t,J).1 An example of the temperature in an area with six random light SOUTCES 6k ee eh eh ee es QI h5 Comparing the histogram founded by the 80% random walk on the graph and the histogram of the real data from Figure 5.3 The progress of partial cover time as function of number of steps normalized to n for different graphs of size n =4096.4 Partial Cover time in increasing size of random network with same density ee Or Œt Partial Cover Time in random walks with increasing bias on ran- dom network 2. ee ee Hole size as a function of the number of steps normalized to n for đ(4096,r) with different radlir 2.7 The Partial Cover time required when the probability p of each node to fail is increasing. The result are for 4096 nodes networks .8 An example of a 4096 random network with 4 disaster areas.

We can see the creation of bottlenecks. 94 or to The Partial Cover time required when we increase the number of disaster areas in the network.10 Histogram of the expected number of visits to a node in a 80% cover random walk .000 + ee eee ne vi List oF NOTATION Auvw triangle Of U,U, Wo. cece eee cece nee n ence tenn cence eens 56 blanket time_. HQ HH ect been etn kh xa 20 B(n,p) Bernoulli random graph_.

1 Ce cover time of graph GÃ. HH nh hs. 17 Ca(c) partial cover time of fraction €. 18 Cuw commute tiMe.

eect eee eee een een kh ke 18 dữ, j) Euclidian distance between 4,7. cece cece teen ence eee 9 disk, (u) disk centered around œ with radius r. 55 disk(u, v, w) unique circumcircle over u,v and W. eect eee es 55 Del(G) Delaunay triangulation of a geometric graph G_.

53 D(n, 9) random distance graph. cece cence ence HH nhu kh xa 15 6(v) degree Of U oe cece cnet kh kh kh kh no need 14 Oavg average degree in the graph. 37 E(G) electrical network of Go. ccc ccc cece HH nh kh xa 22 hitting time 2.

ccc HH HH nent nena kh vờ 17 maximum hitting time. 18 random geometric graph.c cece eee HH nh ng va 27 k-fuzz of a grid of SỈZ© No. ccc eee een tenn hy. 44 the intersection of disk,(i) and đ¿sk„(j).

ccc cece eee ene eee nà kẻ 16 second largest eigenvalue in absolute vaÌue_. nh nhu và 14 1X set of neighbors of u including. eee ccc ete eee tne nh kh kh kh kế 55 edge probability 2. c ccc ccc cece Q nhuky 2 power of a flow €_.Q Q QQ nee nen n eee n een ennens 24 Poisson random graph_.

ng eee eens 14 CONGUCTANCE 2. ccc ceed eee tence tent nent beens 21 TACIUS 22. nent tener neenaeees 2 critical radius for connectÏVÌEV. cece cece eee eee nee ee 3 resistance.

eee eee eee ener tee ences ¬ 23 effective resistance between u and U. 23 Restricted Delaunay Graph of G 1. cece eee eee 53 THÌIXỈNE tIME 1. cee cence enn nett rte kh eens 16 the unit disk_.

"¬ eee e eee e ene eees 71 Voronoi diagram of a set of nodes W. 55 ACKNOWLEDGMENTS I could not have reached the end of this long, challenging path without the support and help of many people. First, I would like to thank my advisor Judea Pearl for his support and for allowing me the freedom to pursue my own interest. Despite difficult times, he was always there when I needed him and I’m thankful for that.

I would also like to thank my co-chair Deborah Estrin for introducing me to sensor networks and for her valuable feedback on my work. I thank the other member of my committee, Adnan Darwiche and Mark Hansen for their support and for interesting and enjoyable classes along the way. Many friends at UCLA with whom I worked and discussed my research made it possible for me to complete this work. In particular, I would like to thank Gunes Ercal who is a co-author and a friend for life and Carlos Brito who put me on the right track and taught me how research is being done.

Chapter 2 and 5 of this dissertation are based on joint work with Gunes and Carlos [AB04, AE05b, AE05a]. Thanks to other members in our windowless lab along the years: Blai Bonet, Mark Hopkins, Ilya Shpitser, and Shailesh Vaya, each has helped me in his own way along the road. The open door, good advice and friendship of Eli Gafni helped me to continue during my most difficult times and I am grateful for that. I would like to thanks Kaoru Mulvihill for being supportive and understanding, and for all her help.

I would not have started this journey without the encouragements of Rachel Ben-Eliyahu and Ran Giladi and without the financial support of the Department of Communication System Engineering at Ben-Gurion University, Israel. A special thought goes to Verra Morgan whom I met on my first day at UCLA, and who was ever-since a countless source of smiles, moral support and reminders to ”stay out of trouble”. To David, whom I also met during my first xi days at UCLA and who now he is my best friend: thank you for being there whenever I need you. Finally, I would like to thank my family who has always been the most im- portant part of my life.

To my late father Tzvi who never finished high school, but showed me the joy of learning and curiosity. To my late grandparents Yuda and Shlomit who inspired me with their knowledge and wisdom. You are always with me. To my mother Ilana who is always there to support me, in good and bad times and to my brothers and sisters Ayelet, Eran, Shira and Yagil for there unconditional love.

Most of all there is my own “little” family: To my wonderful kids, Itamar and Maya, you are the source of my power. What I have learned from them, and in particular from Itamar, is priceless and beyond what I could ever imagine, and this is just the beginning. And last, my wife, my love, Yehudit who has stood by me all the way and makes all of this possible. xủ VITA 1970 Born, Beer-Sheva, Israel., Communication Systems Engineering, Ben Gurion Uni- versity of The Negev, Beer Sheva, Israel., Computer Science, Ủniversity of California Los Angeles, Los Angeles, USA.

Fast and Efficient Restricted Delaunay Triangulation in Random Geo- metric Graphs. In Workshop on Combinatorial and Algorithmic Aspects of Net- working (CAAN-05), 2005. Identifiability of Path-Specific Effects In Proceedings Nineteenth International Joint Conference on Artificial Intelligence (IJCA1-05), pp 357-363, 2005 Avin, C. On The Cover Time of Random Geometric Graphs.

Automata, Languages and Programming, 82nd International Collo- quium (ICALP-05), pp 677-689, 2005. Bounds on the Mixing Time and Partial Cover of Ad-hoc xa and Sensor Networks. In Proceedings of the 2nd European Workshop on Wireless Sensor Networks (EWSN-05), pp 1-12, 2005. Efficient and Robust Query Processing in Dynamic En- vironments Using Random Walk Techniques.

In Proceedings of the third interna- tional symposium on Information processing in sensor networks (IPSN-04), pp 277-286, 2004., and Ben-Eliyahu R. Algorithms for Computing X-Minimal Models. In Proceedings of LPNMR-01 pp 322-335, 2001. XIV ABSTRACT OF THE DISSERTATION Random Geometric Graphs: An Algorithmic Perspective by Chen Avin Doctor of Philosophy in Computer Science University of California, Los Angeles, 2006 Professor Judea Pearl, Co-chair Professor Deborah Estrin, Co-chair A random geometric graph G(n,r) is a graph resulting from placing n points uniformly at random on the unit square (or on the unit disk) and connecting two points iff their Euclidean distance is at most the radius r(n).

Recently, this class of random graphs has gained relevance as a natural model for wireless ad-hoc and sensor networks. Investigating properties of these graphs can unearth properties of the real-life systems they model and allow for the design of efficient algorithms.