Evolution and Devolution in Geometric Random Graphs

Speaker: Dr. Santosh S. Venkatesh

A mosaic process is formed by placing a small random set at each point in a collection of a large number of random points in the unit disc. From each point we draw a directed edge outward to every other point in the collection that lies within its random set. The mosaic thus induces a geometric random digraph on the collection of points. This setting can model a network of randomly placed sensors, each equipped with a limited, possibly anisotropic, communication capability. If, following establishment, vertices are extinguished at random times, we obtain a sanitized model of network devolution. Here vertex extinctions model node failures due to battery exhaustion. If the random sets forming the mosaic are sufficiently regular then, initially, a threshold function for graph connectivity is manifested at a critical rate of coverage by the small sets. Following establishment, as vertices are extinguished, the devolution of the graph with time is characterized by a succession of phase transitions at which isolated vertices appear, followed by the sudden appearance of sensory lacunae or dead spots, and, eventually, an abrupt breakdown in connectivity between survivors. I will show that these results can be explicated using elementary arguments in the classical Poisson paradigm.
These results are from joint work with Srisankar S. Kunniyur.


Santosh S. Venkatesh received the B.Tech. with Honors in Electrical Engineering from the Indian Institute of Technology, Bombay, in 1981, and the Ph.D. in Electrical Engineering from the California Institute of Technology, Pasadena, in 1986. On being informed to his surprise that graduate students actually have to leave some time, he joined the faculty of the Department of Electrical and Systems Engineering at the University of Pennsylvania where he is also a member of the David Mahoney Institute for Neurological Sciences. He has haunted the corridors at Penn since then excepting for visiting forays to the Helsinki Institute of Technology, Caltech, Bell Labs, Siemens, and Microsoft Research. His research interests are in probability, information, communication, learning, and security, though what he really likes doing is flipping coins. He was a recipient of the Lindback Award in 2004.

Presented On: April 20th, 2007
Click here to see the video