CS Distinguished Lecture Series: “A Walk in the Dark: Random Walks and Network Discovery”

Friday, February 15, 2013
Research Hall, Room 163
Don Towsley


We rely on a wide variety of digital networks in our daily lives, to provide a rich set of services in commerce, government, communications, and to feel connected. These networks include the Internet, the World Wide Web, on-line social networks such as Facebook, Twitter, etc., and cellular networks. They are large, complex, very richly structured, and constantly changing over time. Moreover, because of their size and complexity, very little is known about them.

In this talk we focus on the problem of how to discover the structure of these networks. Traditional methods for network discovery and exploration include crawling the network using breadth first search (BFS). We will show, however, that such methods introduce significant biases unless almost all of the network is crawled. Instead, we focus on random walks as a method for exploring the network. We will show that random walks can be used to solve a number of network discovery tasks including characterizing degree distributions, identifying important nodes, finding short paths, locating content, etc., while exploring only a very small portion of network. Last, we do this in the context of networks whose underlying graphs are either directed or undirected.

Speaker's Bio

Professor Towsley's research spans a wide range of activities from stochastic analyses of queueing models of computer and telecommunications to the design and conduct of measurement studies. He has performed some of the pioneering work on the exact and approximate analyses of parallel/distributed applications and architectures. More recently, he pioneered the area of network tomography and the use of fluid models for large networks. He has published extensively, with over 150 articles in leading journals.

PhD Comptuer Science, University of Texas (1975), BA Physics, University of Texas (1971). Professor Towsley first joined the faculty at the University of Massachuseets in the Department of Electrical and Computer Engineering in 1976 and moved to the Department of Computer Science in 1986. He was named University Distinguished Professor of Computer Science in 1998. Professsor Towsley was a Visiting Scientist at the IBM T.J. Watson Research Center, (1982-83, 2003), INRIA and AT&T Labs - Research (1996-97), and Cambridge Microsoft Research Lab (2004); a Visiting Professor at the Laboratoire MASI, Paris, (1989-90).