IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v77y2018icp96-114.html
   My bibliography  Save this article

Seed activation scheduling for influence maximization in social networks

Author

Listed:
  • Samadi, Mohammadreza
  • Nagi, Rakesh
  • Semenov, Alexander
  • Nikolaev, Alexander

Abstract

This paper addresses the challenge of strategically maximizing the influence spread in a social network, by exploiting cascade propagators termed “seeds”. It introduces the Seed Activation Scheduling Problem (SASP) that chooses the timing of seed activation under a given budget, over a given time horizon, in the presence/absence of competition. The SASP is framed as a blogger-centric marketing problem on a two-level network, where the decisions are made to buy sponsored posts from prominent bloggers at calculated points in time. A Bayesian evidence diffusion model – the Partial Parallel Cascade (PPC) model – allows the network nodes to be partially activated, proportional to their accumulated evidence levels. The SASP under the PPC model is proven NP-hard. A mixed-integer program is presented for the SASP, along with an efficient column generation heuristic. The paper sets up its problem instances in real-world settings, taking web-based marketing as an application example. Favorable optimality gaps are achieved for SASP solutions on networks based on observed user interactions in pro-health discussion forums. The presented analyses highlight a trade-off between early and late seed activation in igniting and maintaining influence cascades over time. The results reveal the importance of early seeds for campaigns that favor longevity, e.g., in service industry, and the importance of late seeds for campaigns with deadline(s), e.g., in political competitions.

Suggested Citation

  • Samadi, Mohammadreza & Nagi, Rakesh & Semenov, Alexander & Nikolaev, Alexander, 2018. "Seed activation scheduling for influence maximization in social networks," Omega, Elsevier, vol. 77(C), pages 96-114.
    • Handle: RePEc:eee:jomega:v:77:y:2018:i:c:p:96-114
    DOI: 10.1016/j.omega.2017.06.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048316303577
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2017.06.002?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. repec:cup:cbooks:9780511771576 is not listed on IDEAS
    2. Samadi, Mohammadreza & Nikolaev, Alexander & Nagi, Rakesh, 2016. "A subjective evidence model for influence maximization in social networks," Omega, Elsevier, vol. 59(PB), pages 263-278.
    3. Kaplan, Andreas M. & Haenlein, Michael, 2010. "Users of the world, unite! The challenges and opportunities of Social Media," Business Horizons, Elsevier, vol. 53(1), pages 59-68, January.
    4. Kristine de Valck & Roberts V. Kozinets & Andrea C. Wojnicki & Sarah J.S. Wilner, 2010. "Networked Narratives: Understanding Word-of-Mouth Marketing in Online Communities," Post-Print hal-00458424, HAL.
    5. Jason D. Papastavrou & Srikanth Rajagopalan & Anton J. Kleywegt, 1996. "The Dynamic and Stochastic Knapsack Problem with Deadlines," Management Science, INFORMS, vol. 42(12), pages 1706-1718, December.
    6. Vijay Mahajan & Eitan Muller & Subhash Sharma, 1984. "An Empirical Comparison of Awareness Forecasting Models of New Product Introduction," Marketing Science, INFORMS, vol. 3(3), pages 179-197.
    7. Huckfeldt, Robert & Sprague, John, 1987. "Networks in Context: The Social Flow of Political Information," American Political Science Review, Cambridge University Press, vol. 81(4), pages 1197-1216, December.
    8. Anton J. Kleywegt & Jason D. Papastavrou, 1998. "The Dynamic and Stochastic Knapsack Problem," Operations Research, INFORMS, vol. 46(1), pages 17-35, February.
    9. Bone, Paula Fitzgerald, 1995. "Word-of-mouth effects on short-term and long-term product judgments," Journal of Business Research, Elsevier, vol. 32(3), pages 213-223, March.
    10. Easley,David & Kleinberg,Jon, 2010. "Networks, Crowds, and Markets," Cambridge Books, Cambridge University Press, number 9780521195331, January.
    11. Shlomo Kalish, 1985. "A New Product Adoption Model with Price, Advertising, and Uncertainty," Management Science, INFORMS, vol. 31(12), pages 1569-1585, December.
    12. Robert M. Bond & Christopher J. Fariss & Jason J. Jones & Adam D. I. Kramer & Cameron Marlow & Jaime E. Settle & James H. Fowler, 2012. "A 61-million-person experiment in social influence and political mobilization," Nature, Nature, vol. 489(7415), pages 295-298, September.
    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. Raúl M. Ortiz-Gaona & Marcos Postigo-Boix & José L. Melús-Moreno, 2021. "Extent prediction of the information and influence propagation in online social networks," Computational and Mathematical Organization Theory, Springer, vol. 27(2), pages 195-230, June.
    2. Fontecha, John E. & Nikolaev, Alexander & Walteros, Jose L. & Zhu, Zhenduo, 2022. "Scientists wanted? A literature review on incentive programs that promote pro-environmental consumer behavior: Energy, waste, and water," Socio-Economic Planning Sciences, Elsevier, vol. 82(PA).
    3. Fontecha, John E. & Walteros, Jose L. & Nikolaev, Alexander, 2021. "Reach maximization for social lotteries," Omega, Elsevier, vol. 105(C).
    4. Tavasoli, Ali & Fazli, Mehrdad & Ardjmand, Ehsan & Young, William A. & Shakeri, Heman, 2023. "Competitive pricing under local network effects," European Journal of Operational Research, Elsevier, vol. 311(2), pages 545-566.
    5. Wen, Tao & Chen, Yu-wang & Syed, Tahir abbas & Wu, Ting, 2024. "ERIUE: Evidential reasoning-based influential users evaluation in social networks," Omega, Elsevier, vol. 122(C).
    6. Kahr, Michael & Leitner, Markus & Ruthmair, Mario & Sinnl, Markus, 2021. "Benders decomposition for competitive influence maximization in (social) networks," Omega, Elsevier, vol. 100(C).

    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. Angshuman Ghosh & Sanjeev Varshney & Pingali Venugopal, 2014. "Social Media WOM: Definition, Consequences and Inter-relationships," Management and Labour Studies, XLRI Jamshedpur, School of Business Management & Human Resources, vol. 39(3), pages 293-308, August.
    2. Payal S. Kapoor & K.R. Jayasimha & Ashish Sadh, 2013. "Brand-related, Consumer to Consumer, Communication via Social Media," IIM Kozhikode Society & Management Review, , vol. 2(1), pages 43-59, January.
    3. Akbari, Morteza & Foroudi, Pantea & Zaman Fashami, Rahime & Mahavarpour, Nasrin & Khodayari, Maryam, 2022. "Let us talk about something: The evolution of e-WOM from the past to the future," Journal of Business Research, Elsevier, vol. 149(C), pages 663-689.
    4. Inyoung Chae & Andrew T. Stephen & Yakov Bart & Dai Yao, 2017. "Spillover Effects in Seeded Word-of-Mouth Marketing Campaigns," Marketing Science, INFORMS, vol. 36(1), pages 89-104, January.
    5. Lena Steinhoff & Denni Arli & Scott Weaven & Irina V. Kozlenkova, 2019. "Online relationship marketing," Journal of the Academy of Marketing Science, Springer, vol. 47(3), pages 369-393, May.
    6. Ziad Abdelmoety & Spiros Gounaris, 2015. "Exporting B2B Solutions: The Impact and Contribution of Using Social Media," Athens Journal of Business & Economics, Athens Institute for Education and Research (ATINER), vol. 1(1), pages 23-40, January.
    7. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    8. Sheng, Jie, 2019. "Being Active in Online Communications: Firm Responsiveness and Customer Engagement Behaviour," Journal of Interactive Marketing, Elsevier, vol. 46(C), pages 40-51.
    9. Yong Wang & Shamim Chowdhury Ahmed & Shejun Deng & Haizhong Wang, 2019. "Success of Social Media Marketing Efforts in Retaining Sustainable Online Consumers: An Empirical Analysis on the Online Fashion Retail Market," Sustainability, MDPI, vol. 11(13), pages 1-27, June.
    10. Javornik, Ana, 2016. "Augmented reality: Research agenda for studying the impact of its media characteristics on consumer behaviour," Journal of Retailing and Consumer Services, Elsevier, vol. 30(C), pages 252-261.
    11. Clifford Stein & Van-Anh Truong & Xinshang Wang, 2020. "Advance Service Reservations with Heterogeneous Customers," Management Science, INFORMS, vol. 66(7), pages 2929-2950, July.
    12. Fischer, Eileen & Reuber, A. Rebecca, 2011. "Social interaction via new social media: (How) can interactions on Twitter affect effectual thinking and behavior?," Journal of Business Venturing, Elsevier, vol. 26(1), pages 1-18, January.
    13. Camila F. S. Campos & Shaun Hargreaves Heap & Fernanda Leite Lopez de Leon, 2017. "The political influence of peer groups: experimental evidence in the classroom," Oxford Economic Papers, Oxford University Press, vol. 69(4), pages 963-985.
    14. Shelby Brumelle & Darius Walczak, 2003. "Dynamic Airline Revenue Management with Multiple Semi-Markov Demand," Operations Research, INFORMS, vol. 51(1), pages 137-148, February.
    15. Pak, K. & Dekker, R., 2004. "Cargo Revenue Management: Bid-Prices for a 0-1 Multi Knapsack Problem," ERIM Report Series Research in Management ERS-2004-055-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    16. Jihyeok Jung & Chan-Oi Song & Deok-Joo Lee & Kiho Yoon, 2024. "Optimal Mechanism in a Dynamic Stochastic Knapsack Environment," Papers 2402.14269, arXiv.org.
    17. Lucas Böttcher & Hans J Herrmann & Hans Gersbach, 2018. "Clout, activists and budget: The road to presidency," PLOS ONE, Public Library of Science, vol. 13(3), pages 1-11, March.
    18. Peng, Yala & Li, Jiajie & Xia, Hui & Qi, Siyuan & Li, Jianhong, 2015. "The effects of food safety issues released by we media on consumers’ awareness and purchasing behavior: A case study in China," Food Policy, Elsevier, vol. 51(C), pages 44-52.
    19. King, Robert Allen & Racherla, Pradeep & Bush, Victoria D., 2014. "What We Know and Don't Know About Online Word-of-Mouth: A Review and Synthesis of the Literature," Journal of Interactive Marketing, Elsevier, vol. 28(3), pages 167-183.
    20. Grace Lin & Yingdong Lu & David Yao, 2007. "Stochastic Knapsack Problem Revisited: Switch-Over Policies and Dynamic Pricing," Papers 0708.1146, arXiv.org.

    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:eee:jomega:v:77:y:2018:i:c:p:96-114. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    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.