Truth Tracking in the Echo Chamber: How Weakly Connected Agents Learn in Dynamic Networks

TL;DR

In the hyper-dynamic landscape of social media, "truth" isn't a static destination but a moving target. This paper proposes a Multi-Armed Bandit (MAB) approach to help "followers" (weakly connected agents) learn a time-varying true state, even when dominated by influential personalities who might be spreading misinformation.

Background: The Static Truth Fallacy

Most academic models of social learning assume the True State ($heta$) is time-invariant. They envision a network where agents eventually reach a consensus on a fixed fact. However, in our reality of 24/7 news cycles, information is released and updated every second. The "truth" about a celebrity feud, a political event, or a market trend shifts constantly.

Furthermore, social networks are inherently hierarchical. We have:

• Strongly Connected Agents: Influencers who communicate bidirectionally.
• Weakly Connected Agents: Followers who act as "receivers only" and are easily dominated by the opinions of the leaders.

Why Previous Methods Fail

Traditional non-Bayesian diffusion learning succeeds when the state is constant but struggles in a dynamic setting. When the truth is arbitrarily time-varying, agents fail to converge. Prior work focused on influential hubs; this paper shifts the gaze to the "weakly connected" fringes—those most susceptible to manipulation—and asks: Can they still find the truth?

Methodology: Adversarial Multi-Armed Bandits meets Graph Theory

The author proposes an Online Diffusion Learning algorithm. Instead of just following a leader, agents treat the learning process as a game against an "oblivious adversary."

1. The Domination Number ($\delta$)

The core insight is the introduction of the Weak Domination Number. It represents the minimal set of "leader" nodes that influence the "follower" network. The algorithm uses this to calibrate the exploration-exploitation tradeoff.

2. The Algorithmic Loop

1. Intermediate Belief: Each agent generates a belief based on private noisy signals.
2. Consensus Probability: Agents combine their beliefs with their neighbors based on a weight matrix ($A$), even if they are in a subnetwork that is not "left-stochastic" (meaning they don't have equal influence).
3. Loss Estimation: Since an agent can't see the "loss" (error) of every possible state simultaneously, it uses an unbiased estimator to update its knowledge.
4. Exponential Update: Beliefs are updated using an exponential function of the estimated loss, ensuring that states yielding lower error gain higher probability over time.

Fig 1. Schematic showing how two influential subnetworks (top) dominate two receiving subnetworks (bottom).

Experimental Insights: The Cost of Being a Follower

The paper provides a theoretical "regret bound"—a measure of how often the agent is wrong compared to an omniscient oracle.

• Strongly Connected Regret: $O(T^{1/2})$
• Weakly Connected Regret: $O(T^{2/3})$

The higher exponent ($2/3$ vs $1/2$) indicates that while followers can learn the truth, their learning curve is significantly steeper. They suffer more "regret" (error) because their structural position in the graph limits their ability to verify information independently from their dominant influencers.

Fig 2. The sublinear regret comparison shows that weakly connected agents (proposed) accumulate error faster than strongly connected ones.

Critical Insight & Conclusion

The value of this work lies in its realism. By moving away from "stationary truth" and acknowledging the "receive-only" nature of most social media users, the author provides a template for more resilient social agents.

Takeaway: In a network, your position (topology) dictates your learning efficiency. If you are a "follower," you need more robust online learning algorithms (like MAB) to filter the noise from the shifting signals of those who dominate your feed.

Limitations: The exploration parameter ($\gamma$) is assumed to be uniform, and the "adversary" is assumed to be oblivious. Future work could explore active adversaries (e.g., bots specifically designed to counter-learn the agents' strategies).