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. 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.
    2. 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.
    3. 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.
    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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Yuho Chung & Yiwei Li & Jianmin Jia, 2021. "Exploring embeddedness, centrality, and social influence on backer behavior: the role of backer networks in crowdfunding," Journal of the Academy of Marketing Science, Springer, vol. 49(5), pages 925-946, September.
    11. Sebastian Martin & Birgit Grüb, 0. "Intensive WOM-behavior in the healthcare sector – the case of an Austrian hospital’s Facebook site," International Review on Public and Nonprofit Marketing, Springer;International Association of Public and Non-Profit Marketing, vol. 0, pages 1-22.
    12. Hu, Miao & Chen, Jie & Chen, Qimei & He, Wei, 2020. "It pays off to be authentic: An examination of direct versus indirect brand mentions on social media," Journal of Business Research, Elsevier, vol. 117(C), pages 19-28.
    13. Jolanta Tkaczyk, 2015. "Consumer Susceptibility to Social Influence and Tendency to Generate a Positive or Negative Message in Word of Mouth Communication," International Conference on Marketing and Business Development Journal, The Bucharest University of Economic Studies, vol. 1(1), pages 21-28, July.
    14. Wang, Kai-Yu & Ting, I-Hsien & Wu, Hui-Ju, 2013. "Discovering interest groups for marketing in virtual communities: An integrated approach," Journal of Business Research, Elsevier, vol. 66(9), pages 1360-1366.
    15. Maise Soares Pereira & Ivan Lapuente Garrido & Celso Augusto de Matos, 2015. "Firm-Created Word-of-Mouth Recommendation: is it Also Worthwhile?," Brazilian Business Review, Fucape Business School, vol. 12(3), pages 91-118, May.
    16. Chakravarty, Anindita & Liu, Yong & Mazumdar, Tridib, 2010. "The Differential Effects of Online Word-of-Mouth and Critics' Reviews on Pre-release Movie Evaluation," Journal of Interactive Marketing, Elsevier, vol. 24(3), pages 185-197.
    17. Kim, Juran & Kang, Seungmook & Lee, Ki Hoon, 2021. "Evolution of digital marketing communication: Bibliometric analysis and network visualization from key articles," Journal of Business Research, Elsevier, vol. 130(C), pages 552-563.
    18. Claus, Bart & Geyskens, Kelly & Millet, Kobe & Dewitte, Siegfried, 2012. "The referral backfire effect: The identity-threatening nature of referral failure," International Journal of Research in Marketing, Elsevier, vol. 29(4), pages 370-379.
    19. Palmeira, Mauricio, 2020. "Advice in the presence of external cues: The impact of conflicting judgments on perceptions of expertise," Organizational Behavior and Human Decision Processes, Elsevier, vol. 156(C), pages 82-96.
    20. David Godes & Dina Mayzlin, 2004. "Using Online Conversations to Study Word-of-Mouth Communication," Marketing Science, INFORMS, vol. 23(4), pages 545-560, June.

    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.