A Walk in the Dark: Random Walks and Network Discovery 

Abstract:

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, both in terms of their structure and what content they contain. In this talk we focus on two related problems: how do we discover underlying properties of these networks? and how do we discover content within them?  Traditional methods for network discovery 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. Moreover, as a means of content discovery, they are ery inefficient. Instead, we focus on random walks as a method for exploring and discovering content within the network. We illustrate how random walks solve a number of network discovery problems including characterizing degree distributions, and locating content, while exploring only a very small portion of network. 

Bio:

Don Towsley received a B.A. degree in physics and a Ph.D. degree in computer science, both from University of Texas. He is currently a Distinguished University Professor in the Department of Computer Science at the University of Massachusetts – Amherst. Professor Towsley has been a Visiting Scientist at AT&T Labs – Research,IBM Research, INRIA , Microsoft Research Cambridge, and the University of Paris 6.Dr. Towsley’s research interests include network measurement, modeling, and analysis. He serves on the editorial boards of Journal of the ACM and IEEE Journalof Selected Areas in Communications, and has served as Editor-in-Chief of the IEEE/ACM Transactions on Networking and on numerous editorial boards including those of IEEE Transactions on Communications and Performance Evaluation. He has been active on the program committees for numerous conferences including IEEE Infocom, ACM SIGCOMM, ACM SIGMETRICS, and IFIP Performance conferences for many years, and has served as Technical Program Co-Chair for ACM SIGMETRICS and IEEE INFOCOM, and IFIP Performance conferences. He has also served as Chair of the IFIP Working Group 7.3 on computer performance measurement, modeling, and analysis, and as an officer or advisor of ACM SIGMETRICS and ACM SIGCOMM. He is one of the founders of the Computer Performance Foundation.Dr. Towsley has received the 2007 IEEE Koji Kobayashi Computer and Communications Award , the 2007 ACM SIGMETRICS Achievement Award, the 2008 ACM SIGCOMM Award, the 1999 IEEE Communications Society William Bennett Award, and several conference and workshop best paper awards. He is also the recipient of the UMass Award for Outstanding Accomplishments in Research and Creative Activity, the University of Massachusetts Chancellor’s Medal and an Outstanding Research Award from the College of Natural Science and Mathematics at the University of Massachusetts. He has twice received IBM Faculty Fellowship Awards, and is a Fellow of the IEEE and the ACM.