Competitive Influence – A Review
Ever since I got into reading papers, it has always fascinated how much knowledge can just a 8 page document hold. How can the 8 page document be currently extending the boundaries of human knowledge? By my blog posts, I want to draw attention of readers towards some of the upcoming concepts in the field of network science. Today I would like to illuminate readers about the topic of competitive influence maximization.
The problem of influence maximization is quite a well known and has been studied extensively in the past few decades both by economists and computer scientists. However, to just be complete, lets define the problem of influence maximization in the viral marketing setting. Suppose a company wants to launch a new product and wants to market it to consumer by giving some free samples. But, its problem is that, it doesn’t want to give everyone a free sample, but it wants to give samples only to say few people as it really cannot afford to give a lot many free samples. Suppose each sample costs 1 unit and it has only 20 units to give. Now the company wants to select the people whom it wants to give the free samples is in the sense that they can persuade more people to buy the product. It all works on the assumption that a user uses the product and then they refer it to their friends, and they in turn refer to their friends. And those friends buy the product. This problem of which 20 seeds to select such that at the end of the process, the reach of the product is maximum is known as Influence Maximization problem. According to me, for CS students, the best paper to get into this area would definitely be work by Kempe, Kleinberg and Tardos titled “Maximizing the spread of influence through a social network” [link].
Researchers over the past have tried to make the model more realistic by introducing various concepts like, time, game theory, budgets, costs, passivity of users, incentive mechanisms and many more. Others have tried to create efficient heuristics so that the algorithm proposed in the above mentioned paper can scale easily for larger networks without compromising much on the accuracy. One more such factor that is very much applicable in the domain of viral marketing is competition or competitive influence. It is a very valid extension to this problem. Whenever the market is not a monopoly, it is quite safe to assume that there are going to be multiple companies launching a campaign simultaneously or there are going to be more than one marketing campaign in the network at a given time. The question however is, how can we model this competitive behavior?
The researchers have tried to model this competitive behaviour by extending some existing models, for example let us consider the Independent Cascade Model as defined in the above mentioned paper. What the independent cascade model says is that, once a node gets activated, it will try to activate all its currently unactivated nodes with a constant probability p. The model is quite simple. Suppose there are b companies which are competing in the market. Each of the company selects a set Si of nodes, consisting of atmost k nodes. It is assumed that a node selected by the company will buy that company product. However, in the case when a particular node is selected by more than 1 company, then that particular node will get allocated to a company randomly. The goal of each of the company is to maximize the expected number of people allocated to their company at the end of the cascade flow. We can definitely view this as a game. And definitely there does not exist any pure strategy Nash equilibrium, however mixed-strategy Nash equilibrium will exist.
It has been shown that a company’s payoff i.e. expected value of revenue from his strategy given that he knows others strategy is a monotone and a submodular function. Algorithm which can give 1-1/e approximation of the optimal follows a greedy approach. The greedy algorithm is basically iteratively adding a node with largest marginal contribution to the subset.
The above mentioned model just introduces us to the problem of competitive influence in social network. Now, we will try to extend this simplistic model by changing settings. For example consider the budget, the above mentioned model did not account for budget of a player but however that might not be the case. Lets look the above mentioned problem from a follower’s perspective. Suppose there are 2 companies which want to launch a product, and company say A has information about who company B’s influencers are going to be. Now it is upto company A to select nodes in such a way that the number of nodes that buy the product A is more than those buying product B. A has to achieve all of this under a fixed budget. Obviously the model assumes that the choice of a particular node is progressive, that means once a node has bought a product it won’t be willing to change its decision. Also, it is safe to assume that there will definitely be nodes in the network which won’t buy either of A and B. The question which will be answered assuming these settings can be viewed as a best response to competitior’s move in a Stackelberg competition.
Mathematically speaking, we are trying to find the solution to the following problem.
Where A is the company which has information about B’s initil seeds, B is A’s total budget, V is the set of vertices and IA and IB is the set of influencers chosen by A and B respectively. f(IA| IB) is the number of people that will eventually buy product A given that influencers chosen by A is IA and by B is IB.
In the model that we discussed above, we saw that the node randomly choses the company it wants to get influenced by, incase there were multiple nodes who were trying to activate it. Let us now introduce 2 more models to achieve the same task as things might not be random everytime.
Model 1: Distance based model
The distance based model tries to relate to competitive facility location concept. It tries to tell that the location of a node in the network is important to influence people. A consumer will try to adopt the technology which is closest to it and in abundance. Consider a node u is connected by “active” edges (by active edges, we mean edges which have produced the result success when a coin was flipped with success probability equal to independent cascade probability p), and the shortest distance to any active node is say x. Now the node u will accept technology A with probability = number of nodes who have accepted A and are at a distance of x from u connected by active edges divided by total nnumber of nodes who have accepted A and who have accepted B and are at a distance of x from u.
Model 2: Wave propogation model
This particular model doesn’t look at overall shortest distance but it gives more weightage to your immediate neighbours. It says each node makes a decision of which technology to accept, irrespective of the decision made by nodes who are at a distance greater than 1 unit from it.
So probability of u accepting technology A is nothing but ratio of the sum of probabilities of a node accepting technology A for all nodes which are at a distance of 1 unit from it or say x-1 unit from the active set.
It has been proved that both of these models are indeed submodular and a hill climbing approach greedy algorithm can give 1-1/e-E approximation of the optimal. Using these it has been shown that A can obtain a good chunk of market share even by chosing the seed set second.
You can go into the exact technical details and see the results of the above mentioned techniques by going through the following papers:
Cairns T., Nagarajan C., Wild S., and Zulen A., Maximizing Influence in a Competitive Social Network: A Follower’s Perspective [link]
Bharathi S., Kempe D., and Salek M., Competitive Influence Maximization in Social Networks [link]
Other good papers to read regarding this concept:
J. Kotska, Y.A. Oswald, and R. Wattenhofer. Word of Mouth: Rumor dissemination in social networks. In SIROCCO, pages 185-196, 2008
S. Goyal, M. Kearns, Competitive Contagion in Networks. In STOC 2012.