IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v33y2017i2d10.1007_s10878-016-0006-z.html
   My bibliography  Save this article

Solution of Bharathi–Kempe–Salek conjecture for influence maximization on arborescence

Author

Listed:
  • Zaixin Lu

    (Washington State University)

  • Zhao Zhang

    (Zhejiang Normal University)

  • Weili Wu

    (Taiyuan University of Technology
    University of Texas at Dallas)

Abstract

Influence maximization is an important problem in social networks. Bharathi et al. (Competitive influence maximization in social networks, pp 306–311, 2007) conjectured that this problem is $${{\mathcal {N}}}{{\mathcal {P}}}$$ N P -hard on arborescence directed into a root. In this short note, we show that the conjecture is true for the independent cascade (IC) model, which is the most studied model in the literature specifying how each node influences other nodes. Therefore, assuming $${\mathcal {P}}\ne {{\mathcal {N}}}{{\mathcal {P}}}$$ P ≠ N P , there exists no polynomial-time algorithm for the influence maximization problem under the IC model on arborescence directed into a root. On the other hand, Wang et al. (J Comb Optim, doi: 10.1007/s10878-016-9991-1 , 2016) have shown that there exists polynomial-time algorithm for this problem under the linear threshold (LT) model. Hence, this pair of results is of theoretical interest since this is the first time to give a theoretical difference on computational complexity between the IC and LT models. We believe it may motivate further research for influence maximization on arborescence and other special graphs.

Suggested Citation

  • Zaixin Lu & Zhao Zhang & Weili Wu, 2017. "Solution of Bharathi–Kempe–Salek conjecture for influence maximization on arborescence," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 803-808, February.
    • Handle: RePEc:spr:jcomop:v:33:y:2017:i:2:d:10.1007_s10878-016-0006-z
    DOI: 10.1007/s10878-016-0006-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-016-0006-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-016-0006-z?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. 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.
    2. Ailian Wang & Weili Wu & Lei Cui, 2016. "On Bharathi–Kempe–Salek conjecture for influence maximization on arborescence," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1678-1684, May.
    3. Lidan Fan & Zaixin Lu & Weili Wu & Yuanjun Bi & Ailian Wang & Bhavani Thuraisingham, 2014. "An individual-based model of information diffusion combining friends’ influence," Journal of Combinatorial Optimization, Springer, vol. 28(3), pages 529-539, October.
    Full references (including those not matched with items on IDEAS)

    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. Hemant Gehlot & Shreyas Sundaram & Satish V. Ukkusuri, 2023. "Algorithms for influence maximization in socio-physical networks," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-28, January.
    2. 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.
    3. 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.
    4. 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.
    5. Chuangen Gao & Shuyang Gu & Jiguo Yu & Hai Du & Weili Wu, 2022. "Adaptive seeding for profit maximization in social networks," Journal of Global Optimization, Springer, vol. 82(2), pages 413-432, February.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. Sebastian Schneider, 2022. "Price-related consumer discussions in China and the United States: a cross-cultural study investigating price perceptions and word-of-mouth transmission," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 21(3), pages 274-290, June.
    14. Bogdan Anastasiei & Nicoleta Dospinescu, 2019. "Electronic Word-of-Mouth for Online Retailers: Predictors of Volume and Valence," Sustainability, MDPI, vol. 11(3), pages 1-18, February.
    15. Easley, Richard W. & Bearden, William O. & Teel, Jesse E., 1995. "Testing predictions derived from inoculation theory and the effectiveness of self-disclosure communications strategies," Journal of Business Research, Elsevier, vol. 34(2), pages 93-105, October.
    16. Hsiang-Ming Lee & Tsai Chen & Ya-Hui Hsu & Yu-Chi Wu, 2018. "Effect Of Complementary Product Fit And Brand Awareness On Brand Attitude After M&As: Word Of Mouth As A Moderator," Global Journal of Business Research, The Institute for Business and Finance Research, vol. 12(1), pages 51-67.
    17. Yoon, Hyun Shik & Occeña, Luis G., 2015. "Influencing factors of trust in consumer-to-consumer electronic commerce with gender and age," International Journal of Information Management, Elsevier, vol. 35(3), pages 352-363.
    18. Luís Filipe Miranda Grochocki & Andrea Felippe Cabello, 2023. "Research collaboration networks in maturing academic environments," Scientometrics, Springer;Akadémiai Kiadó, vol. 128(4), pages 2535-2556, April.
    19. Reema Nofal & Pelin Bayram & Okechukwu Lawrence Emeagwali & Lu’ay Al-Mu’ani, 2022. "The Effect of eWOM Source on Purchase Intention: The Moderation Role of Weak-Tie eWOM," Sustainability, MDPI, vol. 14(16), pages 1-20, August.
    20. Rohit Aggarwal & Ram Gopal & Ramesh Sankaranarayanan, 2007. "Negative Blogs, Positive Outcomes: When should Firms Permit Employees to Blog Honestly?," Working Papers 07-32, NET Institute, revised Sep 2007.

    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:spr:jcomop:v:33:y:2017:i:2:d:10.1007_s10878-016-0006-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.