In many real-world situations, different and often opposite opinions, innovations, or products are competing with one another for their social influence in a networked society. In this paper, we study competitive influence propagation in social networks under the competitive linear threshold (CLT) model, an extension to the classic linear threshold model. Under the CLT model, we focus on the problem that one entity tries to block the influence propagation of its competing entity as much as possible by strategically selecting a number of seed nodes that could initiate its own influence propagation. We call this problem the influence blocking maximization (IBM) problem. We prove that the objective function of IBM in the CLT model is submodular, and thus a greedy algorithm could achieve 1-1 e approximation ratio. However, the greedy algorithm requires Monte-Carlo simulations of competitive influence propagation, which makes the algorithm not efficient. We design an efficient algorithm CLDAG, which utilizes the properties of the CLT model, to address this issue. We conduct extensive simulations of CLDAG, the greedy algorithm, and other baseline algorithms on real-world and synthetic datasets. Our results show that CLDAG is able to provide best accuracy in par with the greedy algorithm and often better than other algorithms, while it is two orders of magnitude faster than the greedy algorithm.
Independent cascade model and linear threshold model are two extensively studied influence diffusions models originally summarized by @cite_21 , based on earlier works of @cite_16 @cite_24 @cite_6 . prove that the generalized versions of these two models are equivalent @cite_21 . Based on the IC and LT model, Kempe et.al @cite_21 @cite_15 propose a greedy algorithm to solve the influence maximization problem (brought about by Richardson @cite_8 ) to maximize the spreading of a single piece of ideas, innovations, etc. under these two models. Many follow-up studies propose alternative heuristics and try to solve the influence maximization problem more efficiently @cite_14 @cite_12 @cite_13 @cite_22 @cite_2 @cite_18 . In terms of efficient algorithm design, our work follows the idea in @cite_22 @cite_2 of finding efficient local graph structures to speed up the computation. In particular, our CLDAG algorithm is similar to the LDAG algorithm of @cite_2 , which is also based on the DAG structure, but our CLDAG algorithm is novel in dealing with competitive influence diffusion using the dynamic programming method.
@cite_18 @cite_14 @cite_22 @cite_8 @cite_21 @cite_6 @cite_24 @cite_2 @cite_15 @cite_16 @cite_13 @cite_12
1944367023 1984069252 2056609785 2187996512 2041157860 1543143196
When we consider the problem of finding influential nodes for information diffusion in a large-scale social network based on the Independent Cascade Model (ICM), we need to compute the expected number of nodes influenced by a given set of nodes. However, a good estimate of this quantity needs a large amount of computation in the ICM. In this paper, we propose two natural special cases of the ICM such that a good estimate of this quantity can be efficiently computed. Using real large-scale social networks, we experimentally demonstrate that for extracting influential nodes, the proposed models can provide novel ranking methods that are different from the ICM, typical methods of social network analysis, and “PageRank” method. Moreover, we experimentally demonstrate that when the propagation probabilities through links are small, they can give good approximations to the ICM for finding sets of influential nodes. Influence maximization, defined by Kempe, Kleinberg, and Tardos (2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. The scalability of influence maximization is a key factor for enabling prevalent viral marketing in large-scale online social networks. Prior solutions, such as the greedy algorithm of (2003) and its improvements are slow and not scalable, while other heuristic algorithms do not provide consistently good performance on influence spreads. In this paper, we design a new heuristic algorithm that is easily scalable to millions of nodes and edges in our experiments. Our algorithm has a simple tunable parameter for users to control the balance between the running time and the influence spread of the algorithm. Our results from extensive simulations on several real-world and synthetic networks demonstrate that our algorithm is currently the best scalable solution to the influence maximization problem: (a) our algorithm scales beyond million-sized graphs where the greedy algorithm becomes infeasible, and (b) in all size ranges, our algorithm performs consistently well in influence spread --- it is always among the best algorithms, and in most cases it significantly outperforms all other scalable heuristics to as much as 100 --260 increase in influence spread. Viral marketing takes advantage of networks of influence among customers to inexpensively achieve large changes in behavior. Our research seeks to put it on a firmer footing by mining these networks from data, building probabilistic models of them, and using these models to choose the best viral marketing plan. Knowledge-sharing sites, where customers review products and advise each other, are a fertile source for this type of data mining. In this paper we extend our previous techniques, achieving a large reduction in computational cost, and apply them to data from a knowledge-sharing site. We optimize the amount of marketing funds spent on each customer, rather than just making a binary decision on whether to market to him. We take into account the fact that knowledge of the network is partial, and that gathering that knowledge can itself have a cost. Our results show the robustness and utility of our approach. Aggregate level simulation procedures have been used in many areas of marketing. In this paper we show how individual level simulations may be used support marketing theory development. More specifically, we show how a certain type of simulations that is based on complex systems studies (in this case Stochastic Cellular Automata) may be used to generalize diffusion theory one of the fundamental theories of new product marketing. Cellular Automata models are simulations of global consequences, based on local interactions between individual members of a population, that are widely used in complex system analysis across disciplines. In this study we demonstrate how the Cellular Automata approach can help untangle complex marketing research problems. Specifically, we address two major issues facing current theory of innovation diffusion: The first is general lack of data at the individual level, while the second is the resultant inability of marketing researchers to empirically validate the main assumptions used in the aggregate models of innovation diffusion. Using a computer-based Cellular Automata Diffusion Simulation, we demonstrate how such problems can be overcome. More specifically, we show that relaxing the commonly used assumption of homogeneity in the consumers’ communication behavior is not a barrier to aggregate modeling. Thus we show that notwithstanding some exceptions, the well-known Bass model performs well on aggregate data when the assumption that that all adopters have a possible equal effect on all other potential adopters is relaxed. Through Cellular Automata we are better able to understand how individual level assumptions influence aggregate level parameter values, and learn the strengths and limitations of the aggregate level analysis. We believe that this study can serve as a demonstration towards a much wider use of Cellular Automata models for complex marketing research phenomena. Models of collective behavior are developed for situations where actors have two alternatives and the costs and or benefits of each depend on how many other actors choose which alternative. The key concept is that of "threshold": the number or proportion of others who must make one decision before a given actor does so; this is the point where net benefits begin to exceed net costs for that particular actor. Beginning with a frequency distribution of thresholds, the models allow calculation of the ultimate or "equilibrium" number making each decision. The stability of equilibrium results against various possible changes in threshold distributions is considered. Stress is placed on the importance of exact distributions distributions for outcomes. Groups with similar average preferences may generate very different results; hence it is hazardous to infer individual dispositions from aggregate outcomes or to assume that behavior was directed by ultimately agreed-upon norms. Suggested applications are to riot ... In this paper, we consider the problem of selecting, for any given positive integer k, the top-k nodes in a social network, based on a certain measure appropriate for the social network. This problem is relevant in many settings such as analysis of co-authorship networks, diffusion of information, viral marketing, etc. However, in most situations, this problem turns out to be NP-hard. The existing approaches for solving this problem are based on approximation algorithms and assume that the objective function is sub-modular. In this paper, we propose a novel and intuitive algorithm based on the Shapley value, for efficiently computing an approximate solution to this problem. Our proposed algorithm does not use the sub-modularity of the underlying objective function and hence it is a general approach. We demonstrate the efficacy of the algorithm using a co-authorship data set from e-print arXiv (www.arxiv.org), having 8361 authors.