Top

World Wide Web

Published in:

01-01-2024

Rumor blocking with pertinence set in large graphs

Authors: Fangsong Xiang, Jinghao Wang, Yanping Wu, Xiaoyang Wang, Chen Chen, Ying Zhang

Published in: World Wide Web | Issue 1/2024

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Online social networks facilitate the spread of information, while rumors can also propagate widely and fast, which may mislead some users. Therefore, suppressing the spread of rumors has become a daunting task. One of the widely used approaches is to select users in the social network to spread the truth and compete against the rumor, so that users who receive the truth before receiving rumors will not trust or propagate the rumor. However, the existing works only aim to speed up blocking rumors without considering the pertinency of users. For example, consider a social media platform operator aiming to enhance user online safety. Based on the user’s online behavior, the users who are at high risk should be alerted first. Motivated by this, we formally define the rumor blocking with pertinence set (RBP) problem, which aims to find a truth seed set that maximizes the number of nodes affected by truth and ensures that the number of influenced nodes within the pertinence set reaches at least a given threshold. To solve this problem, we design a hybrid greedy framework (HGF) algorithm with local and global phases. We prove that HGF can provide a \((1-1/e-\epsilon )\)-approximate solution with high probability while reducing the cost of the sampling process. Extensive experiments on 8 real social networks demonstrate the efficiency and effectiveness of our proposed algorithms.

previous article Efficient approximation and privacy preservation algorithms for real time online evolving data streams

next article Adaptive retrofitting for industrial machines: utilizing webassembly and peer-to-peer connectivity on the edge

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

http://snap.stanford.edu

Borgs, C., Brautbar, M., Chayes, J., Lucier, B.: Maximizing social influence in nearly optimal time. In: SODA, pp. 946–957 (2014)

Borodin, A., Filmus, Y., Oren, J.: Threshold models for competitive influence in social networks. In: Internet and Network Economics, pp. 539–550 (2010)

Budak, C., Agrawal, D., El Abbadi, A.: Limiting the spread of misinformation in social networks. In: WWW, pp. 665–674 (2011)

Chen, C., Zhang, M., Sun, R., Wang, X., Zhu, W., Wang, X.: Locating pivotal connections: the k-truss minimization and maximization problems. World Wide Web 25(2), 899–926 (2022)CrossRef

Chen, C., Zhu, Q., Sun, R., Wang, X., Wu, Y.: Edge manipulation approaches for k-core minimization: Metrics and analytics. TKDE 35(1), 390–403 (2023)

Chen, C., Zhu, Q., Wu, Y., Sun, R., Wang, X., Liu, X.: Efficient critical relationships identification in bipartite networks. World Wide Web 25(2), 741–761 (2022)CrossRef

Chen, W., Lakshmanan, L.V.S., Castillo, C.: Information and Influence Propagation in Social Networks. Synthesis Lectures on Data Management. Morgan & Claypool Publishers (2013)

DSouza, K.M., French, A.M.: Fake news detection using machine learning: an adversarial collaboration approach. Int. Res. (2023)

Guo, Q., Wang, S., Wei, Z., Chen, M.: Influence maximization revisited: efficient reverse reachable set generation with bound tightened. In: SIGMOD, pp. 2167–2181 (2020)

10.

He, Q., Zhang, D., Wang, X., Ma, L., Zhao, Y., Gao, F., Huang, M.: Graph convolutional network-based rumor blocking on social networks. TCSS 1–10 (2022)

11.

Huang, K., Wang, S., Bevilacqua, G., Xiao, X., Lakshmanan, L.V.: Revisiting the stop-and-stare algorithms for influence maximization. VLDB 913–924 (2017)

12.

Jiang, Z., Chen, X., Ma, J., Yu, P.S.: Rumordecay: rumor dissemination interruption for target recipients in social networks. IEEE Trans. Syst. Man Cybern. 6383–6395 (2022)

13.

Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: SIGKDD, pp. 137–146 (2003)

14.

Khalil, E.B., Dilkina, B., Song, L.: Scalable diffusion-aware optimization of network topology. In: SIGKDD, pp. 1226–1235 (2014)

15.

Liu, C., Zhou, X., Zehmakan, A.N., Zhang, Z.: A fast algorithm for moderating critical nodes via edge removal. IEEE Trans. Knowl. Data Eng. (2023)

16.

Manouchehri, M.A., Helfroush, M.S., Danyali, H.: Temporal rumor blocking in online social networks: A sampling-based approach. IEEE Trans. Syst. Man Cybern. 4578–4588 (2022)

17.

Nguyen, H.T., Thai, M.T., Dinh, T.N.: Stop-and-stare: optimal sampling algorithms for viral marketing in billion-scale networks. In: SIGMOD, pp. 695–710 (2016)

18.

Song, C., Hsu, W., Lee, M.L.: Node immunization over infectious period. In: CIKM, pp. 831–840 (2015)

19.

Sun, R., Chen, C., Liu, X., Xu, S., Wang, X., Lin, X.: Critical nodes identification in large networks: The inclined and detached models. World Wide Web 25(3), 1315–1341 (2022)CrossRef

20.

Sun, R., Chen, C., Wang, X., Wu, Y., Zhang, M., Liu, X.: The art of characterization in large networks: Finding the critical attributes. World Wide Web 25(2), 655–677 (2022)CrossRef

21.

Tang, J., Tang, X., Xiao, X., Yuan, J.: Online processing algorithms for influence maximization. In: SIGMOD, pp. 991–1005 (2018)

22.

Tang, J., Tang, X., Yuan, J.: Profit maximization for viral marketing in online social networks: Algorithms and analysis. TKDE 1095–1108 (2018)

23.

Tang, Y., Shi, Y., Xiao, X.: Influence maximization in near-linear time: a martingale approach. In: SIGMOD, pp. 1539–1554 (2015)

24.

Tong, G., Wu, W., Du, D.Z.: Distributed rumor blocking with multiple positive cascades. TCSS 468–480 (2018)

25.

Tong, G., Wu, W., Guo, L., Li, D., Liu, C., Liu, B., Du, D.Z.: An efficient randomized algorithm for rumor blocking in online social networks. TNSE 845–854 (2017)

26.

Tong, H., Prakash, B.A., Eliassi-Rad, T., Faloutsos, M., Faloutsos, C.: Gelling, and melting, large graphs by edge manipulation. In: CIKM, pp. 245–254 (2012)

27.

Tsai, J., Nguyen, T.H., Tambe, M.: Security games for controlling contagion. In: AAAI (2012)

28.

Wang, B., Chen, G., Fu, L., Song, L., Wang, X.: Drimux: dynamic rumor influence minimization with user experience in social networks. TKDE 2168–2181 (2017)

29.

Wang, X., Zhang, Y., Zhang, W., Lin, X.: Distance-aware influence maximization in geo-social network. In: ICDE, pp. 1–12 (2016)

30.

Wang, X., Zhang, Y., Zhang, W., Lin, X.: Efficient distance-aware influence maximization in geo-social networks. TKDE 599–612 (2017)

31.

Wang, X., Zhang, Y., Zhang, W., Lin, X., Chen, C.: Bring order into the samples: a novel scalable method for influence maximization. TKDE 29(2), 243–256 (2017)

32.

Wu, H., Zhang, Z., Fang, Y., Zhang, S., Jiang, Z., Huang, J., Li, P.: Containment of rumor spread by selecting immune nodes in social networks. Math. Biosci. Eng 2614–2631 (2021)

33.

Xie, J., Zhang, F., Wang, K., Lin, X., Zhang, W.: Minimizing the influence of misinformation via vertex blocking. In: ICDE, pp. 789–801 (2023)

34.

Yan, R., Li, D., Wu, W., Du, D.Z., Wang, Y.: Minimizing influence of rumors by blockers on social networks: algorithms and analysis. TNSE 1067–1078 (2019)

35.

Yang, L., Ma, Z., Li, Z., Giua, A.: Rumor containment by blocking nodes in social networks. IEEE Trans. Syst. Man Cybern. (2023)

36.

Zhang, P., Chen, W., Sun, X., Wang, Y., Zhang, J.: Minimizing seed set selection with probabilistic coverage guarantee in a social network. In: SIGKDD, pp. 1306–1315 (2014)

37.

Zhang, X., Wang, H., Yu, J., Chen, C., Wang, X., Zhang, W.: Polarity-based graph neural network for sign prediction in signed bipartite graphs. World Wide Web 25(2), 471–487 (2022)CrossRef

38.

Zhang, X., Wang, H., Yu, J., Chen, C., Wang, X., Zhang, W.: Bipartite graph capsule network. World Wide Web 26(1), 421–440 (2023)CrossRef

Title: Rumor blocking with pertinence set in large graphs
Authors: Fangsong Xiang
Jinghao Wang
Yanping Wu
Xiaoyang Wang
Chen Chen
Ying Zhang
Publication date: 01-01-2024
Publisher: Springer US
Published in: World Wide Web / Issue 1/2024
Print ISSN: 1386-145X
Electronic ISSN: 1573-1413
DOI: https://doi.org/10.1007/s11280-024-01235-w

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 1/2024

Adaptive retrofitting for industrial machines: utilizing webassembly and peer-to-peer connectivity on the edge

Knowledge-enhanced personalized hierarchical attention network for sequential recommendation

Discrete cross-modal hashing with relaxation and label semantic guidance

Privacy-preserving data publishing: an information-driven distributed genetic algorithm

A novel robust memetic algorithm for dynamic community structures detection in complex networks

Efficient approximation and privacy preservation algorithms for real time online evolving data streams

Premium Partner