Why Rumors Spread Fast in Social Networks, and How to Stop It

Ahad N. Zehmakan, Charlotte Out, Sajjad Hesamipour KhelejanIJCAI 2023 · DOI

TL;DR

This paper introduces a novel rumor spreading model that incorporates individual trust and forgetting mechanisms, and identifies graph properties like strong expansion and well-connected communities as crucial for rapid rumor dissemination. It also proposes and evaluates six countermeasures, finding that decentralized approaches significantly outperform centralized ones in stopping rumor spread.

What Problem Does This Paper Address?

The rapid spread of misinformation, particularly rumors, on social media poses significant societal challenges. While existing models capture aspects of rumor propagation, they often lack nuanced features like individual trust and the waning interest of spreaders over time. Furthermore, understanding why rumors spread so quickly in real-world networks and developing effective strategies to combat them remain open questions. This paper aims to bridge this gap by proposing a more realistic rumor spreading model and systematically investigating countermeasures, with a particular focus on decentralized solutions.

Methods

The authors introduce a rumor spreading model that builds upon existing frameworks like the Independent Cascade (IC) and Push-Pull models. Key novelties include:

  • Trust-based Spreading: The probability of an individual accepting a rumor from a connected spreader is proportional to the Jaccard similarity of their neighborhoods, serving as a proxy for trust.
  • Forgetting Mechanism: Spreaders gradually lose interest in the rumor over time, with their probability of spreading decreasing until they eventually stop. This is modeled by a parameter k, after which a spreader becomes "orange" (uninterested) and remains so.
  • Graph Property Analysis: The paper theoretically analyzes how graph structural properties, specifically "expansion" (how well-connected the graph is overall) and "community structure" (how densely connected nodes within groups are), influence rumor spread. They introduce concepts like "moderate expander graphs" for theoretical analysis.
  • Countermeasure Evaluation: Six distinct countermeasures are proposed and evaluated. These include traditional methods like blocking nodes/edges and novel approaches like "accuracy flags," "spreading the truth," "fact checkers," and "hearing it twice." The effectiveness of these countermeasures is assessed against four criteria: effectiveness, ease of application, not infringing on freedom of expression, and not being too intrusive.

Datasets

The authors utilized publicly available social network datasets for their experiments:

  • Twitter (TW): 81,306 nodes, 1,342,310 edges
  • Facebook (FB): 4,039 nodes, 88,234 edges
  • Google+ (G+): 107,614 nodes, 13,673,453 edges
  • Twitch Germany (T-GE): 9,498 nodes, 153,138 edges
  • Twitch France (T-FR): 6,549 nodes, 122,666 edges

They also generated synthetic graphs for theoretical analysis and experimental comparison:

  • Erdős-Rényi (ER) random graphs: Used to study the impact of random connectivity.
  • Hyperbolic Random Graphs (HRG): Used to model real-world network properties.
  • Flower Graphs and Moderate Expander Graphs: Specifically constructed graphs designed to isolate and study the effects of community structure and expansion properties, respectively.

Key Insights and Ideas

  • Community + Expansion = Fast Spread: The paper convincingly argues that it's not just one structural property, but the combination of strong expansion and well-connected local communities that drives the rapid spread of rumors in social networks. Sparse networks with only one of these properties may not see widespread dissemination.
  • Trust Matters: Incorporating trust (via Jaccard similarity) into the spreading probability makes the model more realistic, reflecting how people are more likely to believe information from those they know or have similar connections with.
  • Forgetting is Crucial: The "forgetting mechanism" is vital for explaining why rumors don't spread indefinitely and why their pace eventually slows. This is a significant departure from models that assume continuous spreading.
  • Decentralized Countermeasures Shine: The most impactful insight is that decentralized countermeasures (executed by individuals, like fact-checking or requiring multiple sources) are not only more aligned with user freedoms but also significantly more effective than centralized ones (like government-imposed blocking). This suggests a paradigm shift in how we should combat misinformation.

Key Results

  • Theoretical Findings:
    • Rumors do not spread with constant probability on Erdős-Rényi graphs with low edge density (p < 1/√n).
  • Rumors do not spread w.h.p. on flower graphs with few red "super nodes" (o(log n)).
  • Rumors do spread w.h.p. in O(log n) rounds on moderate expander graphs, demonstrating the power of combined expansion and community structure.
  • Experimental Findings:
    • Experiments on real-world networks (Twitter, Facebook) show that rumors spread to a large portion of the network quickly, supporting the theoretical findings that these networks possess a good level of expansion and community structure.
  • Countermeasure Effectiveness: * CM1 (Blocking Nodes) and CM2 (Blocking Edges) are not very effective and intrude on freedom of expression.
  • CM3 (Accuracy Flags) and CM4 (Spreading Truth) show some effect but don't stop rumors effectively.
  • CM5 (Fact Checkers) and CM6 (Hearing It Twice) are highly effective, with CM6 being particularly potent in preventing spread.
  • Table 1 summarizes that decentralized countermeasures (CM4, CM5, CM6) satisfy most desirable criteria (effectiveness, ease of application, freedom of expression, not intrusive), while centralized ones (CM1, CM2) fail on several fronts.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that real-world social networks may not perfectly match the idealized "moderate expander" graphs used for theoretical analysis, though they exhibit similar beneficial properties.
  • The quantitative assessment of countermeasure criteria (C1-C4) is subjective and relative.
  • Some countermeasures (CM2, CM3) were computationally expensive to run extensively.
  • Future Work:
    • Investigate other graph parameters that govern rumor spread.
  • Further explore and develop decentralized countermeasures, shifting focus away from centralized, regulatory approaches.
  • The authors suggest that educating network members is a more promising path than forceful regulation.

Summary updated

BibTeX
@inproceedings{zehmakan2023why,
  author = {Ahad N. Zehmakan and Charlotte Out and Sajjad Hesamipour Khelejan},
  title = {{Why Rumors Spread Fast in Social Networks, and How to Stop It}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/27},
}
Figure