Mining the network value of customers.
One of the major applications of data mining is in helping companies determine which potential customers to market to. If the expected profit from a customer is greater than the cost of marketing to her, the marketing action for that customer is executed. So far, work in this area has considered only the intrinsic value of the customer (i.e, the expected profit from sales to her). We propose to model also the customer's network value: the expected profit from sales to other customers she may influence to buy, the customers those may influence, and so on recursively. Instead of viewing a market as a set of independent entities, we view it as a social network and model it as a Markov random field. We show the advantages of this approach using a social network mined from a collaborative filtering database. Marketing that exploits the network value of customers---also known as viral marketing---can be extremely effective, but is still a black art. Our work can be viewed as a step towards providing a more solid foundation for it, taking advantage of the availability of large relevant databases.
INTRODUCTION
Direct marketing is one of the major applications of KDD.
In contrast to mass marketing, where a product is promoted
indiscriminately to all potential customers, direct marketing
attempts to rst select the customers likely to be protable,
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
and market only to those [19]. Data mining plays a key role
in this process, by allowing the construction of models that
predict a customer's response given her past buying behavior
and any available demographic information [29]. When suc-
cessful, this approach can signicantly increase prots [34].
One basic limitation of it is that it treats each customer
as making a buying decision independently of all other cus-
tomers. In reality, a person's decision to buy a product is
often strongly in
uenced by her friends, acquaintances, business
partners, etc. Marketing based on such word-of-mouth
networks can be much more cost-eective than the more conventional
variety, because it leverages the customers themselves
to carry out most of the promotional eort. A classic
example of this is the Hotmail free email service, which grew
from zero to 12 million users in 18 months on a minuscule
advertising budget, thanks to the inclusion of a promotional
message with the service's URL in every email sent using
it [23]. Competitors using conventional marketing fared far
less well. This type of marketing, dubbed viral marketing
because of its similarity to the spread of an epidemic, is now
used by a growing number of companies, particularly in the
Internet sector. More generally, network eects (known in
the economics literature as network externalities) are of critical
importance in many industries, including notably those
associated with information goods (e.g., software, media,
telecommunications, etc.) [38]. A technically inferior product
can often prevail in the marketplace if it better leverages
the network of users (for example, VHS prevailed over Beta
in the VCR market).
Ignoring network eects when deciding which customers
to market to can lead to severely suboptimal decisions. In
addition to the intrinsic value that derives from the purchases
she will make, a customer eectively has a network
value that derives from her in
uence on other customers. A
customer whose intrinsic value is lower than the cost of marketing
may in fact be worth marketing to when her network
value is considered. Conversely, marketing to a protable
customer may be redundant if network eects already make
her very likely to buy. However, quantifying the network
value of a customer is at rst sight an extremely di-cult un-
dertaking, and to our knowledge has never been attempted.
A customer's network value depends not only on herself,
but potentially on the conguration and state of the entire
network. As a result, marketing in the presence of strong
network eects is often a hit-and-miss aair. Many startup
companies invest heavily in customer acquisition, on the basis
that this is necessary to \seed" the network, only to face
bankruptcy when the desired network eects fail to materi-
alize. On the other hand, some companies (like Hotmail and
the ICQ instant messenger service) are much more successful
than expected. A sounder basis for action in network-driven
markets would thus have the potential to greatly reduce the
risk of companies operating in them.
We believe that, for many of these markets, the growth
of the Internet has led to the availability of a wealth of
data from which the necessary network information can be
mined. In this paper we propose a general framework for
doing this, and for using the results to optimize the choice
of which customers to market to, as well as estimating what
customer acquisition cost is justied for each. Our solution
is based on modeling social networks as Markov random
elds, where each customer's probability of buying is a
function of both the intrinsic desirability of the product for
the customer and the in
uence of other customers. We then
focus on collaborative ltering databases as an instance of a
data source for mining networks of in
uence from. We apply
our framework to the domain of marketing motion pictures,
using the publicly-available EachMovie database of 2.8 million
movie ratings, and demonstrate its advantages relative
to traditional direct marketing. The paper concludes with a
discussion of related work and a summary of contributions
and future research directions.
2. MODELING MARKETS AS SOCIAL
Consider a set of n potential customers, and let X i be a
Boolean variable that takes the value 1 if customer i buys the
product being marketed, and 0 otherwise. In what follows
we will often slightly abuse language by taking X i to \be"
the ith customer. Let the neighbors of X i be the customers
which directly in
uence
Xng. In other words, X i is independent
of
the customers whose value (i.e., whether they have bought
the product) is known (unknown), and let N u
Assume the product is described by a set of attributes
be a variable representing the marketing
action that is taken for customer i. For example, M i
could be a Boolean variable, with M the customer is
oered a given discount, and M Alternately,
could be a continuous variable indicating the size of the
discount oered, or a nominal variable indicating which of
several possible actions is taken. Let Mng.
Then, for all
C(N
C(N
C(N u
where C(N u
is the set of all possible congurations of the
unknown neighbors of X i (i.e., the set of all possible 2 jN u
assignments of 0 and 1 to them). Following Pelkowitz [33],
we approximate P (N u by its maximum entropy
estimate given the marginals P (X
This yields 1
C(N
Y
(2)
The set of variables X u , with joint probability conditioned
on X k , Y and M described by Equation 2, is an instance
of a Markov random eld [2, 25, 7]. Because Equation 2
expresses the probabilities P as a function of
themselves, it can be applied iteratively to nd them, starting
from a suitable initial assignment. This procedure is
known as relaxation labeling, and is guaranteed to converge
to locally consistent values as long as the initial assignment
is su-ciently close to them [33]. A natural choice for initialization
is to use the network-less probabilities
Notice that the number of terms in Equation 2 is exponential
in the number of unknown neighbors of X i . If this
number is small (e.g., 5), this should not be a problem; oth-
erwise, an approximate solution is necessary. A standard
method for this purpose is Gibbs sampling [16]. An alternative
based on an e-cient k-shortest-path algorithm is proposed
in Chakrabarti et al. [6].
Given N i and Y, X i should be independent of the marketing
actions for other customers. Assuming a naive Bayes
model for X i as a function of N i ,
Y
Y
where
corresponding net-
work-less probabilities are
Given Equation 3, in order to
compute Equation 2 we need to know only the following
probabilities, since all terms reduce to them: P (X
k. With the exception
of P (X i jN i ), all of these are easily obtained in one pass
through the data by counting (assuming the Yk are discrete
or have been pre-discretized; otherwise a univariate model
can be t for each numeric Yk ). The form of P (X
on the mechanism by which customers in
uence each
other, and will vary from application to application. In the
next section we focus on the particular case where X is the
set of users of a collaborative ltering system.
For simplicity, assume that M is a Boolean vector (i.e.,
only one type of marketing action is being considered, such
as oering the customer a given discount). Let c be the
cost of marketing to a customer (assumed constant), r0 be
the revenue from selling the product to the customer if no
marketing action is performed, and r1 be the revenue if marketing
is performed. r0 and r1 will be the same unless the
1 The same result can be obtained by assuming that the X j
are independent given X k , Y and M.
marketing action includes oering a discount. Let f 1
i (M) be
the result of setting M i to 1 and leaving the rest of M un-
changed, and similarly for f 0
(M). The expected lift in prot
from marketing to customer i in isolation (i.e., ignoring her
eect on other customers) is then [8]
Let M0 be the null vector (all zeros). The global lift in
prot that results from a particular choice M of customers
to market to is then
the number of 1's in M. Our goal is to nd the assignment
of values to M that maximizes ELP. In general, nding the
optimal M requires trying all possible combinations of assignments
to its components. Because this is intractable, we
propose using one of the following approximate procedures
instead:
Single pass For each i, set M
> 0, and set M
Greedy search Set through the M i 's, setting
each M i to 1 if ELP (X
Y;M). Continue looping until there are no changes
in a complete scan of the M i 's. The key dierence between
this method and the previous one is that here
later changes to the M i 's are evaluated with earlier
changes to the M i 's already in place, while in the previous
method all changes are evaluated with respect
to M0 .
Hill-climbing search Set
(M))g. Now set M i 2
(M)))g. Repeat
until there is no i for which setting M
ELP.
Each method is computationally more expensive than the
previous one, but potentially leads to a better solution for
(i.e., produces a higher ELP).
The intrinsic value of a customer is given by Equation 4.
The total value of a customer (intrinsic plus network) is the
ELP obtained by marketing to her: ELP (X
(M)). The customer's network value is the
dierence between her total and intrinsic values. Notice
that, in general, this value will depend on which other customers
are being marketed to, and which others have already
bought the product.
Suppose now that M i is a continuous variable, that we
can choose to incur dierent marketing costs for dierent
customers, and that there is a known relationship between
In other words, suppose that we can increase
a customer's probability of buying by increasing the
amount spent in marketing to her, and that we can estimate
how much needs to be spent to produce a given increase in
buying probability. The optimal customer acquisition cost
for customer i is then the value of c i that maximizes her total
value
jMjc replaced by
Equation 5.
3. MINING SOCIAL NETWORKS FROM
COLLABORATIVE FILTERING
DATABASES
Arguably, a decade ago it would have been di-cult to
make practical use of a model like Equation 2, because
of the lack of data to estimate the in
uence probabilities
Fortunately, the explosion of the Internet has
drastically changed this. People in
uence each other online
(and leave a record of it) through postings and responses to
newsgroups, review and knowledge-sharing sites like epin-
ions.com, chat rooms and IRC, online game playing and
MUDs, peer-to-peer networks, email, interlinking of Web
pages, etc. In general, any form of online community is a
potentially rich source of data for mining social networks
from. (Of course, mining these sources is subject to the
usual privacy concerns; but many sources are public infor-
mation.) In this paper we will concentrate on a particularly
simple and potentially very eective data source: the collaborative
ltering systems widely used by e-commerce sites
(e.g., amazon.com) to recommend products to consumers.
In a collaborative ltering system, users rate a set of items
(e.g., movies, books, newsgroup postings, Web pages), and
these ratings are then used to recommend other items the
user might be interested in. The ratings may be implicit
(e.g., the user did or did not buy the book) or explicit (e.g.,
the user gives a rating of zero to ve stars to the book,
depending on how much she liked it). Many algorithms have
been proposed for choosing which items to recommend given
the incomplete matrix of ratings (see, for example, Breese
et al. [3]). The most widely used method, and the one that
we will assume here, is the one proposed in GroupLens, the
project that originally introduced quantitative collaborative
ltering [35]. The basic idea in this method is to predict a
user's rating of an item as a weighted average of the ratings
given by similar users, and then recommend items with high
predicted ratings. The similarity of a pair of users (i; j) is
measured using the Pearson correlation coe-cient:
(R ik R i )(R jk R j
(R ik R i
(R jk R j
where R ik is user i's rating of item k, R i is the mean of user
i's ratings, likewise for j, and the summations and means
are computed over the items k that both i and j have rated.
Given an item k that user i has not rated, her rating of it is
then predicted as
(R jk R j
is a normalization factor, and
N i is the set of n i users most similar to i according to
Equation 6 (her neighbors). In the limit, N i can be the
entire database of users, but for reasons of noise robustness
and computational e-ciency it is usually much smaller (e.g.,
5). For neighbors that did not rate the item, R jk is set
to R j .
The key advantage of a collaborative ltering database
as a source for mining a social network for viral marketing
is that the mechanism by which individuals in
uence each
other is known and well understood: it is the collaborative
ltering algorithm itself. User i in
uences user j when j
sees a recommendation that is partly the result of i's rating.
Assuming i and j do not know each other in real life (which,
given that they can be anywhere in the world, is likely to
be true), there is no other way they can substantially inuence
each other. Obviously, a user is subject to many
in
uences besides that of the collaborative ltering system
(including the in
uence of people not on the system), but
the uncertainty caused by those in
uences is encapsulated
to a rst degree of approximation in P (X
R ik ), the probability
that a user will purchase an item given the rating the
system predicts for her. It is also reasonable to assume that
an individual would not continue to use a collaborative l-
tering system if she did not nd its recommendations useful,
and therefore that there is a causal connection (rather than
simply a correlation) between the recommendations received
and the purchases made.
To extract a social network model from a collaborative l-
tering database, we view an item as a random sample from
the space (X; Y), where Y is a set of properties of the item
(assumed available), and X i represents whether or not user
rated the item. For simplicity, we assume that if a user
rates an item then she bought it, and vice-versa; removing
this assumption would be straightforward, given the relevant
data. The prior P (X i ) can then be estimated simply as the
fraction of items rated by user i. The conditional probabilities
can be obtained by counting the number
of occurrences of each value of Yk (assumed discrete or pre-
discretized) with each value of X i . Estimating
requires a data collection phase in which users to market
to are selected at random and their responses are recorded
(both when being marketed to and not). P (M i jX i ) can be
estimated individually for each user, or (requiring far less
data) as the same for all users, as done in Chickering and
Heckerman [8]. If the necessary data is not available, we
propose setting P (M i jX i ) using prior knowledge about the
eectiveness of the type of marketing being considered, given
any demographic information available about the users. (It
is also advisable to test the sensitivity of the outcome to
trying a range of values.)
The set of neighbors N i for each i is the set of neighbors
of the corresponding user in the collaborative ltering sys-
tem. If the ratings are implicit (i.e., yes/no), a model for
naive Bayes model, as we have assumed
for P (Yk jX i )) can be t directly to the observed X vectors.
If explicit ratings are given (e.g., zero to ve stars), then
we know that X i depends on N i solely through ^
predicted rating according to Equation 7 (for readability,
we will omit the item indexes k). In other words, X i is
conditionally independent of N
R i . If the neighbors'
ratings are known, ^
R i is a deterministic function of N i given
by Equation 7, with determining whether the contribution
of the jth neighbor is R j R j or 0 (see discussion
following Equation 7). If the ratings of some or all neighbors
are unknown (i.e., the ratings that they would give if
they were to rate the item), we can estimate them as their
expected values given the item's attributes. In other words,
the contribution of a neighbor with unknown rating will be
(R j jY) can be estimated using a naive
Bayes model (assuming R j only takes on a small number of
dierent values, which is usually the case). Let ^
the value of ^
obtained in this way. Then, treating this as
a deterministic value,
Z Rmax
R min
All that remains is to estimate P (X
R i ). This can be
viewed as a univariate regression problem, with ^
R i as the
input and P (X
as the output. The most appropriate
functional form for this regression will depend on the observed
data. In the experiments described below, we used
a piecewise-linear model for P (X
obtained by dividing
R i 's range into bins, computing the mean ^
for each bin, and then estimating P (X
for an arbitrary
R i by interpolating linearly between the two nearest means.
Given a small number of bins, this approach can t a wide
variety of observations relatively well, with little danger of
overtting.
Notice that the technical denition of a Markov random
eld requires that the neighborhood relation be symmetric
(i.e., if i is a neighbor of j, then j is also a neighbor of i),
but in a collaborative ltering system this may not be the
case. The probabilistic model obtained from it in the way
described will then be an instance of a dependency network,
a generalization of Markov random elds recently proposed
by Heckerman et al. [17]. Heckerman et al. show that Gibbs
sampling applied to such a network denes a joint distribution
from which all probabilities of interest can be computed.
While in our experimental studies Gibbs sampling and relaxation
labeling produced very similar results, the formal
derivation of the properties of dependency networks under
relaxation labeling is a matter for future research.
4. EMPIRICAL STUDY
We have applied the methodology described in the previous
sections to the problem of marketing motion pictures,
using the EachMovie collaborative ltering database (www.-
research.compaq.com/src/eachmovie/). EachMovie contains
2.8 million ratings of 1628 movies by 72916 users, gathered
between January 29, 1996 and September 15, 1997 by
the eponymous recommendation site, which was run by the
DEC (now Compaq) Systems Research Center. EachMovie
is publicly available, and has become a standard database
for evaluating collaborative ltering systems (e.g., Breese at
al. [3]). Motion picture marketing is an interesting application
for the techniques we propose because the success of a
movie is known to be strongly driven by word of mouth [12].
EachMovie is composed of three databases: one containing
the ratings, one containing demographic information
about the users (which we did not use), and one containing
information about the movies. The latter includes the
movie's title, studio, theater and video status (old or cur-
rent), theater and video release dates, and ten Boolean attributes
describing the movie's genre (action, animation,
art/foreign, classic, comedy, drama, family, horror, romance,
and thriller; a movie can have more than one genre). The
movie's URL in the Internet Movie Database (www.imdb.-
com) is also included. This could be used to augment the
movie description with attributes extracted from the IMDB;
we plan to do so in the future. The ratings database contains
an entry for each movie that each user rated, on a scale of
zero to ve stars, and the time and date on which the rating
was generated.
The collaborative ltering algorithm used in EachMovie
has not been published, but we will assume that the algorithm
described in the previous section is a reasonable
approximation to it. This assumption is supported by the
observation that, despite their variety in form, all the many
collaborative ltering algorithms proposed attempt to capture
essentially the same information (namely, correlations
between users).
The meaning of the variables in the EachMovie domain
is as follows: X i is whether person i saw the movie being
considered. Y contains the movie attributes. R i is the rating
(zero to ve stars) given to the movie by person i. For
simplicity, throughout this section we assume the ^
R i 's are
centered at zero (i.e., R i has been subtracted from ^
Equation 7).
4.1 The Model
We used the ten Boolean movie
genre attributes. Thus P (YjX i ) was in essence a model of
a user's genre preferences, and during inference two movies
with the same genre attributes were indistinguishable. The
network consisted of all people who had rated at least ten
movies, and whose ratings had non-zero standard deviation
(otherwise they contained no useful information). Neighbor
weights determined using a modied Pearson
correlation coe-cient, which penalized the correlation
by 0.05 for each movie less than ten that both X i and X j
had rated. This correction is commonly used in collaborative
ltering systems to avoid concluding that two users
are very highly correlated simply because they rated very
few movies in common, and by chance rated them similarly
[18]. The neighbors of X i were the 's for which W ji was
highest. With n i =5, a number we believe provides a reason-able
tradeo between model accuracy and speed, the average
W ji of neighbors was 0.91. Repeating the experiments
described below with produced no sig-
nicant change in model accuracy, and small improvements
in prot. Interestingly, the network obtained in each case
was completely connected (i.e., it contained no isolated sub-
graphs).
As discussed above, the calculation of P (X
requires estimating P (X
and P (R simply the fraction of movies X i
rated. We used a naive Bayes model for P (R
(R j jY), and P (X i ) were all smoothed using an m-estimate
[5] with m=1 and the population average as the prior. We
did not know the true values of P (M i jX i ). We expected
marketing to have a larger eect on a customer who was
already inclined to see the movie, and thus we set the probabilities
so as to obtain
where  > 1 is a parameter that we varied in the experiments
described below. 2 As described in the previous sec-
To fully specify P (M i jX i ) we used the additional constraint
that the values of 0.20.61
R

Figure

1: Empirical distribution of ^
R i and X i given
R i .
tion,
modeled using a piecewise linear func-
tion. We measured P (X
for each of nine bins, whose
boundaries were 5.0, 2.0, 1.0, 0.5, 0.1, 0.1, 0.5, 1.0,
2.0, and 5.0. Note that while R i must be between 0 and 5,
R i is a weighted sum of the neighbors' dierence from their
average, and thus may range from 5 to 5. We also had a
zero-width bin located at ^
Movies were seen with low
probability (1{5%), and thus there was a high probability
that a movie had not been rated by any of X i 's neighbors. In
the absence of a rating, a neighbor's contribution to ^
zero. 84% of the samples fell into this zero bin. Bin boundaries
were chosen by examination of the distribution of data
in the training set, shown in Figure 1. ^
unlikely to
deviate far from 0, for the reasons given above. We used
narrow bins near ^
to obtain higher accuracy in this
area, which contained a majority of the data (96.4% of the
data fell between 0.5 and 0.5). To combat data sparseness,
both
and the per-bin mean ^
R i were smoothed for
each bin using an m-estimate with m=1 and the population
average as the prior.
Initially, we expected P (X
increase monotonically
R i . The actual shape, shown in Figure 1, shows increasing
signicantly away from 0
in either direction. This shape is due to a correlation between
and the popularity of a movie: for a popular
R i is more likely to deviate further from zero and
more likely to be 1. Note, however, that
is indeed monotonically increasing in the [ 0:1; 0:1] inter-
val, where the highest density of ratings is. Furthermore,
4.2 The Data
While the EachMovie database is large, it has problems
which had to be overcome. The movies in the database
which were in theaters before January 1996 were drawn
from a long time period, and so tended to be very well
known movies. Over 75% (2.2 million) of the ratings were
on these movies. In general, the later a movie was released,
the fewer ratings and thus the less information we had for
it. We divided the database into a training set consisting
of all ratings received through September 1, 1996, and a
test set consisting of all movies released between September
1, 1996 and December 31, 1996, with the ratings received
we used it was always possible to satisfy Equation 9 and this
constraint simultaneously.
for those movies any time between September 1, 1996 and
the end of the database. Because there was such a large
dierence in average movie popularity between the early
movies and the later ones, we further divided the training
set into two subsets: S old , containing movies released before
January 1996 (1.06 million votes), and Srecent , containing
movies released between January and September 1996 (90k
votes). The average movie viewership of S old was 5.6%, versus
1.4% for Srecent . Since 92% of the training data was in
old , we could not aord to ignore it. However, in terms of
the probability that someone rates a movie, the test period
could be expected to be much more similar to Srecent . Thus,
we trained using all training data, then rescaled P (X i ) and
using Srecent , and smoothed these values using
an m-estimate with m=1 and the distribution on the full
training set as the prior.
Many movies in the test set had very low probability (36%
were viewed by 10 people or less, and 48% were viewed by
20 people or less, out of over 20748 people 3 ). Since it is not
possible to model such low probability events with any reli-
ability, we removed all movies which were viewed by fewer
than 1% of the people. This left 737,579 votes over 462
movies for training, and 3912 votes over 12 movies for test-
ing.
learned
using only these movies. However, because the EachMovie
collaborative ltering system presumably used all movies,
we used all movies when simulating it (i.e., when computing
similarities (Equation 6), selecting neighbors, and predicting
ratings (Equation 7)).
A majority of the people in the EachMovie database provided
ratings once, and never returned. These people affected
the predicted ratings ^
R i seen by users of EachMovie,
but because they never returned to the system for queries,
their movie viewing choices were not aected by their neigh-
bors. We call these people inactive. A person was marked as
inactive if there were more than  days between her last rating
and the end of the training period. In our tests, we used
a  of 60, which resulted in 11163 inactive people. Inactive
people could be marketed to, since they were presumably
still watching movies; they were just not reporting ratings
to EachMovie. If an inactive person was marketed to, she
was assumed to have no eect on the rest of the network.
4.3 Inference and Search
Inference was performed by relaxation labeling, as described
in Section 2. This involved iteratively re-estimating
probabilities until they all converged to within a threshold
(We used
We maintained a queue of nodes whose
probabilities needed to be re-estimated, which initially contained
all nodes in the network. Each X i was removed from
the queue in turn, and its probability was re-estimated using
Equation 2. If P (X i jX k ; Y;M) had changed by more than
, all nodes that X i was a neighbor of that were not already
in the queue were added to it. Note that the probabilities
of nodes corresponding to inactive people only needed to be
computed once, since they are independent of the rest of the
network.
The computation of Equation 2 can be sped up by noting
that, after factoring, all terms involving the Yk 's are constant
throughout a run, and so these terms and their com-
3 This is the number of people left after we removed anyone
who rated fewer than ten movies, rated movies only after
September 1996, or gave the same rating to all movies.
binations only need to be computed once. Further, since in
a single search step only one M i changes, most of the results
of one step can be reused in the next, greatly speeding
up the search process. With these optimizations, we were
able to measure the eect of over 10,000 single changes in
per second, on a 1 GHz Pentium III machine. In preliminary
experiments, we found relaxation labeling carried
out this way to be several orders of magnitude faster than
Gibbs sampling; we expect that it would also be much faster
than the more e-cient version of Gibbs sampling proposed
in Heckerman et al. [17]. 4 The relaxation labeling process
typically converged quite quickly; few nodes ever required
more than a few updates.
4.4 Model Accuracy
To test the accuracy of our model, we computed the estimated
probability for each person X i with
We measured the correlation between
this and the actual value of X i in the test set, over all movies,
over all people. 5 (Note that, since the comparison is with
test set values, we did not expect to receive ratings from
inactive people, and therefore P (X them.) The
resulting correlation was 0.18. Although smaller than desir-
able, this correlation is remarkably high considering that the
only input to the model was the movie's genre. We expect
the correlation would increase if a more informative set of
movie attributes Y were used.
4.5 Network Values
For the rst movie in the test set (\Space Jam"), we measured
the network value for all 9585 active people 6 in the
following scenario (see Equations 4 and 9):
Figure 2 shows the 500
highest network values (out of 9585) in decreasing order.
The unit of value in this graph is the average revenue that
would be obtained by marketing to a customer in isolation,
without costs or discounts. Thus, a network value of 20 for
a given customer implies that by marketing to her we essentially
marketing to an additional 20 customers.
The scale of the graph depends on the marketing scenario
(e.g., network values increase with ), but the shape generally
remains the same. The gure shows that a few users
have very high network value. This is the ideal situation for
the type of targeted viral marketing we propose, since we
can eectively market to many people while incurring only
the expense of marketing to those few. A good customer
to market to is one who: (1) is likely to give the product
a high rating, (2) has a strong weight in determining the
rating prediction for many of her neighbors, (3) has many
neighbors who are easily in
uenced by the rating prediction
they receive, (4) will have a high probability of purchasing
the product, and thus will be likely to actually submit a rating
that will aect her neighbors, and nally (5) has many
neighbors with the same four characteristics outlined above,
4 In our experiments, one Gibbs cycle of sampling all the
nodes in the network took on the order of a ftieth of a
second. The total runtime would be this value multiplied
by the number of sampling iterations desired and by the
number of search steps.
Simply measuring the predictive error rate would not be
very useful, because a very low error rate could be obtained
simply by predicting that no one sees the movie.
6 Inactive people always have a network value of zero.
Rank
Normalized
Network
Value

Figure

2: Typical distribution of network values.
and so on recursively. In the movie domain, these correspond
to nding a person who (1) will enjoy the movie, (2)
has many close friends, who are (3) easily swayed, (4) will
very likely see the movie if marketed to, and (5) has friends
whose friends also have these properties.
4.6 Marketing Experiments
We compared three marketing strategies: mass marketing,
traditional direct marketing, and the network-based marketing
method we proposed in Section 2. In mass marketing,
all customers were marketed to (M In direct
marketing, a customer X i was marketed to (M
and only if ELP i (X Equation ignoring
network eects (i.e., using the network-less probabilities
our approach, we compared the three
approximation methods proposed in Section 2: single pass,
greedy search and hill-climbing. Figure 3 compares these
three search types and direct marketing on three dierent
marketing scenarios. For all scenarios, means
prot numbers are in units of number of movies seen. In
the and in the discounted movie
In both of these scenarios we assumed a
cost of marketing of 10% of the revenue from a single sale:
0:1. In the advertising scenario no discount was offered
1), and a lower cost of marketing was assumed
(corresponding, for example, to online marketing instead of
physical 0:02. Notice that all the marketing
actions considered were eectively in addition to the (pre-
sumably mass) marketing that was actually carried out for
the movie. The average number of people who saw a movie
given only this marketing (i.e., with
The baseline prot would be obtained by subtracting from
this the (unknown) original costs. The correct  for each
marketing scenario was unknown, so we present the results
for a range of values. We believe we have chosen plausible
ranges, with a free movie providing more incentive than a
discount, which in turn provides more incentive than simply
advertising. experiments.
In all scenarios, mass marketing resulted in negative prof-
its. Not surprisingly, it fared particularly poorly in the
discounted movie scenarios, producing prots which
ranged from 2057 to 2712. In the advertising scenario,
mass marketing resulted in prots ranging from 143 to
381 (depending on the choice of ). In the case of a free
movie oer, the prot from direct marketing could not be
positive, since without network eects we were guaranteed
to lose money on anyone who saw a movie for free. Figure 3
shows that our method was able to nd protable marketing
opportunities that were missed by direct marketing. For
the discounted movie, direct marketing actually resulted in
a loss of prot. A customer that looked protable on her
own may actually have had a negative overall value. This
situation demonstrates that not only can ignoring network
eects cause missed marketing opportunities, but it can also
make an unprotable marketing action look protable. In
the advertising scenario, for small  our method increased
prots only slightly, while direct marketing again reduced
them. Both methods improved with increasing , but our
method consistently outperformed direct marketing.
As can be seen in Figure 3, greedy search produced results
that were quite close to those of hill climbing. The
average dierence between greedy and hill-climbing prots
(as a percentage of the latter) in the three marketing scenarios
was 9.6%, 4.0%, and 0.0% respectively. However, as
seen in Figure 3, the runtimes diered signicantly, with
hill-climbing time ranging from 4.6 minutes to 42.1 minutes
while greedy-search time ranged from 3.8 to 5.5 minutes.
The contrast was even more pronounced in the advertising
scenario, where the prots found by the two methods were
nearly identical, but hill climbing took 14 hours to com-
plete, compared to greedy search's 6.7 minutes. Single-pass
was the fastest method and was comparable in speed to direct
marketing, but led to signicantly lower prots in the
discounted movie scenarios.
The lift in prot was considerably higher if all users were
assumed to be active. In the free movie scenario, the lift in
prot using greedy search was 4.7 times greater than when
the network had inactive nodes. In the discount and advertising
scenarios the ratio was 4.1 and 1.8, respectively. This
was attributable to the fact that the more inactive neighbors
a node had, the less responsive it could be to the network.
From the point of view of an e-merchant applying our ap-
proach, this suggests modifying the collaborative ltering
system to only assign active users as neighbors.
5. RELATED WORK
Social networks have been an object of study for some
time, but previous work within sociology and statistics has
suered from a lack of data and focused almost exclusively
on very small networks, typically in the low tens of individuals
[41]. Interestingly, the Google search engine [4] and
Kleinberg's (1998) HITS algorithm for nding hubs and authorities
on the Web are based on social network ideas. The
success of these approaches, and the discovery of widespread
network topologies with nontrivial properties [42], has led to
a
urry of research on modeling the Web as a semi-random
graph (e.g., Kumar et al. [28], Barabasi et al. [1]). Some of
this work might be applicable in our context.
In retrospect, the earliest sign of the potential of viral
marketing was perhaps the classic paper by Milgram [31]
estimating that every person in the world is only six edges
away from every other, if an edge between i and j means \i
knows j." Schwartz and Wood [37] mined social relationships
from email logs. The ReferralWeb project mined a social
network from a wide variety of publicly-available online
information [24], and used it to help individuals nd experts
who could answer their questions. The COBOT project
Free Movie26101
Alpha
Profit
hill greedy single-pass direct
Advertising
Alpha
Profit
hill greedy single-pass direct
Discounted Movie
Alpha
Profit
hill greedy single-pass direct
Discounted Movie Runtimes103050
Alpha
Time
hill greedy single-pass direct

Figure

3: Prots and runtimes obtained using dierent marketing strategies.
gathered social statistics from participant interactions in the
LambdaMoo MUD, but did not explicitly construct a social
network from them [21]. A Markov random eld formulation
similar to Equation 2 was used by Chakrabarti et al. [6] for
classication of Web pages, with pages corresponding to cus-
tomers, hyperlinks between pages corresponding to in
uence
between customers, and the bag of words in the page corresponding
to properties of the product. Neville and Jensen
[32] proposed a simple iterative algorithm for labeling nodes
in social networks, based on the naive Bayes classier. Cook
and Holder [9] developed a system for mining graph-based
data. Flake et al. [13] used graph algorithms to mine communities
from the Web (dened as sets of sites that have
more links to each other than to non-members).
Several researchers have studied the problem of estimating
a customer's lifetime value from data [22]. This line of re-search
generally focuses on variables like an individual's expected
tenure as a customer [30] and future frequency of purchases
[15]. Customer networks have received some attention
in the marketing literature [20]. Most of these studies
are purely qualitative; where data sets appear, they are very
small, and used only for descriptive purposes. Krackhardt
[27] proposes a very simple model for optimizing which customers
to oer a free sample of a product to. The model only
considers the impact on the customer's immediate friends,
ignores the eect of product characteristics, assumes the relevant
probabilities are the same for all customers, and is only
applied to a made-up network with seven nodes.
Collaborative ltering systems proposed in the literature
include GroupLens [35], PHOAKS [40], Siteseer [36], and
others. A list of collaborative ltering systems, projects
and related resources can be found at www.sims.berkeley.-
edu/resources/collab/.
6. FUTURE WORK
The type of data mining proposed here opens up a rich
eld of directions for future research. In this section we
brie
y mention some of the main ones.
Although the network we have mined is large by the standards
of previous research, much larger ones can be en-
visioned. Scaling up may be helped by developing search
methods specic to the problem, to replace the generic ones
we used here. Segmenting a network into more tractable
parts with minimal loss of prot may also be important.
Flake et al. [13] provide a potential way of doing this. A
related approach would be to mine subnetworks with high
prot potential embedded in larger ones. Recent work on
mining signicant Web subgraphs such as bipartite cores,
cliques and webrings (e.g., [28]) provides a starting point.
More generally, we would like to develop a characterization
of network types with respect to the prot that can be obtained
in them using an optimal marketing strategy. This
would, for example, help a company to better gauge the
prot potential of a market before entering (or attempting
to create) it.
In this paper we mined a network from a single source
(a collaborative ltering database). In general, multiple
sources of relevant information will be available; the ReferralWeb
project [24] exemplied their use. Methods for
combining diverse information into a sound representation of
the underlying in
uence patterns are thus an important area
for research. In particular, detecting the presence of causal
relations between individuals (as opposed to purely correlational
ones) is key. While mining causal knowledge from
observational databases is di-cult, there has been much recent
progress [10, 39].
We have also assumed so far that the relevant social net-work
is completely known. In many (or most) applications
this will not be the case. For example, a long-distance telephone
company may know the pattern of telephone calls
among its customers, but not among its non-customers. How-
ever, it may be able to make good use of connections between
customers and non-customers, or to take advantage
of information about former customers. A relevant question
is thus: what can be inferred from a (possibly biased)
sample of nodes and their neighbors in a network? At the
extreme where no detailed information about individual interactions
is available, our method could be extended to
apply to networks where nodes are groups of similar or related
customers, and edges correspond to in
uence among
groups.
Another promising research direction is towards more detailed
node models and multiple types of relations between
nodes. A theoretical framework for this could be provided
by the probabilistic relational models of Friedman et al. [14].
We would also like to extend our approach to consider multiple
types of marketing actions and product-design decisions,
and to multi-player markets (i.e., markets where the actions
of competitors must also be taken into account, leading to
a game-like search process).
This paper considered making marketing decisions at a
specic point in time. A more sophisticated alternative
would be to plan a marketing strategy by explicitly simulating
the sequential adoption of a product by customers
given dierent interventions at dierent times, and adapting
the strategy as new data on customer response arrives. A
further time-dependent aspect of the problem is that social
networks are not static objects; they evolve, and particularly
on the Internet can do so quite rapidly. Some of the largest
opportunities may lie in modeling and taking advantage of
this evolution.
Once markets are viewed as social networks, the inadequacy
of random sampling for pilot tests of products subject
to strong network eects (e.g., smart cards, video on
demand) becomes clear. Developing a better methodology
for studies of this type could help avoid some expensive failures

Many e-commerce sites already routinely use collaborative
ltering. Given that the infrastructure for data gathering
and for inexpensive execution of marketing actions (e.g.,
making specic oers to specic customers when they visit
the site) is already in place, these would appear to be good
candidates for a real-world test of our method. The greatest
potential, however, may lie in knowledge-sharing and customer
review sites like epinions.com, because the interaction
between users is richer and stronger there. For example, it
may be protable for a company to oer its products at a
loss to in
uential contributors to such sites. Our method
is also potentially applicable beyond marketing, to promoting
any type of social change for which the relevant network
of in
uence can be mined from available data. The spread
of online interaction creates unprecedented opportunities for
the study of social information processing; our work is a step
towards better exploiting this new wealth of information.
7. CONCLUSION
This paper proposed the application of data mining to viral
marketing. Viewing customers as nodes in a social net-
work, we modeled their in
uence on each other as a Markov
random eld. We developed methods for mining social net-work
models from collaborative ltering databases, and for
using these models to optimize marketing decisions. An
empirical study using the EachMovie collaborative ltering
database conrmed the promise of this approach.
8.



--R


Spatial interaction and the statistical analysis of lattice systems.
Empirical analysis of predictive algorithms for collaborative
The anatomy of a large-scale hypertextual Web search engine
Estimating probabilities: A crucial task in machine learning.
Enhanced hypertext categorization using hyperlinks.
Markov Random Fields: Theory and Application.
A decision theoretic approach to targeted advertising.

A simple constraint-based algorithm for e-ciently mining observational databases for causal relationships
On the optimality of the simple Bayesian classi
The buzz on buzz.


Value Miner: A data mining environment for the calculation of the customer lifetime value with application to the automotive industry.
Stochastic relaxation
Dependency networks for inference
An algorithmic framework for performing collaborative
The Complete Database Marketer: Second-Generation Strategies and Techniques for Tapping the Power of your Customer Database
Networks in Marketing.

Strategic application of customer lifetime value in direct marketing.
What exactly is viral marketing?
Combining social networks and collaborative
Markov Random Fields and Their Applications.
Authoritative sources in a hyperlinked environment.
Structural leverage in marketing.
Extracting large-scale knowledge bases from the Web
Data mining for direct marketing: Problems and solutions.
Statistics and data mining techniques for lifetime value modeling.
The small world problem.
Iterative classi
A continuous relaxation labeling algorithm for Markov random
Estimating campaign bene
GroupLens: An open architecture for collaborative
Personalized navigation for the web.
Discovering shared interests using graph analysis.
Information Rules: A Strategic Guide to the Network Economy.
Scalable techniques for mining causal structures.
PHOAKS: A system for sharing recommendations.
Social Network Analysis: Methods and Applications.
Collective dynamics of
--TR
Discovering shared interests using graph analysis
GroupLens
PHOAKS
Referral Web
Siteseer
On the Optimality of the Simple Bayesian Classifier under Zero-One Loss
Enhanced hypertext categorization using hyperlinks
Information rules
The anatomy of a large-scale hypertextual Web search engine
Statistics and data mining techniques for lifetime value modeling
Estimating campaign benefits and modeling lift
An algorithmic framework for performing collaborative filtering
Authoritative sources in a hyperlinked environment
Efficient identification of Web communities
A Simple Constraint-Based Algorithm for Efficiently Mining Observational Databases for Causal Relationships
Scalable Techniques for Mining Causal Structures
Graph-Based Data Mining
Value Miner
Extracting Large-Scale Knowledge Bases from the Web
Learning Probabilistic Relational Models
A Decision Theoretic Approach to Targeted Advertising
Cobot in LambdaMOO
Dependency networks for inference, collaborative filtering, and data visualization

--CTR
Steffen Staab , Pedro Domingos , Peter Mika , Jennifer Golbeck , Li Ding , Tim Finin , Anupam Joshi , Andrzej Nowak , Robin R. Vallacher, Social Networks Applied, IEEE Intelligent Systems, v.20 n.1, p.80-93, January 2005
Elchanan Mossel , Sebastien Roch, On the submodularity of influence in social networks, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Muhammad A. Ahmad , Ankur Teredesai, Modeling spread of ideas in online social networks, Proceedings of the fifth Australasian conference on Data mining and analystics, p.185-190, November 29-30, 2006, Sydney, Australia
David Jensen , Jennifer Neville , Brian Gallagher, Why collective inference improves relational classification, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Louis Licamele , Mustafa Bilgic , Lise Getoor , Nick Roussopoulos, Capital and benefit in social networks, Proceedings of the 3rd international workshop on Link discovery, p.44-51, August 21-25, 2005, Chicago, Illinois
Pnar Yolum , Munindar P. Singh, Dynamic communities in referral networks, Web Intelligence and Agent System, v.1 n.2, p.105-116, April
Andrew Y. Wu , Michael Garland , Jiawei Han, Mining scale-free networks using geodesic clustering, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Paat Rusmevichientong , Shenghuo Zhu , David Selinger, Identifying early buyers from purchase data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Ding Zhou , Eren Manavoglu , Jia Li , C. Lee Giles , Hongyuan Zha, Probabilistic models for discovering e-communities, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland
Esteban Arcaute , Adam Kirsch , Ravi Kumar , David Liben-Nowell , Sergei Vassilvitskii, On threshold behavior in query incentive networks, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
Pinar Yolum , Munindar P. Singh, Dynamic communities in referral networks, Web Intelligence and Agent System, v.1 n.2, p.105-116, December
John Galloway , Simeon J. Simoff, Network data mining: methods and techniques for discovering deep linkage between attributes, Proceedings of the 3rd Asia-Pacific conference on Conceptual modelling, p.21-32, January 16-19, 2006, Hobart, Australia
Matthew Richardson , Pedro Domingos, Mining knowledge-sharing sites for viral marketing, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Dan Cosley , Shyong K. Lam , Istvan Albert , Joseph A. Konstan , John Riedl, Is seeing believing?: how recommender system interfaces affect users' opinions, Proceedings of the SIGCHI conference on Human factors in computing systems, April 05-10, 2003, Ft. Lauderdale, Florida, USA
Andrew Fast , David Jensen , Brian Neil Levine, Creating social networks to improve peer-to-peer networking, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Andrew Fast , David Jensen , Brian Neil Levine, Creating social networks to improve peer-to-peer networking, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Jon Kleinberg, Distributed social systems, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, p.5-6, July 23-26, 2006, Denver, Colorado, USA
Deng Cai , Zheng Shao , Xiaofei He , Xifeng Yan , Jiawei Han, Mining hidden community in heterogeneous social networks, Proceedings of the 3rd international workshop on Link discovery, p.58-65, August 21-25, 2005, Chicago, Illinois
Ralitsa Angelova , Gerhard Weikum, Graph-based text classification: learn from your neighbors, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Rakesh Agrawal , Sridhar Rajagopalan , Ramakrishnan Srikant , Yirong Xu, Mining newsgroups using networks arising from social behavior, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary
Perlich , Foster Provost, Distribution-based aggregation for relational learning with identifier attributes, Machine Learning, v.62 n.1-2, p.65-105, February  2006
David Kempe , Jon Kleinberg , va Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
YongSeog Kim, Toward a successful CRM: variable selection, sampling, and ensemble, Decision Support Systems, v.41 n.2, p.542-553, January 2006
Jennifer Neville , David Jensen, Relational Dependency Networks, The Journal of Machine Learning Research, 8, p.653-692, 5/1/2007
Pedro Domingos, Prospects and challenges for multi-relational data mining, ACM SIGKDD Explorations Newsletter, v.5 n.1, July
Xiaodan Song , Belle L. Tseng , Ching-Yung Lin , Ming-Ting Sun, Personalized recommendation driven by information flow, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Lise Getoor, Link mining: a new data mining challenge, ACM SIGKDD Explorations Newsletter, v.5 n.1, July
YongSeog Kim , W. Nick Street, An intelligent system for customer targeting: a data mining approach, Decision Support Systems, v.37 n.2, p.215-228, May 2004
Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Jonathan L. Herlocker , Joseph A. Konstan , Loren G. Terveen , John T. Riedl, Evaluating collaborative filtering recommender systems, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.5-53, January 2004
Sofus A. Macskassy , Foster Provost, Classification in Networked Data: A Toolkit and a Univariate Case Study, The Journal of Machine Learning Research, 8, p.935-983, 5/1/2007
Xiaodan Song , Yun Chi , Koji Hino , Belle L. Tseng, Information flow modeling based on diffusion rate for prediction and ranking, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
Deepayan Chakrabarti , Christos Faloutsos, Graph mining: Laws, generators, and algorithms, ACM Computing Surveys (CSUR), v.38 n.1, p.2-es, 2006
collaborative filtering;direct marketing;viral marketing;markov random fields;social networks;dependency networks