Competitive Influence Maximization in Social Networks Export

@incollection{Bharathi_Etal.07, abstract = {Social networks often serve as a medium for the diffusion of ideas or innovations. An individual's decision whether to adopt a product or innovation will be highly dependent on the choices made by the individual's peers or neighbors in the social network. In this work, we study the game of innovation diffusion with multiple competing innovations such as when multiple companies market competing products using viral marketing. Our first contribution is a natural and mathematically tractable model for the diffusion of multiple innovations in a network. We give a (1 − 1/e) approximation algorithm for computing the best response to an opponent's strategy, and prove that the ” price of competition” of this game is at most 2. We also discuss ” first mover” strategies which try to maximize the expected diffusion against perfect competition. Finally, we give an FPTAS for the problem of maximizing the influence of a single player when the underlying graph is a tree.}, author = {Bharathi, Shishir and Kempe, David and Salek, Mahyar}, citeulike-article-id = {2826989}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-77105-0_31}, doi = {10.1007/978-3-540-77105-0_31}, journal = {Internet and Network Economics}, keywords = {competitive, greedy, influence, networks, spread, submodular}, pages = {306--311}, posted-at = {2008-05-23 21:52:48}, priority = {2}, title = {Competitive Influence Maximization in Social Networks}, url = {http://dx.doi.org/10.1007/978-3-540-77105-0_31}, year = {2007} }

TY - CHAP ID - Bharathi_Etal.07 L3 - citeulike-article-id:2826989 N2 - Social networks often serve as a medium for the diffusion of ideas or innovations. An individual’s decision whether to adopt a product or innovation will be highly dependent on the choices made by the individual’s peers or neighbors in the social network. In this work, we study the game of innovation diffusion with multiple competing innovations such as when multiple companies market competing products using viral marketing. Our first contribution is a natural and mathematically tractable model for the diffusion of multiple innovations in a network. We give a (1 − 1/e) approximation algorithm for computing the best response to an opponent’s strategy, and prove that the “price of competition” of this game is at most 2. We also discuss “first mover” strategies which try to maximize the expected diffusion against perfect competition. Finally, we give an FPTAS for the problem of maximizing the influence of a single player when the underlying graph is a tree. JF - Internet and Network Economics EP - 311 TI - Competitive Influence Maximization in Social Networks SP - 306 KW - competitive KW - greedy KW - influence KW - networks KW - spread KW - submodular AU - Bharathi, Shishir AU - Kempe, David AU - Salek, Mahyar PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-77105-0_31 ER -