Data Mining: The Textbook

19.6. SOCIAL INFLUENCE ANALYSIS

655

19.6 Social Influence Analysis

All social interactions result in varying levels of influence between individuals. In traditional social interactions, this is sometimes referred to as “word of mouth” influence. This general principle is also true for online social networks. For example, when an actor tweets a message in Twitter, the followers of the actors are exposed to the message. The followers may often retweet the message in the network. This results in the spread of information, ideas, and opinions in the social network. Many companies view this kind of information spread as a valuable advertising channel. By tweeting a popular message to the right participants, millions of dollars worth of advertising can be generated, if the message spreads through the social network as a cascade. An example [532 ] is the famous Oreo Superbowl tweet on February 3, 2013. The power went out during the Superbowl game between the San Francisco 49ers and the Baltimore Ravens. Oreo used this opportunity to tweet the following message, along with a picture of an Oreo cookie, during the 34 min interruption: “Power out? No problem. You can still dunk in the dark.” Viewers loved Oreo’s message, and retweeted it thousands of times. Oreo was thus able to generate millions of dollars of advertising at zero cost, and apparently had a higher impact than paid television advertisements during the Superbowl.

Different actors have different abilities to influence their peers in the social network. The two most common factors that regulate the influence of an actor are as follows:

1. 
   Their centrality within the social network structure is a crucial factor in their influence level. For example, actors with high levels of centrality are more likely to be influential. In directed networks, actors with high prestige are more likely to be influential. These measures are discussed in Sect. 19.2.
   

2. 
   The edges in the network are often associated with weights that are dependent on the likelihood that the corresponding pair of actors can be influenced by each other. Depending on the diffusion model used, these weights can sometimes be directly inter-preted as influence propagation probabilities. Several factors may determine these prob-abilities. For example, a well-known individual may have higher influence than lesser known individuals. Similarly, two individuals, who have been friends for a long time, are more likely to influence one another. It is often assumed that the influence propa-gation probabilities are already available for analytical purposes, although a few recent methods show how to estimate these probabilities in a data-driven way.
   

The precise impact of the aforementioned factors is quantified with the use of an influence propagation model. These are also referred to as diffusion models. The main goal of such models is to determine a set of seed nodes in the network, at which the dissemination of information maximizes influence. Therefore, the influence maximization problem is as follows:

Definition 19.6.1 (Influence Maximization) Given a social network G = (N, A), determine a set of k seed nodes S, influencing which will maximize the overall spread of influence in the network.

The value of k can be viewed as a budget on the number of seed nodes that one is allowed to initially influence. This is quite consistent with real-life models, where advertisers are faced with budgets on initial advertising capacity. The goal of social influence analysis is to extend this initial advertising capacity with word-of-mouth methods.

e−1

e
656 CHAPTER 19. SOCIAL NETWORK ANALYSIS

Each model or heuristic can quantify the influence level of a node with the use of a function of S that is denoted by f (·). This function maps subsets of nodes to real numbers representing influence values. Therefore, after a model has been chosen for quantifying the influence f (S) of a given set S, the optimization problem is that of determining the set S that maximizes f (S). An interesting property of a very large number of influence analysis models is that the optimized function f (S) is submodular.

What does submodularity mean? It is a mathematical way of representing the natural law of diminishing returns, as applied to sets. In other words, if S ⊆ T , then the additional influence obtained by adding an individual to set T cannot be larger than the additional influence of adding the same individual to set S. Thus, the incremental influence of the same individual diminishes, as larger supersets of cohorts are available as seeds. The sub-modularity of set S is formally defined as follows:

Definition 19.6.2 (Submodularity) A function f (·) is said to be submodular, if for any pair of sets S, T satisfying S ⊆ T , and any set element e, the following is true: