IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y2020i2p289-302.html
   My bibliography  Save this article

Least-Cost Influence Maximization on Social Networks

Author

Listed:
  • Dilek Günneç

    (Department of Industrial Engineering, Ozyegin University, Istanbul 34794, Turkey)

  • S. Raghavan

    (Robert H. Smith School of Business and Institute for Systems Research, University of Maryland, College Park, Maryland 20742)

  • Rui Zhanga

    (Leeds School of Business, University of Colorado, Boulder, Colorado 80309)

Abstract

Viral-marketing strategies are of significant interest in the online economy. Roughly, in these problems, one seeks to identify which individuals to strategically target in a social network so that a given proportion of the network is influenced at minimum cost. Earlier literature has focused primarily on problems where a fixed inducement is provided to those targeted. In contrast, resembling the practical viral-marketing setting, we consider this problem where one is allowed to “partially influence” (by the use of monetary inducements) those selected for targeting. We thus focus on the “least-cost influence problem (LCIP)”: an influence-maximization problem where the goal is to find the minimum total amount of inducements (individuals to target and associated tailored incentive) required to influence a given proportion of the population. Motivated by the desire to develop a better understanding of fundamental problems in social-network analytics, we seek to develop (exact) optimization approaches for the LCIP. Our paper makes several contributions, including (i) showing that the problem is NP-complete in general as well as under a wide variety of special conditions; (ii) providing an influence greedy algorithm to solve the problem polynomially on trees, where we require 100% adoption and all neighbors exert equal influence on a node; and (iii) a totally unimodular formulation for this tree case.

Suggested Citation

  • Dilek Günneç & S. Raghavan & Rui Zhanga, 2020. "Least-Cost Influence Maximization on Social Networks," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 289-302, April.
    • Handle: RePEc:inm:orijoc:v:32:y:2020:i:2:p:289-302
    DOI: 10.1287/ijoc.2019.0886
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2019.0886
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2019.0886?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. MARCHAND, Hugues & WOLSEY, Laurence A., 1999. "The 0-1 Knapsack problem with a single continuous variable," LIDAM Reprints CORE 1390, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Brown, Jacqueline Johnson & Reingen, Peter H, 1987. "Social Ties and Word-of-Mouth Referral Behavior," Journal of Consumer Research, Journal of Consumer Research Inc., vol. 14(3), pages 350-362, December.
    3. Ravi Bapna & Akhmed Umyarov, 2015. "Do Your Online Friends Make You Pay? A Randomized Field Experiment on Peer Influence in Online Social Networks," Management Science, INFORMS, vol. 61(8), pages 1902-1920, August.
    4. Catherine Tucker & Juanjuan Zhang, 2010. "Growing Two-Sided Networks by Advertising the User Base: A Field Experiment," Marketing Science, INFORMS, vol. 29(5), pages 805-814, 09-10.
    5. Geng Lin & Wenxing Zhu & M. Ali, 2011. "An exact algorithm for the 0–1 linear knapsack problem with a single continuous variable," Journal of Global Optimization, Springer, vol. 50(4), pages 657-673, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Cheng-Lung Chen & Eduardo L. Pasiliao & Vladimir Boginski, 2023. "A polyhedral approach to least cost influence maximization in social networks," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-31, January.
    2. Ariah Klages-Mundt & Andreea Minca, 2021. "Optimal Intervention in Economic Networks using Influence Maximization Methods," Papers 2102.01800, arXiv.org, revised Mar 2023.
    3. Klages-Mundt, Ariah & Minca, Andreea, 2022. "Optimal intervention in economic networks using influence maximization methods," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1136-1148.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wang, Le & Luo, Xin (Robert) & Li, Han, 2022. "Envy or conformity? An empirical investigation of peer influence on the purchase of non-functional items in mobile free-to-play games," Journal of Business Research, Elsevier, vol. 147(C), pages 308-324.
    2. Tingting Song & Qian Tang & Jinghua Huang, 2019. "Triadic Closure, Homophily, and Reciprocation: An Empirical Investigation of Social Ties Between Content Providers," Information Systems Research, INFORMS, vol. 30(3), pages 912-926, September.
    3. Rishika Rishika & Jui Ramaprasad, 2019. "The Effects of Asymmetric Social Ties, Structural Embeddedness, and Tie Strength on Online Content Contribution Behavior," Management Science, INFORMS, vol. 65(7), pages 3398-3422, July.
    4. Muller, Eitan & Peres, Renana, 2019. "The effect of social networks structure on innovation performance: A review and directions for research," International Journal of Research in Marketing, Elsevier, vol. 36(1), pages 3-19.
    5. Sinan Aral & Dylan Walker, 2014. "Tie Strength, Embeddedness, and Social Influence: A Large-Scale Networked Experiment," Management Science, INFORMS, vol. 60(6), pages 1352-1370, June.
    6. Pasquale Avella & Maurizio Boccia & Igor Vasilyev, 2012. "Computational Testing of a Separation Procedure for the Knapsack Set with a Single Continuous Variable," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 165-171, February.
    7. Choo Yeon Kim & Seong Soo Cha, 2023. "Effect of SNS Characteristics for Dining Out on Customer Satisfaction and Online Word of Mouth," SAGE Open, , vol. 13(3), pages 21582440231, September.
    8. Jennifer K D’Angelo & Kristin Diehl & Lisa A Cavanaugh, 2019. "Lead by Example? Custom-Made Examples Created by Close Others Lead Consumers to Make Dissimilar Choices," Journal of Consumer Research, Journal of Consumer Research Inc., vol. 46(4), pages 750-773.
    9. Yucheng Zhang & Zhiling Wang & Lin Xiao & Lijun Wang & Pei Huang, 2023. "Discovering the evolution of online reviews: A bibliometric review," Electronic Markets, Springer;IIM University of St. Gallen, vol. 33(1), pages 1-22, December.
    10. Feixiang Zhang & Liyong Zong, 2014. "Dissemination of Word of Mouth Based on SNA Centrality Modeling and Power of Actors - An Empirical Analysis of Internet Word of Mouth," International Journal of Business Administration, International Journal of Business Administration, Sciedu Press, vol. 5(5), pages 65-70, September.
    11. Miguel Godinho de Matos & Pedro Ferreira, 2020. "The Effect of Binge-Watching on the Subscription of Video on Demand: Results from Randomized Experiments," Information Systems Research, INFORMS, vol. 31(4), pages 1337-1360, December.
    12. Gangopadhyay, Partha & Jain, Siddharth & Bakry, Walid, 2022. "In search of a rational foundation for the massive IT boom in the Australian banking industry: Can the IT boom really drive relationship banking?," International Review of Financial Analysis, Elsevier, vol. 82(C).
    13. Paolo E. Giordani & Francesco Rullani, 2020. "The Digital Revolution and COVID-19," Working Papers 06, Department of Management, Università Ca' Foscari Venezia.
    14. Prabirendra Chatterjee & Bo Zhou, 2021. "Sponsored Content Advertising in a Two-Sided Market," Management Science, INFORMS, vol. 67(12), pages 7560-7574, December.
    15. Ting Li & Robert J. Kauffman & Eric van Heck & Peter Vervest & Benedict G. C. Dellaert, 2014. "Consumer Informedness and Firm Information Strategy," Information Systems Research, INFORMS, vol. 25(2), pages 345-363, June.
    16. Yadav, Manjit S. & de Valck, Kristine & Hennig-Thurau, Thorsten & Hoffman, Donna L. & Spann, Martin, 2013. "Social Commerce: A Contingency Framework for Assessing Marketing Potential," Journal of Interactive Marketing, Elsevier, vol. 27(4), pages 311-323.
    17. Khim-Yong Goh & Cheng-Suang Heng & Zhijie Lin, 2013. "Social Media Brand Community and Consumer Behavior: Quantifying the Relative Impact of User- and Marketer-Generated Content," Information Systems Research, INFORMS, vol. 24(1), pages 88-107, March.
    18. Fang Di & Richards Timothy J. & Grebitus Carola, 2019. "Modeling Product Choices in a Peer Network," Forum for Health Economics & Policy, De Gruyter, vol. 22(1), pages 1-13, June.
    19. Jalees, Tariq & Tariq, Huma & Zaman, Syed Imran & Alam Kazmi, Syed Hasnain, 2015. "Social Media in Virtual Marketing," MPRA Paper 69868, University Library of Munich, Germany, revised 10 Apr 2015.
    20. Songhong Chen & Jian Ming Luo, 2023. "Understand Delegates Risk Attitudes and Behaviour: The Moderating Effect of Trust in COVID-19 Vaccination," IJERPH, MDPI, vol. 20(5), pages 1-18, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:32:y:2020:i:2:p:289-302. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.