Community-based rumor blocking maximization in social networks: Algorithms and analysis.

Area of Science:

• Computer Science
• Social Network Analysis
• Information Science

Background:

• Social networks facilitate communication but also enable rapid spread of misinformation.
• Misinformation can lead to significant societal disruptions, including public panic and economic instability.
• Existing methods often overlook the community structure inherent in social networks.

Purpose of the Study:

• To propose a novel Community-based Rumor Blocking Problem (CRBMP) for social networks.
• To develop an efficient algorithm for selecting seed users (protectors) to maximize rumor blocking.
• To consider budget constraints in the protector selection process.

Main Methods:

• The problem is solved in two stages: budget allocation across communities and protector seed selection within communities.
• The first stage utilizes submodular function maximization on an integer lattice, employing greedy and speed-up greedy algorithms.
• The second stage uses a greedy approach for protector selection, achieving a 1/2 approximation guarantee.

Main Results:

• The proposed greedy community budget allocation algorithm achieves an approximation ratio.
• A speed-up greedy algorithm reduces computational cost while maintaining a strong approximation guarantee.
• Experimental results on real-world datasets validate the algorithm's effectiveness and superiority over other methods.

Conclusions:

• The CRBMP effectively addresses misinformation spread by leveraging social network community structures.
• The proposed two-stage algorithmic approach provides efficient and effective solutions for rumor blocking.
• The study demonstrates the practical applicability and performance of the developed methods in combating online rumors.