Bureaucrats, editor, Administrators
373
edits
Changes
no edit summary
== 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.
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.