From: Paul Beame (beame@cs.washington.edu)
Date: Wed Jan 14 2004 - 16:05:12 PST
COLLOQUIUM
SPEAKER: David Kempe, Cornell University
TITLE: Maximizing the Spread of Influence in a Social Network
DATE: Thursday, January 15, 2004
TIME: 3:30 pm
PLACE: EE-105
HOST: Anna Karlin
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).
Refreshments served in the room prior to the talk.
*NOTE* This lecture will be broadcast live via the Internet. See
http://www.cs.washington.edu/news/colloq.info.html for more information.
Email: talk-info@cs.washington.edu
Info: http://www.cs.washington.edu
The University of Washington is committed to providing access, equal
opportunity and reasonable accommodation in its sevices, programs,
activities, education and employment for individuals with disabilities.
To request disability accommodation, contact the Disability Services
Office at least ten days in advance of the event at: (206) 543-6450/V,
(206) 543-6452/TTY, (206) 685-3885/FAX, or access@u.washington.edu.
_______________________________________________
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 : Wed Jan 14 2004 - 16:05:28 PST