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).