From: Jennifer Janzen (jennifer@microsoft.com)
Date: Tue Apr 20 2004 - 08:55:24 PDT
You are invited to attend...
************************************************************************
*****************************
WHO: David Kempe
AFFILIATION: University of Washington
TITLE: Maximizing the Spread of Influence in a Social
Network
WHEN: Wed 4/21/2004
WHERE: Microsoft Campus - Building 113 - 1021 Research Lecture
Room
TIME: 1:30PM-3:00PM
HOST: Dimitris Achlioptas
CONTACT: Jennifer Janzen (jennifer@microsoft.com)
NOTE: If attending, please e-mail your name and UW
affiliation to above contact
Directions are on the web by clicking on
"Visiting MSR" at http://www.research.microsoft.com
<http://www.research.microsoft.com/>
************************************************************************
******************************
ABSTRACT:
A social network - the graph of relationships and interactions within a
group of individuals - plays a fundamental role as a medium for the
spread of information, ideas, and influence among its members. An idea
or innovation will appear - for example, the use of cell phones among
college students, the adoption of a new drug within the medical
profession, or the rise of a political movement in an unstable society -
and it can either die out quickly or make significant inroads into the
population.
The resulting collective behavior of individuals in a social network has
a long history of study in sociology. Recently, motivated by
applications to word-of-mouth marketing, Domingos and Richardson
proposed the following optimization problem: allocate a given
"advertising" budget so as to maximize the (expected) number of
individuals who will have adopted a given product or behavior.
In this talk, we will investigate this question under the mathematical
models of influence studied by sociologists. We present and analyze a
simple approximation algorithm, and show that it guarantees to reach at
least a 1-1/e (roughly 63%) fraction of what the optimal solution can
achieve, under many quite general models. In addition, we experimentally
validate our algorithm, comparing it to several widely used heuristics
on a data set consisting of collaborations among scientists.
(joint work with Jon Kleinberg and Eva Tardos)
BIO:
David Kempe is a PostDoctoral researcher in the Department of Computer
Science & Engineering at the University of Washington, working with
Prof. Anna Karlin. Before coming to Seattle, he obtained a PhD from
Cornell University, under the guidance of Prof. Jon Kleinberg. His
research interests are centered around the dynamics of information flow
in networks and its connections with decentralized algorithms, and
lately, questions relating to auctions and mechanism design.
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Tue Apr 20 2004 - 08:55:56 PDT