This paper presents a simple framework, called WalkAbout, to infer a coarse view of connectivity in very large graphs; that is, identify well-connected “regions” with different edge densities and determine the corresponding inter- and intra- region connectivity. We leverage the transient behavior of many short random walks (RW) on a large graph that is assumed to have regions of varying edge density but whose structure is otherwise unknown. The key idea is that as RWs approach the mixing time of a region, the ratio of the number of visits by all RWs to the degree for nodes in that region converges to a value proportional to the average node degree in that region. Leveraging this indirect sign of connectivity enables our proposed framework to effectively scale with graph size.

Link to the full paper: http://onrg.cs.uoregon.edu/pub/CameraReadyPapers/cosn080f-motamedi.pdf

About Reza Rejaie

Reza Rejaie is currently an Associate Professor at the Department of Computer and Information Science at the University of Oregon. From October 1999 to March 2002, he was a Senior Technical Staff member at AT&T Labs-Research in Menlo Park, California. Reza has founded Oregon Network Research Group (ONRG) at the University of Oregon in 2004. Reza received a European Union Marie Curie Fellowship in 2009 and a NSF CAREER Award for his work on P2P streaming in 2005. Reza’s research in the area of congestion control, adaptive video streaming, video caching, P2P measurement, and P2P streaming have been widely cited. Reza has been the TPC chair for NOSSDAV’07, Global Internet ’07, MMCN’08 and MMCN’09, and also served on the editorial board of several journals, review panels and numerous technical program committees. He has been a senior member of both the ACM and IEEE since September 2006.

Reza received his M.S. and Ph.D. degrees in computer science from the University of Southern California(USC) in 1996 and 1999 respectively. During his graduate study at USC, he participated in several projects at Information Sciences Institute(ISI), the Computer Networks and Distributed Systems Research Laboratory and the Database Laboratory. He completed his B.S. degree in Electrical Engineering at Sharif University of Technology, Tehran, Iran, in 1991.

This event will be conducted in English