David Deutscher
Authored Publications
Google Publications
Other Publications
Sort By
Suggesting (More) Friends Using the Implicit Social Graph
Maayan Roth
Tzvika Barenholz
Assaf Ben-David
Guy Flysher
Ilan Horn
Ari Leichtberg
Ron Merom
International Conference on Machine Learning (ICML)(2011)
Preview abstract
Although users of online communication tools rarely categorize their contacts into groups such as "family", "co-workers", or "jogging buddies", they nonetheless implicitly cluster contacts, by virtue of their interactions with them, forming implicit groups. In this paper, we describe the implicit social graph which is formed by users' interactions with contacts and groups of contacts, and which is distinct from explicit social graphs in which users explicitly add other individuals as their "friends". We introduce an interaction-based metric for estimating a user's affinity to his contacts and groups. We then describe a novel friend suggestion algorithm that uses a user's implicit social graph to generate a friend group, given a small seed set of contacts which the user has already labeled as friends. We show experimental results that demonstrate the importance of both implicit group relationships and interaction-based affinity ranking in suggesting friends. Finally, we discuss two applications of the Friend Suggest algorithm that have been released as Gmail features.
View details
Suggesting Friends Using the Implicit Social Graph
Maayan Roth
Assaf Ben-David
Guy Flysher
Ilan Horn
Ari Leichtberg
Ron Merom
Proceedings of the 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining(2010)
Preview abstract
Although users of online communication tools rarely categorize their contacts into groups such as "family", "co-workers", or "jogging buddies", they nonetheless implicitly cluster contacts, by virtue of their interactions with them, forming implicit groups. In this paper, we describe the implicit social graph which is formed by users' interactions with contacts and groups of contacts, and which is distinct from explicit social graphs in which users explicitly add other individuals as their "friends". We introduce an interaction-based metric for estimating a user's affinity to his contacts and groups. We then describe a novel friend suggestion algorithm that uses a user's implicit social graph to generate a friend group, given a small seed set of contacts which the user has already labeled as friends. We show experimental results that demonstrate the importance of both implicit group relationships and interaction-based affinity ranking in suggesting friends. Finally, we discuss two applications of the Friend Suggest algorithm that have been released as Gmail Labs features.
View details
Can single knockouts accurately single out gene functions?
Preview abstract
Background
When analyzing complex biological systems, a major objective is localization of function – assessing how much each element contributes to the execution of specific tasks. To establish causal relationships, knockout and perturbation studies are commonly executed. The vast majority of studies perturb a single element at a time, yet one may hypothesize that in non-trivial biological systems single-perturbations will fail to reveal the functional organization of the system, owing to interactions and redundancies.
Results
We address this fundamental gap between theory and practice by quantifying how misleading the picture arising from classical single-perturbation analysis is, compared with the full multiple-perturbations picture. To this end we use a combination of a novel approach for quantitative, rigorous multiple-knockouts analysis based on the Shapley value from game theory, with an established in-silico model of Saccharomyces cerevisiae metabolism. We find that single-perturbations analysis misses at least 33% of the genes that contribute significantly to the growth potential of this organism, though the essential genes it does find are responsible for most of the growth potential. But when assigning gene contributions for individual metabolic functions, the picture arising from single-perturbations is severely lacking and a multiple-perturbations approach turns out to be essential.
Conclusion
The multiple-perturbations investigation yields a significantly richer and more biologically plausible functional annotation of the genes comprising the metabolic network of the yeast.
View details
AI System Designs for the First RTS-Game AI Competition
Michael Buro
James Bergsma
Timothy Furtak
Frantisek Sailer
David Tom
Nick Wiebe
GAMEON-NA'2006, Eurosis, pp. 44-48
Preview abstract
Real-time strategy (RTS) games are complex decision
domains which require quick reactions as well as strategic planning. In this paper we describe the first RTS
game AI tournament, which was held in June 2006, and
the programs that participated.
View details
Multiple knockout analysis of genetic robustness in the yeast metabolic network
Preview abstract
Genetic robustness characterizes the constancy of the phenotype in face of heritable perturbations. Previous investigations have used comprehensive single and double gene knockouts to study gene essentiality and pairwise gene interactions in the yeast Saccharomyces cerevisiae. Here we conduct an in silico multiple knockout investigation of a flux balance analysis model of the yeast's metabolic network. Cataloging gene sets that provide mutual functional backup, we identify sets of up to eight interacting genes and characterize the 'k robustness' (the depth of backup interactions) of each gene. We find that 74% (360) of the metabolic genes participate in processes that are essential to growth in a standard laboratory environment, compared with only 13% previously found to be essential using single knockouts. The genes' k robustness is shown to be a solid indicator of their biological buffering capacity and is correlated with both the genes' environmental specificity and their evolutionary retention.
View details
