Abstract
Currently, social networks have emerged as significant platforms for individuals to share personal information and social content. However, it is important to recognize that social networks have both positive and negative aspects. To effectively address the dissemination of negative social content such as rumors and misinformation, it is crucial to implement strategies that involve immediate blocking of associated links. This paper introduces a Negative Content Spread Minimization (NCSM) problem, which aims to minimize the spread of negative content by removing a set of edges from the network. We begin by demonstrating the NP-hardness of the NCSM problem through reduction from the Knapsack Problem. Furthermore, we establish that the objective function is not submodular under the Independent Cascade model. To address, we employ a distributed method which includes community partition and influential edges selection. The advantage of this approach is to reduce computational overhead by selecting key edges in parallel in each community. To evaluate proposed algorithm, we conduct experiments using real-world datasets and compare them against existing methods. The experimental results demonstrate that our method outperforms state-of-the-art algorithms.
This work was supported in part by the National Key R&D Program of China under Grants 2022YFB4501600 and 2022YFB4501603.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Bajpai, S., Chaturvedi, A.: A multi-criteria decision making based integrated approach for rumor prevention in social networks. Multimedia Tools Appl., 1–26 (2024)
Budak, C., Agrawal, D., El Abbadi, A.: Limiting the spread of misinformation in social networks. In: Proceedings of the 20th International Conference on World Wide Web, pp. 665–674. ACM (2011)
Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1029–1038. ACM (2010)
Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 199–208. ACM (2009)
He, Q., et al.: Graph convolutional network-based rumor blocking on social networks. IEEE Trans. Comput. Soc. Syst. (2022)
Jung, K., Heo, W., Chen, W.: IRIE: scalable and robust influence maximization in social networks. In: 2012 IEEE 12th International Conference on Data Mining, pp. 918–923. IEEE (2012)
Kimura, M., Saito, K., Motoda, H.: Minimizing the spread of contamination by blocking links in a network. In: Proceedings of the 23nd AAAI Conference of Artificial Intelligence, pp. 1175–1180. AAAI (2008)
Ni, Q., Guo, J., Huang, C., Wu, W.: Community-based rumor blocking maximization in social networks: algorithms and analysis. Theoret. Comput. Sci. 840, 257–269 (2020)
Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76(3), 036106 (2007)
Song, C., Hsu, W., Lee, M.L.: Node immunization over infectious period. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 831–840. ACM (2015)
Tong, G., et al.: An efficient randomized algorithm for rumor blocking in online social networks. IEEE Trans. Network Sci. Eng., 7, 845–854 (2017)
Wang, B., Chen, G., Fu, L., Song, L., Wang, X.: DRIMUX: dynamic rumor influence minimization with user experience in social networks. IEEE Trans. Knowl. Data Eng. 29(10), 2168–2181 (2017)
Yan, R., Li, Y., Li, D., Wang, Y., Zhu, Y., Wu, W.: A stochastic algorithm based on reverse sampling technique to fight against the cyberbullying. ACM Trans. Knowl. Discovery Data (TKDD) 15(4), 1–22 (2021)
Yan, R., Li, Y., Wu, W., Li, D., Wang, Y.: Rumor blocking through online link deletion on social networks. ACM Trans. Knowl. Discovery Data (TKDD) 13(2), 1–26 (2019)
Zi, H., Wu, S., Wu, K.: Hybrid control strategy for rumor spread in social networks. In: Jin, H., Pan, Y., Lu, J. (eds.) IAIC 2023. CCIS, vol. 2060, pp. 198–210. Springer, Singapore (2023). https://doi.org/10.1007/978-981-97-1332-5_16
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Yan, R., Guo, Z., Wu, W., Fan, B. (2024). A Distributed Method for Negative Content Spread Minimization on Social Networks. In: Ghosh, S., Zhang, Z. (eds) Algorithmic Aspects in Information and Management. AAIM 2024. Lecture Notes in Computer Science, vol 15179. Springer, Singapore. https://doi.org/10.1007/978-981-97-7798-3_14
Download citation
DOI: https://doi.org/10.1007/978-981-97-7798-3_14
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-7797-6
Online ISBN: 978-981-97-7798-3
eBook Packages: Computer ScienceComputer Science (R0)