Article

Threshold models for competitive influence in social networks

Authors:

Allan Borodin,

Yuval Filmus,

Joel OrenAuthors Info & Claims

WINE'10: Proceedings of the 6th international conference on Internet and network economics

Pages 539 - 550

Published: 13 December 2010 Publication History

Publisher Site

Abstract

The problem of influence maximization deals with choosing the optimal set of nodes in a social network so as to maximize the resulting spread of a technology (opinion, product-ownership, etc.), given a model of diffusion of influence in a network. A natural extension is a competitive setting, in which the goal is to maximize the spread of our technology in the presence of one or more competitors.

We suggest several natural extensions to the well-studied linearthreshold model, showing that the original greedy approach cannot be used.

Furthermore, we show that for a broad family of competitive influence models, it is NP-hard to achieve an approximation that is better than a square root of the optimal solution; the same proof can also be applied to give a negative result for a conjecture in [2] about a general cascade model for competitive diffusion.

Finally, we suggest a natural model that is amenable to the greedy approach.

References

[1]

Bharathi, S., Kempe, D., Salek, M.: Competitive influence maximization in social networks. In:WINE 2007. LNCS, vol. 4858, pp. 306-311. Springer, Heidelberg (2007)

Digital Library

Google Scholar

[2]

Carnes, T., Nagarajan, C., Wild, S.M., van Zuylen, A.: Maximizing influence in a competitive social network: a follower's perspective. In: ICEC 2007: Proceedings of the Ninth International Conference on Electronic Commerce, pp. 351-360. ACM, New York (2007)

Digital Library

Google Scholar

[3]

Domingos, P., Richardson, M.: Mining the network value of customers. In: KDD 2001: Proceedings of the seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 57-66. ACM Press, New York (2001)

Digital Library

Google Scholar

[4]

Nemhauser, M.F.G., Wolsey, L.: An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14, 265-294 (1978)

Digital Library

Google Scholar

[5]

Brown, P.R.J.: Social ties and word-of-mouth referral behavior. Journal of Consumer Research 14(3), 350-362 (1987)

Crossref

Google Scholar

[6]

Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: KDD 2003: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137-146. ACM, New York (2003)

Digital Library

Google Scholar

[7]

Kostka, J., Oswald, Y.A., Wattenhofer, R.: Word of mouth: Rumor dissemination in social networks. In: Shvartsman, A.A., Felber, P. (eds.) SIROCCO 2008. LNCS, vol. 5058, pp. 185-196. Springer, Heidelberg (2008)

Digital Library

Google Scholar

[8]

Mossel, E., Roch, S.: Submodularity of influence in social networks: From local to global. SIAM J. Comput. 39(6), 2176-2188 (2010)

Digital Library

Google Scholar

Cited By

View all

Tsaras DTrimponias GNtaflos LPapadias D(2021)Collective influence maximization for multiple competing products with an awareness-to-influence modelProceedings of the VLDB Endowment10.14778/3450980.345098114:7(1124-1136)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.14778/3450980.3450981
D'Angelo GAbouei Mehrizi MDemartini GZuccon GCulpepper JHuang ZTong H(2021)Mitigating Negative Influence Diffusion is HardProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482451(332-341)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482451
Sabato YAzaria AHazon NEl Fallah Seghrouchni ASukthankar GAn BYorke-Smith N(2020)Viral vs. EffectiveProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3398761.3398897(1169-1177)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.5555/3398761.3398897
Show More Cited By

Recommendations

Containment of competitive influence spread in social networks

To contain the competitive influence spread in social networks is to maximize the influence of one participant and contain the influence of its opponent. It is desirable to develop effective strategies for influence spread of the participants themselves ...
Scalable Influence Maximization in Social Networks under the Linear Threshold Model
ICDM '10: Proceedings of the 2010 IEEE International Conference on Data Mining

Influence maximization is the problem of finding a small set of most influential nodes in a social network so that their aggregated influence in the network is maximized. In this paper, we study influence maximization in the linear threshold model, one ...
New Competitive Influence Propagation Models in Social Networks
MSN '14: Proceedings of the 2014 10th International Conference on Mobile Ad-hoc and Sensor Networks

We study competitive influence propagation in social networks based on Independent Cascade (IC) model. First we propose two new models, in both of which each individual in the network is allowed to propagate multiple influences to its neighbors. In the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

WINE'10: Proceedings of the 6th international conference on Internet and network economics

December 2010

578 pages

ISBN:3642175716

Editor:
Amin Saberi
Stanford University, Department of Management Science and Engineering, Stanford, CA

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 13 December 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tsaras DTrimponias GNtaflos LPapadias D(2021)Collective influence maximization for multiple competing products with an awareness-to-influence modelProceedings of the VLDB Endowment10.14778/3450980.345098114:7(1124-1136)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.14778/3450980.3450981
D'Angelo GAbouei Mehrizi MDemartini GZuccon GCulpepper JHuang ZTong H(2021)Mitigating Negative Influence Diffusion is HardProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482451(332-341)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482451
Sabato YAzaria AHazon NEl Fallah Seghrouchni ASukthankar GAn BYorke-Smith N(2020)Viral vs. EffectiveProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3398761.3398897(1169-1177)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.5555/3398761.3398897
Ali KWang CYeh MChen YAlhajj R(2020)Addressing competitive influence maximization on unknown social network with deep reinforcement learningProceedings of the 12th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1109/ASONAM49781.2020.9381471(196-203)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1109/ASONAM49781.2020.9381471
(2019)Influence maximisation in social networksInternational Journal of Computational Science and Engineering10.5555/3319216.331921718:2(103-117)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3319216.3319217
Auletta VFerraioli DFionda VGreco GElkind EVeloso MAgmon NTaylor M(2019)Maximizing the Spread of an Opinion when Tertium Datur EstProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331823(1207-1215)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3331823
Lakshmanan LSimpson MThirumuruganathan S(2019)Combating fake newsProceedings of the VLDB Endowment10.14778/3352063.335211712:12(1990-1993)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.14778/3352063.3352117
Amelkin VBogdanov PSingh A(2019)A Distance Measure for the Analysis of Polar Opinion Dynamics in Social NetworksACM Transactions on Knowledge Discovery from Data10.1145/333216813:4(1-34)Online publication date: 8-Aug-2019
https://dl.acm.org/doi/10.1145/3332168
Amanatidis GKleer PSchäfer GKarlin AImmorlica NJohari R(2019)Budget-Feasible Mechanism Design for Non-Monotone Submodular ObjectivesProceedings of the 2019 ACM Conference on Economics and Computation10.1145/3328526.3329622(901-919)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3328526.3329622
Wu LLiu HBoldi PWelles BKinder-Kurlanda KWilson CPeters IMeira W(2019)Debunking Rumors in Social NetworksProceedings of the 10th ACM Conference on Web Science10.1145/3292522.3326025(323-331)Online publication date: 26-Jun-2019
https://dl.acm.org/doi/10.1145/3292522.3326025
Show More Cited By

Abstract

References

Cited By

Recommendations

Containment of competitive influence spread in social networks

Scalable Influence Maximization in Social Networks under the Linear Threshold Model

New Competitive Influence Propagation Models in Social Networks

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations