CompeteRank: Tracing Influential Nodes in a Competitive Social Wilderness

TL;DR

When iPhone and Android compete for the same user, the "first-come, first-served" rule of traditional social influence often fails. This paper presents the Weighted Competitive Independent Cascade Model (WCICM) to account for user preferences. Crucially, it proves that competition destroys the "submodularity" (diminishing returns) that greedy algorithms rely on. To solve this, the authors introduce CompeteRank, a reverse random-walk heuristic that finds the best seed nodes by tracing information back to its source, outperforming standard heuristics in speed and accuracy.

The "Death" of Submodularity in Competition

In classic influence maximization (IM), adding one more seed node always helps, but the incremental gain decreases as the seed set grows. This property, submodularity, is the "Holy Grail" that allows a simple greedy search to get within 63% of the optimal solution.

However, the authors demonstrate that in a competitive environment—where nodes choose between information based on weighted preferences—this logic breaks. They provide a counter-example showing that a seed node might have a larger marginal gain on a larger set than a smaller one because it might "block" an adversary just in time. This realization means the industry's go-to greedy algorithms are no longer theoretically safe and remain computationally sluggish.

Methodology: The Logic of Reverse Tracing

Instead of simulating forward cascades (which is like trying to predict every ripple in a pond), the authors ask: "If everyone was already convinced by us, where did they likely get the idea from?"

The CompeteRank Architecture

The core of the method is a Markov process. The paper defines a transition matrix $P$ where the probability of moving from node $u$ back to $v$ is determined by how much $v$ influences $u$ relative to other neighbors.

1. Shortest Path Modeling (SPM): To make the competition tractable, they assume nodes are reached via the shortest path from seeds. This allows them to estimate the "Diffusion Step" ($T$) for adversary information.
2. Weighted Transition: An edge $(v,u)$ gets more weight if $v$ can reach $u$ before or at the same time as the adversary, adjusted by the node's preference $\varphi$.

In the figure above, the diffusion steps (in brackets) show how adversary seeds (0 and 9) lock down certain nodes, determining the competitive environment in which our seeds must operate.

Experimental Battleground

The authors tested CompeteRank against Greedy, Degree Centrality, and specialized heuristics like "Largest Infectees" on academic collaboration networks (ca-GrQc, ca-HepTh).

Key Findings:

• Performance: CompeteRank consistently matches or exceeds the Greedy algorithm. Specifically, in scenarios where the adversary is "stronger" (higher weight), CompeteRank's ability to selectively target nodes that can "beat" the adversary is most evident.
• Scalability: The Greedy algorithm is notoriously slow. CompeteRank, being a random walk, converges rapidly (usually within 50 iterations) and its runtime remains stable even as the network grows to tens of thousands of nodes.

Experimental results across different datasets show CompeteRank (solid line with circles) maintaining a top-tier position compared to heuristics like Degree Centrality.

Critical Insight & Conclusion

The true value of this paper lies in its rejection of the "greedy-is-enough" status quo. By acknowledging that competition changes the mathematical landscape (losing submodularity), it shifts the focus toward topological tracing.

Takeaway: If you are launching a product in a market already saturated by a competitor, don't just look for high-degree "influencers." Look for nodes that can reach "undecided" clusters faster or with more weight than your rival. CompeteRank provides the mathematical framework to do exactly that at scale.