CATS-May-10-2013
Title
Reconstructing Latent Similarities in a Multiplex Social Network
Speaker
Alex Slivkins is a researcher at Microsoft Research Silicon Valley since 2007. He joined MSR-SV after a one-year postdoc at Brown University, where he was working with Eli Upfal. He received his Ph.D. in Computer Science from Cornell University, advised by Jon Kleinberg, after completing undergraduate studies at Caltech. His research interests lie in the design and analysis of algorithms, for domains such as machine learning, algorithmic economics, and social and technological networks. He has authored over 25 papers in top computer science conferences in several areas: theory&algorithms (FOCS,STOC,SODA,PODC), machine learning (COLT,ICML,NIPS), algorithmic economics (ACM-EC), and networking (SIGCOMM, INFOCOM). His work was recognized by ACM EC 2010 best paper award, and ACM PODC 2005 best student paper award.
Abstract
It is commonly assumed that individuals tend to be more similar to their friends than to strangers. Thus, we can view an observed social network as a noisy signal about the latent underlying "social space": the way in which individuals are (dis)similar. This naturally raises the inverse question: given a social network, how accurately can we reconstruct the social space?
We begin to address this problem formally. We assume that each category (e.g., geography, profession, hobbies) is characterized by a latent metric capturing (dis)similarities in this category, and gives rise to a separate social network: a random graph parameterized by this metric. The algorithm only observes the unlabeled union of these graphs, and reconstructs each metric with provably low distortion.
Joint work with Ittai Abraham (MSR-SV), Shiri Chechik (MSR-SV) and David Kempe (USC). Appeared in SODA 2013.