More Web Proxy on the site http://driver.im/

poster

The bang for the buck: fair competitive viral marketing from the host perspective

Authors:

Francesco Bonchi,

Laks V.S. LakshmananAuthors Info & Claims

KDD '13: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 928 - 936

https://doi.org/10.1145/2487575.2487649

Published: 11 August 2013 Publication History

Abstract

The key algorithmic problem in viral marketing is to identify a set of influential users (called seeds) in a social network, who, when convinced to adopt a product, shall influence other users in the network, leading to a large number of adoptions. When two or more players compete with similar products on the same network we talk about competitive viral marketing, which so far has been studied exclusively from the perspective of one of the competing players.

In this paper we propose and study the novel problem of competitive viral marketing from the perspective of the host, i.e., the owner of the social network platform. The host sells viral marketing campaigns as a service to its customers, keeping control of the selection of seeds. Each company specifies its budget and the host allocates the seeds accordingly. From the host's perspective, it is important not only to choose the seeds to maximize the collective expected spread, but also to assign seeds to companies so that it guarantees the "bang for the buck" for all companies is nearly identical, which we formalize as the fair seed allocation problem.

We propose a new propagation model capturing the competitive nature of viral marketing. Our model is intuitive and retains the desired properties of monotonicity and submodularity. We show that the fair seed allocation problem is NP-hard, and develop an efficient algorithm called Needy Greedy. We run experiments on three real-world social networks, showing that our algorithm is effective and scalable.

References

[1]

S. Bharathi, D. Kempe, and M. Salek. Competitive influence maximization in social networks. In WINE'07.

Digital Library

[2]

A. Borodin, Y. Filmus, and J. Oren. Threshold models for competitive influence in social networks. In WINE'10.

Digital Library

[3]

C. Budak, D. Agrawal, and A. El Abbadi. Limiting the spread of misinformation in social networks. In WWW'11.

Digital Library

[4]

T. Carnes, C. Nagarajan, S. M. Wild, and A. van Zuylen. Maximizing influence in a competitive social network: a follower's perspective. In ICEC'07.

Digital Library

[5]

W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In KDD'10.

Digital Library

[6]

W. Chen, Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In ICDM'10.

Digital Library

[7]

M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, 1979.

Digital Library

[8]

A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. Learning influence probabilities in social networks. In WSDM'10.

Digital Library

[9]

A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. A data-based approach to social influence maximization. PVLDB, 5(1):73--84, 2011.

Digital Library

[10]

A. Goyal, W. Lu, and L. V. S. Lakshmanan. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In ICDM'11.

Digital Library

[11]

X. He, G. Song, W. Chen, and Q. Jiang. Influence blocking maximization in social networks under the competitive linear threshold model. In SDM'12.

[12]

T. Hogg and G. Szabó. Diversity of User Activity and Content Quality in Online Communities. In ICWSM'09.

[13]

D. Kempe, J. M. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In KDD'03.

Digital Library

[14]

J. M. Kleinberg and É. Tardos. Algorithm design. Addison-Wesley, Massachusetts, 2006.

Digital Library

[15]

J. Kostka, Y. A. Oswald, and R. Wattenhofer. Word of mouth: Rumor dissemination in social networks. In SIROCCO'08.

Digital Library

[16]

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. M. VanBriesen, and N. S. Glance. Cost-effective outbreak detection in networks. In KDD'07.

Digital Library

[17]

G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions - i. Mathematical Programming, 14(1):265--294, 1978.

Digital Library

[18]

N. Pathak, A. Banerjee, and J. Srivastava. A generalized linear threshold model for multiple cascades. In ICDM'10.

Digital Library

[19]

G. Peng and J. Mu. Technology Adoption in Online Social Networks. Journal of Product Innovation Management, 28(s1):133--145, 2011.

[20]

S. Zhao, R. Meyer, and J. Han. The Enhancement Bias in Consumer Decisions to Adopt and Utilize Product Innovations Research Collection Lee Kong Chian School of Business (Open Access), 2003.

Cited By

Zhang CZhou JWang JFan JShi Y(2024)Fairness-Aware Competitive Bidding Influence Maximization in Social NetworksIEEE Transactions on Computational Social Systems10.1109/TCSS.2023.328560511:2(2147-2159)Online publication date: Apr-2024
https://doi.org/10.1109/TCSS.2023.3285605
Niu YLi YKarras PWang YLi Z(2024)Discovering Personalized Characteristic Communities in Attributed Graphs2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00221(2834-2847)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00221
Choudhury ADuraisamy PHaneghan JJiang FDutt V(2024)Online Influence Maximization via an Explore-exploit Ensemble Approach2024 15th International Conference on Computing Communication and Networking Technologies (ICCCNT)10.1109/ICCCNT61001.2024.10725277(1-7)Online publication date: 24-Jun-2024
https://doi.org/10.1109/ICCCNT61001.2024.10725277
Show More Cited By

Index Terms

The bang for the buck: fair competitive viral marketing from the host perspective
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Creating Social Contagion Through Viral Product Design: A Randomized Trial of Peer Influence in Networks

We examine how firms can create word-of-mouth peer influence and social contagion by designing viral features into their products and marketing campaigns. To econometrically identify the effectiveness of different viral features in creating social ...
Discovering influencers for marketing in the blogosphere

Discovering influential bloggers will not only allow us to understand better the social activities taking place in the blogosphere, but will also provide unique opportunities for sales and advertising. In this paper, we develop an MIV (marketing ...
Identifying bloggers with marketing influence in the blogosphere
ICEC '09: Proceedings of the 11th International Conference on Electronic Commerce

Finding influential bloggers will not only allow us to better understand interesting activities happening in a social network, but also present unique opportunities for sales and advertisements. In this paper, we address a novel problem of finding ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '13: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2013

1534 pages

ISBN:9781450321747

DOI:10.1145/2487575

Editors:
Rayid Ghani
University of Chicago
,
Ted E. Senator
SAIC
,
Paul Bradley
MethodCare, Inc.
,
Rajesh Parekh
Groupon
,
Jingrui He
Stevens Institute of Technology
,
General Chairs:
Robert L. Grossman
University of Chicago and Open Data Group
,
Ramasamy Uthurusamy
General Motors Corporation (retired)
,
Program Chairs:
Inderjit S. Dhillon
University of Texas
,
Yehuda Koren
Google

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 August 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

KDD' 13

Sponsor:

KDD' 13: The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 11 - 14, 2013

Illinois, Chicago, USA

Acceptance Rates

KDD '13 Paper Acceptance Rate 125 of 726 submissions, 17%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
598
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang CZhou JWang JFan JShi Y(2024)Fairness-Aware Competitive Bidding Influence Maximization in Social NetworksIEEE Transactions on Computational Social Systems10.1109/TCSS.2023.328560511:2(2147-2159)Online publication date: Apr-2024
https://doi.org/10.1109/TCSS.2023.3285605
Niu YLi YKarras PWang YLi Z(2024)Discovering Personalized Characteristic Communities in Attributed Graphs2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00221(2834-2847)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00221
Choudhury ADuraisamy PHaneghan JJiang FDutt V(2024)Online Influence Maximization via an Explore-exploit Ensemble Approach2024 15th International Conference on Computing Communication and Networking Technologies (ICCCNT)10.1109/ICCCNT61001.2024.10725277(1-7)Online publication date: 24-Jun-2024
https://doi.org/10.1109/ICCCNT61001.2024.10725277
Çakirkaya MAytaç Afşar Ö(2024)Bibliometric and content analysis of viral marketing in marketing literatureCogent Business & Management10.1080/23311975.2024.236484711:1Online publication date: 18-Jun-2024
https://doi.org/10.1080/23311975.2024.2364847
Zhang CZhou JWei WShi Y(2024)Order-Sensitive Competitive Revenue Maximization for Viral Marketing in Social NetworksInformation Sciences10.1016/j.ins.2024.121474(121474)Online publication date: Sep-2024
https://doi.org/10.1016/j.ins.2024.121474
Yang SDu QZhu GCao JQin WWang YWang Z(2024)Neural attentive influence maximization model in social networks via reverse influence sampling on historical behavior sequencesExpert Systems with Applications10.1016/j.eswa.2024.123491249(123491)Online publication date: Sep-2024
https://doi.org/10.1016/j.eswa.2024.123491
Jaya Krishna RVamshi Krishna BGopalakrishnan TAnagha PKumar Sharma VPrasad Sharma D(2024)Predictive Modeling Techniques of Social Dynamics in Multilayer Social Networks: A SurveySmart Systems: Innovations in Computing10.1007/978-981-97-3690-4_46(621-630)Online publication date: 30-Sep-2024
https://doi.org/10.1007/978-981-97-3690-4_46
Zhang SLiu STang K(2024)A Sample Reuse Strategy for Dynamic Influence Maximization ProblemBio-Inspired Computing: Theories and Applications10.1007/978-981-97-2275-4_9(107-120)Online publication date: 16-Apr-2024
https://doi.org/10.1007/978-981-97-2275-4_9
Saha AKe XKhan ALakshmanan L(2023)Voting-based Opinion Maximization2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00048(544-557)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00048
Zheng JPan L(2023)Dominant coverage for target users at the lowest cost under competitive propagation in social networksComputer Networks10.1016/j.comnet.2023.109693226(109693)Online publication date: May-2023
https://doi.org/10.1016/j.comnet.2023.109693
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents