Abstract: 

In this talk, we will consider two problems in online social network analysis. First, we consider an algorithmic problem regarding visualizing the connection between two individuals in a large social network.  We introduce the "connection subgraph" as a small subgraph that best captures the relationship between the pair, and give algorithms for finding and displaying this subgraph.  And second, we give an experimental and theoretical analysis of the importance of geography in the formation of an online social network.  We show that previous models connecting probability of friendship to geographic location do not satisfactorily explain a large online social network. We present a new model that matches experimental observations from the network, and show a theorem regarding the nature of paths within the model.

Biography:   

Andrew Tomkins is a senior research scientist at Yahoo! Research. His research interests lie in measurement, modeling, algorithms, and analytics for large heterogeneous datasets like the World Wide Web. Prior to joining Yahoo!, Andrew spent 8 years at IBM's Almaden Research Center, where he managed the information management principles group and served as Chief Scientist of the Web Fountain project.  He has published over fifty technical papers, including two best paper awards from the World Wide Web conference.  He also serves on various program committees and editorial boards. Andrew received his PhD in Computer Science from Carnegie Mellon University in 1997.