Influence blocking maximization under refutation | Social Network Analysis and Mining Skip to main content
Springer Nature Link
Log in

Influence blocking maximization under refutation

  • Original Article
  • Published:
Social Network Analysis and Mining Aims and scope Submit manuscript

Abstract

In social networks, a phenomenon termed the refutation mechanism arises when certain users spontaneously counter negative information based on their knowledge and experience. To the best of our knowledge, this paper focuses on the influence blocking maximization under the refutation mechanism for the first time. Specifically, incorporating the refutation mechanism with the Competitive Independent Cascade model, we introduce the Refutation Competitive Independent Cascade model, while also considering real-time delay. Under the proposed model, we study the Joint Influence Blocking Maximization (JIBM) problem. The objective of JIBM is to maximize the expected number of nonnegatives by finding a set of positive seeds in a network. We show that the problem is NP-hard. We present a scalable approximation algorithm, named RR-JIBM, by making a non-trivial adaptation of the generation process of reverse reachable sets. We prove that the given algorithms achieve a \((1-1/e-\varepsilon )\)-approximation for any \(\varepsilon > 0\) for JIBM problem. An improved algorithm named RR-JIBM+ is also proposed to improve the efficiency of RR-JIBM in reality. Experiments on real-world social networks show that our algorithms outperform other intuitive baselines in reducing the number of nodes influenced by negative seed nodes. Meanwhile, the RR-JIBM+ algorithm has a higher efficiency advantage than RR-JIBM on different datasets.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Algorithm 2
Algorithm 3
Algorithm 4
Fig. 2
Fig. 3

Similar content being viewed by others

Data availability

All the datasets can be accessed from http://snap.stanford.edu/data/index.html and http://konect.cc/networks.

Notes

  1. http://snap.stanford.edu/data/index.html

  2. http://konect.cc/networks

References

  • Banerjee A, Chandrasekhar AG, Duflo E, Jackson MO (2013) The diffusion of microfinance. Science 341(6144):1236498

    Article  Google Scholar 

  • Borgs C, Brautbar M, Chayes J, Lucier B (2014) Maximizing social influence in nearly optimal time. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms

  • Borodin A, Filmus Y, Oren J (2010) Threshold models for competitive influence in social networks. In: Internet and network economics - 6th international workshop, WINE. Lecture Notes in Computer Science, 6484: 539–550

  • Bovet A, Makse HA (2019) Influence of fake news in Twitter during the 2016 US presidential election. Nat Commun 10(1):7

    Article  Google Scholar 

  • Braunstein A, Dall’Asta L, Semerjian G, Zdeborová L (2016) Network dismantling. Proc Natl Acad Sci 113(44):12368–12373

    Article  Google Scholar 

  • Budak C, Agrawal D, El Abbadi A (2011) Limiting the spread of misinformation in social networks. In: Proceedings of the 20th international conference on world wide web

  • Chen W (2018) An issue in the martingale analysis of the influence maximization algorithm imm. In: Computational data and social networks

  • Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 199–208

  • Chen D, Lü L, Shang M-S, Zhang Y-C, Zhou T (2012) Identifying influential nodes in complex networks. Physica A Statist Mech Appl 391(4):1777–1787

    Article  Google Scholar 

  • Chen W, Lakshmanan LVS, Castillo C (2013) Inform Influ Propagation Soc Netw. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, California, United States

    Google Scholar 

  • Chen B-L, Jiang W-X, Chen Y-X, Chen L, Wang R-J, Han S, Lin J-H, Zhang Y-C (2022) Influence blocking maximization on networks: Models, methods and applications. Phys Rep 976:1–54

    Article  MathSciNet  Google Scholar 

  • Del Vicario M, Bessi A, Zollo F, Petroni F, Scala A, Caldarelli G, Stanley HE, Quattrociocchi W (2016) The spreading of misinformation online. Proc Natl Acad Sci 113(3):554–559

    Article  Google Scholar 

  • Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the 7th ACM SIGKDD international conference on knowledge discovery and data mining, pp 57–66

  • Fan C, Zeng L, Sun Y, Liu Y-Y (2020) Finding key players in complex networks through deep reinforcement learning. Nat Mach Intell 2(6):317–324

    Article  Google Scholar 

  • He X, Song G, Chen W, Jiang Q (2012) Influence blocking maximization in social networks under the competitive linear threshold model. In: SDM

  • Jones NM, Thompson RR, Schetter CD, Silver RC (2017) Distress and rumor exposure on social media during a campus lockdown. Proc Natl Acad Sci 114(44):11663–11668

    Article  Google Scholar 

  • Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining

  • Kimura, Masahiro, Saito, Kazumi, Motoda, Hiroshi (2008) Minimizing the spread of contamination by blocking links in a network. In: Proceedings of the 23rd national conference on artificial intelligence - vol 2

  • Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, Makse HA (2010) Identification of influential spreaders in complex networks. Nat Phys 6(11):888–893

    Article  Google Scholar 

  • Lu W, Chen W, Lakshmanan LVS (2015) From competition to complementarity: comparative influence diffusion and maximization

  • Masahiro Kimura, Kazumi Saito, Hiroshi Motoda (2009) Blocking links to minimize contamination spread in a social network. ACM Trans Knowl Discov Data 3(2):1–23

    Article  Google Scholar 

  • Medya S, da Silva AL, Singh AK (2020) Approximate algorithms for data-driven influence limitation. IEEE Trans Know Data Eng 34(6):2641–2652

    Google Scholar 

  • Morone F, Makse HA (2015) Influence maximization in complex networks through optimal percolation. Nature 524(7563):65–68

    Article  Google Scholar 

  • Mugisha S, Zhou H-J (2016) Identifying optimal targets of network attack by belief propagation. Phys Rev E 94:012305

    Article  Google Scholar 

  • Paluck EL, Shepherd H, Aronow PM (2016) Changing climates of conflict: a social network experiment in 56 schools. Proc Natl Acad Sci 113(3):566–571

    Article  Google Scholar 

  • Ren X-L, Gleinig N, Helbing D, Antulov-Fantulin N (2019) Generalized network dismantling. Proc Nat Acad Sci 116(14):6554–6559

    Article  MathSciNet  Google Scholar 

  • Shao C, Ciampaglia GL, Varol O, Yang K-C, Flammini A, Menczer F (2018) The spread of low-credibility content by social bots. Nat Commun 9:4787

    Article  Google Scholar 

  • Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: a martingale approach. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data

  • Tong G, Du DZ (2019) Beyond uniform reverse sampling: a hybrid sampling technique for misinformation prevention

  • Tong G, Wu W, Du D (2018) Distributed rumor blocking with multiple positive cascades. IEEE Trans Comput Soc Syst 5(2):468–480

    Article  Google Scholar 

  • Vosoughi S, Roy D, Aral S (2018) The spread of true and false news online. Science 359(6380):1146–1151

    Article  Google Scholar 

  • Wang B, Chen G, Fu L, Song L, Wang X (2017) Drimux: dynamic rumor influence minimization with user experience in social networks. IEEE transactions on knowledge and data engineering

  • Wu P, Pan L (2017) Scalable influence blocking maximization in social networks under competitive independent cascade models. Comput Netw 123:38–50

    Article  Google Scholar 

  • Yan R, Li D, Wu W, Du DZ (2018) Minimizing influence of rumors by blockers on social networks. In: CSoNet

  • Yan R, Li D, Wu W, Du DZ, Wang Y (2020) Minimizing influence of rumors by blockers on social networks: algorithms and analysis. IEEE transactions on network science and engineering

  • Yao Q, Guo L (2015) Minimizing the social influence from a topic modeling perspective. In: ICDS

  • Yao Q, Zhou C, Xiang L, Cao Y, Guo L (2014) Minimizing the negative influence by blocking links in social networks. In: ISCTCS

  • Yao Q, Shi R, Zhou C, Wang P, Guo L (2015) Topic-aware social influence minimization. Proceedings of the 24th international conference on world wide web

  • Zhang H, Zhang H, Li X, Thai MT (2015) Limiting the spread of misinformation while effectively raising awareness in social networks. In: Computational social networks - 4th international conference, CSoNet, 9197: 35–47

  • Zhu J, Ni P, Wang G (2020) Activity minimization of misinformation influence in online social networks. IEEE Transact Comput Soc Syst 7(4):897–906

    Article  Google Scholar 

Download references

Acknowledgements

The work described in this paper was partially supported by InnoHK initiative, The Government of the HKSAR, and the Laboratory for AI-Powered Financial Technologies.

Funding

National Key Research and Development Program of China under Grant 2020YFB1005900, National Natural Science Foundation of China (NSFC) under Grant 62122042, Shandong University multidisciplinary research and innovation team of young scholars under Grant 2020QNQT017.

Author information

Authors and Affiliations

  1. School of Computer Science and Technology, Shandong University, No. 72 Binhai, Qingdao, Shandong, People’s Republic of China

    Qi Luo, Dongxiao Yu, Dongbiao Wang & Yanwei Zheng

  2. Department of Media and Communication, City University of Hong Kong, Tat Chee Avenue, Hong Kong S.A.R., People’s Republic of China

    Yafei Zhang

  3. Department of Computer Science, Georgia State University, 25 Park Place, Atlanta, GA, USA

    Zhipeng Cai

Authors
  1. Qi Luo
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Dongxiao Yu
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Dongbiao Wang
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Yafei Zhang
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Yanwei Zheng
    View author publications

    You can also search for this author inPubMed Google Scholar

  6. Zhipeng Cai
    View author publications

    You can also search for this author inPubMed Google Scholar

Contributions

QL and DY wrote the manuscript, YZ and YZ collected the data, DW designed the experiments, and ZC analyzed the results. All authors reviewed the results and approved the final version of the manuscript.

Corresponding author

Correspondence to Dongxiao Yu.

Ethics declarations

Conflict of interest

We declare that the authors have no known competing interests or personal relationships that might be perceived to influence the discussion reported in this paper.

Ethical approval

not applicable.

Additional information

Publisher's note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Luo, Q., Yu, D., Wang, D. et al. Influence blocking maximization under refutation. Soc. Netw. Anal. Min. 13, 143 (2023). https://doi.org/10.1007/s13278-023-01123-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s13278-023-01123-7

Keywords