Advanced Networks Colloquium: Athina Markopoulou, "Sampling Online Social Networks"
Friday, September 23, 2011
1146 A.V. Williams Building
301 405 6579
Advanced Networks Colloquium
Sampling Online Social Networks
Electrical Engineering and Computer Science
University of California, Irvine
| video |
Online Social Networks (OSNs) have recently emerged as a new Internet killer-application and are of interest to a range of communities, ranging from computer science and engineering to social sciences. OSNs are widely studied today based on samples collected through measurement of publicly available information. In this talk, I will give an overview of our recent work on sampling online social networks.
First, I will describe a framework for obtaining a probability sample of users by crawling the friendship graph. I will provide practical recommendations including the choice of crawling technique, the use of online convergence diagnostics, and implementation issues. Second, I will introduce multigraph samplinga technique that exploits different relations between users to efficiently sample users, even when the friendship graph exhibits poor connectivity or slow mixing. Third, I will present the stratified weighted random walk (S-WRW)an efficient heuristic that preferentially crawls those nodes and edges that convey greater information pertaining to the target metric. Finally, I will report results from applying our techniques to real-life OSNs, such as Facebook and Last.FM, and from studying their characteristics, including user attributes and structural properties.
This work is joint with Mina Gjoka, Maciej Kurant, and Carter Butts at the University of California, Irvine and with Patrick Thiran at EPFL, Lausanne. Parts of this work appear in IEEE INFOCOM 2010, ACM SIGMETRICS 2011 and IEEE JSAC 2011.
Athina Markopoulou is an assistant professor in EECS at the University of California, Irvine. She received the Diploma degree in Electrical and Computer Engineering from the National Technical University of Athens, Greece, in 1996, and the Master's and Ph.D. degrees in Electrical Engineering from Stanford University, in 1998 and 2003 respectively. She has been a postdoctoral fellow at Sprintlabs (2003) and at Stanford (2004-2005), and a member of the technical staff at Arastra Inc. (2005). Her research interests include network coding, network measurement, network security and online social networks. She received the NSF CAREER award in 2008.