Majority Vote in Social Networks: Make Random Friends or Be Stubborn to Overpower Elites

Charlotte Out, Ahad N. ZehmakanIJCAI 2021 · DOI

TL;DR

This paper investigates the "majority model" of opinion diffusion in social networks, where individuals adopt the most common opinion among their neighbors. The authors show that in real-world networks, a small group of influential "elites" can disproportionately sway the outcome. They propose and validate two practical countermeasures: encouraging random connections and increasing individual "stubbornness" to resist influence.

What Problem Does This Paper Address?

In social networks, opinions spread and evolve. A common model for this is the "majority model," where each person (node) updates their opinion (color, e.g., black/white) to match the majority opinion of their connections. While this model is intuitive, real-world social networks exhibit a phenomenon where a small, highly connected group of individuals (elites) can dominate the outcome, effectively engineering the consensus. This raises questions about the robustness of opinion dynamics and whether individuals can resist such manipulation. The paper aims to understand this elite influence and propose effective, easy-to-implement strategies for individuals to counteract it.

Methods

The authors employ a combination of theoretical analysis and empirical experiments.

  • Theoretical Framework: They analyze the majority model and a generalized version called the $(\psi_1, \psi_2)$-majority model, where nodes have different thresholds for changing their opinion based on neighbor's opinions. They develop mathematical proofs for their proposed countermeasures.
  • Countermeasure 1 (Random Connections): They theoretically prove that adding a "regular random graph" (a graph where every node has the same degree) with strong expansion properties on top of an existing network significantly weakens the power of elite nodes. This is akin to individuals making random new connections.
  • Countermeasure 2 (Stubbornness): They demonstrate that assigning a "stubbornness factor" to nodes, making them less likely to change their opinion unless a very strong majority of neighbors agree, also prevents elites from dominating.
  • Experimental Validation: They conduct experiments on real-world social network datasets (Facebook, YouTube, Twitter, Slashdot) and various random graph models (Erdős-Rényi, Random Regular Graph, Preferential Attachment, Hyperbolic Random Graph) to validate their theoretical findings. They measure the minimum size of an "elite winning set" under different conditions and after applying their countermeasures.

Datasets

The paper uses the following real-world social network datasets:

  • Facebook (FB)
  • YouTube (YT)
  • Twitter (TW)
  • Slashdot (SD)

These datasets were converted into undirected graphs. They also compare their findings with several random graph models:

  • Erdős-Rényi (ER) Random Graph
  • Random Regular Graph (RRG)
  • Preferential Attachment (PA) Random Graph
  • Hyperbolic Random Graph (HRG)

Key Insights and Ideas

  • Elite Dominance is Real: In real-world social networks, a surprisingly small percentage of high-degree nodes (elites) can dictate the final opinion outcome, even with moderate influence. This is less pronounced in purely random graph models like PA.
  • Countermeasures Work: Both adding random connections (represented by RRG) and increasing individual stubbornness are effective in significantly increasing the size of an elite group needed to control the outcome.
  • Randomness as a Stabilizer: Introducing random connections acts as a powerful equalizer, diluting the concentrated influence of elites.
  • Stubbornness as a Shield: Individual resistance to influence, even if not absolute, can collectively thwart coordinated manipulation by elites.
  • Threshold Behavior: The paper confirms and extends findings on threshold behavior in opinion dynamics, where small changes in initial opinion distribution (probability of being black/white) can lead to drastic shifts in the final outcome, especially in random graphs.
  • Poly-logarithmic Stabilization: The authors provide evidence and theoretical arguments supporting the conjecture that opinion dynamics in many network settings stabilize in a poly-logarithmic number of rounds, rather than linearly with the number of edges.

Key Results

  • Elite Influence: In real-world SNs like YT, an elite set of just 1% of nodes with an influence factor of 8 could form a winning set.
  • Countermeasure Effectiveness:
    • Adding an RRG (Countermeasure 1) to FB SN increased the required elite winning set size from 0.4% to 10% (with influence factor 16).
  • Assigning a high stubbornness factor (Countermeasure 2) to FB SN nodes increased the required elite winning set size to 33%.
  • Thresholds in Random Graphs: For the $(\psi_1, \psi_2)$-majority model on dense Erdős-Rényi graphs, they prove a clear two-phase transition behavior at specific probabilities related to $\psi_1$ and $\psi_2$. Experiments suggest similar, though shifted, thresholds in other graph types.
  • Stabilization Time: They prove that for a cycle graph $C_n$, the majority model stabilizes in $O(\log n)$ rounds. Their experimental results on various networks suggest poly-logarithmic stabilization times in practice.

Limitations and Future Work

  • Elites with Extreme Influence: The paper notes that if elites possess extremely large influence factors, even the addition of a complete graph might not fully neutralize their power.
  • Generalizing Countermeasures: While the theoretical results for Countermeasure 1 are for specific graph structures (RRG), the experimental results suggest broader applicability. Future work could explore more general conditions for this countermeasure.
  • Threshold Values: For the $(\psi_1, \psi_2)$-majority model, while threshold behavior is observed in various graphs, the exact threshold values differ from the theoretical predictions for dense ER graphs. Determining these values for different network types is an open question.
  • Poly-logarithmic Stabilization Conjecture: While strong evidence is presented, a general proof for the poly-logarithmic stabilization time conjecture across all network types remains an open problem. The paper's work on the $(\psi, \psi)$-majority model and bichromatic edges is presented as a potential stepping stone.

Summary updated

BibTeX
@inproceedings{out2021majority,
  author = {Charlotte Out and Ahad N. Zehmakan},
  title = {{Majority Vote in Social Networks: Make Random Friends or Be Stubborn to Overpower Elites}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/49},
}
Figure