In the 1970s, researchers including Mark Granovetter and Thomas Schelling in the mathemati...

In the 1970s, researchers including Mark Granovetter and Thomas Schelling in the mathematical social sciences began trying to develop models of certain kinds of collective human behaviors: Why do particular fads catch on while others die out? Why do particular technological innovations achieve widespread adoption, while others remain focused on a small group of users? What are the dynamics by which rioting and looting behavior sometimes (but only rarely) emerges from a crowd of angry people? They proposed that these are all examples of cascade processes, in which an individual s behavior is highly influenced by the behaviors of his or her friends, and so if a few individuals instigate the process, it can spread to more and more people and eventually have a very wide impact. We can think of this process as being like the spread of an illness, or a rumor, jumping from person to person.

The most basic version of their models is the following. There is some underlying behavior (e.g., playing ice hockey, owning a cell phone, taking part in a riot), and at any point in time each person is either an adopter of the behavior or a nonadopter. We represent the population by a directed graph G = (V, E) in which the nodes correspond to people and there is an edge (v, w) if person v has influence over the behavior of person w:If person v adopts the behavior, then this helps induce person w to adopt it as well. Each person w also has a given threshold 6(w) e [0,1], and this has the following meaning: At any time when at least a 6(w) fraction of the nodes with edges to w are adopters of the behavior, the node w will become an adopter as well.

Note that nodes with lower thresholds are more easily convinced to adopt the behavior, while nodes with higher thresholds are more conservative. A node w with threshold 6(w) = 0 will adopt the behavior immediately, with no inducement from friends. Finally, we need a convention about nodes with no incoming edges: We will say that they become adopters if 6(w) = 0, and cannot become adopters if they have any larger threshold.

Given an instance of this model, we can simulate the spread of the behavior as follows.

Note that this process terminates, since there are only n individuals total, and at least one new person becomes an adopter in each iteration.

Now, in the last few years, researchers in marketing and data mining have looked at how a model like this could be used to investigate "word-of-mouth" effects in the success of new products (the so-called viral marketing phenomenon). The idea here is that the behavior we re concerned with is the use of a new product; we may be able to convince a few key people in the population to try out this product, and hope to trigger as large a cascade as possible.

Concretely, suppose we choose a set of nodes S c V and we reset the threshold of each node in S to 0. (By convincing them to try the product, we ve ensured that they re adopters.) We then run the process described above, and see how large the final set of adopters is. Let's denote the size of this final set of adopters by f(S) (note that we write it as a function of S, since it naturally depends on our choice of S). We could think of f(S) as the influence of the set S, since it captures how widely the behavior spreads when "seeded" at S.

The goal, if we re marketing a product, is to find a small set S whose influence f(S) is as large as possible. We thus define the Influence Maximization Problem as follows: Given a directed graph G = (V, E), with a threshold value at each node, and parameters k and b, is there a set S of at most k nodes for which f(S) > b?

Prove that Influence Maximization is NP-complete.

Example. Suppose our graph G = (V, E) has five nodes {a, b, c, d, e}, four edges (a, b), (b, c), (e, d), (d, c), and all node thresholds equal to 2/3. Then the answer to the Influence Maximization instance defined by G, with k = 2 and b = 5, is yes: We can choose S = {a, e}, and this will cause the other three nodes to become adopters as well. (This is the only choice of S that will work here. For example, if we choose S = {a, d}, then b and c will become adopters, but e won t; if we choose S = {a, b}, then none of c, d,ore will become adopters.)