GoDisco: Mimicking Social Intelligence for Selective Information Epidemics

TL;DR

GoDisco (Gossip in Discovery) is a decentralized algorithm that treats information dissemination like an intelligent "word-of-mouth" process. Unlike traditional gossip that floods every node, GoDisco uses social links and semantic categories to ensure messages reach only interested parties. It introduces Information Agents (IAs)—nodes that act as bridges—and a damping mechanism to balance the trade-off between reaching everyone (Recall) and not annoying anyone (Precision).

The Problem: The High Cost of "Shouting"

In a world of massive Online Social Networks (OSNs), disseminating a Call for Papers (CFP) or a targeted advertisement is a double-edged sword.

• Centralized systems (like mailing lists) require explicit subscriptions and create infrastructure bottlenecks.
• Traditional Gossip protocols are "epidemic"—they spread like a virus to everyone. While robust, they are notoriously inefficient for interest-specific content, leading to "Spam" (poor precision) and "Duplication" (network waste).

The authors noticed a gap: we have social graphs, and we have semantic interests. Why not use the Social Link as the primary filter?

Methodology: Engineering the "Information Agent"

GoDisco operates in two phases: Control and Dissemination.

1. The Power of Ranking (Control Phase)

Every node keeps a local score for its neighbors based on three factors:

• History ($h$): Does this neighbor actually forward useful stuff? (Resonating with the principle of reciprocity).
• Degree ($d$): Is this neighbor a "social butterfly" who can reach many others?
• Activeness ($a$): Is this node frequently online to pass the message quickly?

A weighted sum ($h\alpha +d\beta +a\gamma$) ranks neighbors as potential Information Agents (IAs). This allows the system to find the best "conduits" even if those conduits aren't interested in the message themselves.

2. Smart Forwarding (Dissemination Phase)

The algorithm uses an optimistic forwarding strategy. It categorizes neighbors into levels:

• Direct Hit: Neighbors with matching interests get the message immediately.
• Level 1 IA: Neighbors in the same "Main Category" (e.g., interested in ML vs. Data Mining) get it probabilistically.
• Damping & Random Walks: To prevent the message from dying in small "interest islands," GoDisco uses a dampingflag. If no relevant neighbors are found, it sends a limited "Random Walk" to high-ranking IAs to jump across gaps in the social graph.

Experimental Insights: Real-World Performance

The authors tested GoDisco on a massive DBLP co-authorship graph (284k authors) and synthetic Barabassi graphs.

The Recall-Precision Balance

In the DBLP dataset, the semantic structure is "tight." GoDisco achieved high recall with drastically lower spam compared to non-selective gossip.

• Random Walkers (RW) proved essential. In fragmented networks, RW increased the recall significantly (as seen in the DBLP results below), helping the message escape local cliques.

Feedback Loop Efficiency

One of the most profound findings was the Effect of Feedback. As the system handled more messages (the "1000th message" scenario), it effectively "learned" who the best forwarders were. This self-organization improved the network's ability to connect fragmented communities without increasing the spam rate.

Deep Insight & Conclusion

GoDisco represents a shift from topological gossip (where we care about graph connectivity) to socio-semantic gossip (where we care about human behavior).

Key Takeaways:

• Social links are filters: By using only social contacts, the system leverages pre-existing trust, which provides a natural disincentive for spreading "bogus" or spam messages.
• Structure matters: The algorithm performs exceptionally well in "Associativity-based" graphs (where friends share interests), which closely mirrors how professional communities (like DBLP) actually function.

Limitations: Performance does degrade in extremely sparse graphs where "bridges" are few and far between. Future work likely needs to address "adversarial gossip," where nodes might lie about their interests to attract or drop packets.

GoDisco proves that we don't need a central server to tell us who is interested in what; the social graph already contains that intelligence—we just need the right algorithm to unlock it.