Scaling Competitive Diffusion: A Logic-Based Framework for Social Network Dynamics

TL;DR

Predicting how competing ideas or products spread in a massive social network is traditionally a computational nightmare. This paper introduces a framework called Weighted Generalized Annotated Programs (wGAP) to model these "winner-takes-all" scenarios and presents the CODE algorithm, which leverages graph partitioning to scale these predictions to networks with millions of individuals.

Problem & Motivation: The Battle for Mindshare

In the real world, diffusion is rarely a solitary process. If you buy an iPhone, you likely won't buy an Android; if you vote for Candidate A, you cannot vote for Candidate B. This is Competitive Diffusion.

Prior work often focused on "viral marketing" for a single product. When competition was considered, models were often limited to static competitors or lacked a way to handle complex relationships (like the difference between a "boss" and a "friend"). The academic challenge is two-fold:

1. Modeling Complexity: How do we represent diverse relationship types and logical constraints (e.g., probabilities of voting must sum to $\le 1$)?
2. Computational Scale: Standard optimization methods for these models typically scale cubically $O(N^{3.5})$, making them useless for a platform like Facebook or Twitter.

Methodology: Logic Meets Graph Community Detection

1. wGAP: A Language for Influence

The authors use Weighted Generalized Annotated Programs (wGAP). This allows researchers to write rules like: "If your mentor votes for the Labour party, there is a 0.25 probability you will too, provided you are also a student."

The framework uses Integrity Constraints (ICs) to ensure that the resulting probabilities make physical sense—preventing a node from "fully" adopting two mutually exclusive products.

2. The CODE Algorithm: Divide and Conquer

Instead of solving the "Most Probable Interpretation" (MPI) for the entire network at once, the Competing Diffusion Engine (CODE) algorithm uses a clever trick:

• Dependency Graph: It builds a graph where nodes are variables and edges represent their logical dependencies.
• Clustering: It uses greedy modularity optimization to find "communities" within this dependency graph.
• Local Optimization: It solves numerous small optimization problems (DOPs) within these communities and iterates until the values converge across the whole network.

Fig 1: A multi-relational social network example where different edge types (knows, idol, olderRel) govern the flow of influence.

Experiments & Results: Real-World Scalability

The authors tested their approach on synthetic networks ranging from 10k to 8 million edges.

• Efficiency: While exact methods (SNF) became intractable very quickly, CODE handled millions of edges with approximately linear time complexity.
• Accuracy: By adjusting a "conservatism" parameter, the authors showed that they could trade off a small amount of accuracy for massive gains in speed. Even at high speeds, the approximation error remained stable and low.

Fig 2: Runtime comparison showing the CODE algorithm maintaining performance as the network size grows, while exact algorithms spike in complexity.

Critical Insight: Why This Matters

The genius of this work isn't just in the logic—it's in the realization that social networks are naturally modular. Because people cluster into communities, the "influence" dependencies are also clustered. By aligning the optimization algorithm with the natural topology of the social graph, the authors bypassed the "curse of dimensionality" that usually plagues global optimization.

Limitations & Future Work

• Dynamic Networks: The current model assumes a static graph. Real-world social networks have edges that appear and disappear.
• Weight Learning: While the paper mentions weight fitting via gradient descent, the real-world challenge lies in collecting high-quality "ground truth" data for training these weights in competitive settings.

Conclusion

This paper bridges the gap between high-level logical reasoning and big-data engineering. It proves that we can model not just what spreads, but how competing forces balance out across millions of interactions, providing a structured way to simulate market wars and political shifts.