Hardness of Influence: Why Optimal Viral Marketing is Practically Impossible

TL;DR

In the world of social networks, finding the smallest set of people to start a massive trend seems like a dream for marketers. However, this paper by Ning Chen proves it is a mathematical nightmare. The research shows that the Target Set Selection problem is not just NP-hard, but effectively impossible to even approximate within any reasonable factor, even when the rules are as simple as "I'll join if two of my friends do."

The Background: Beyond Submodularity

The study of influence diffusion was popularized by Kempe, Kleinberg, and Tardos, who showed that if influence is "probabilistic," a greedy approach works well because the function is submodular (exhibiting diminishing returns).

Ning Chen shifts the lens to a deterministic threshold model:

• Every node $v$ has a threshold $t_v$.
• A node becomes active if $t_v$ of its neighbors are already active.
• The Goal: Find the minimum set $S$ to activate the whole network.

The problem? Without the "randomness" of prior models, the submodularity vanishes. Influence doesn't just diminish; it can hit "dead ends" or "tipping points" in ways that are computationally impossible to predict efficiently.

Hardness: The Polylogarithmic Barrier

The core contribution of this paper is a proof that we cannot approximate the optimal seed set within a factor of $O(2^{{\log }^{1-ϵ}n})$. This is significantly worse than the logarithmic bounds we see for problems like Set Cover.

1. The MinRep Reduction

The author maps the Minimum Representative (MinRep) problem—a notoriously hard problem from complexity theory related to two-prover one-round systems—onto the social network graph.

Figure 1: The architecture used to prove that selecting influencers is as hard as the MinRep problem.

The "Threshold 2" Surprise

One of the most elegant parts of the paper is the treatment of small thresholds. Intuition might suggest that if people are very easy to influence (e.g., they only need 2 friends to adopt a product), finding the best starters should be easier.

Chen proves this intuition wrong. By simulating monotone boolean circuits (using AND and OR gates), the author shows that even with a threshold of 2, the graph can compute complex logic that hides the optimal starting set.

• AND Gate Gadget: Requires both inputs to be active to trigger the output.
• OR Gate Gadget: Requires only one input to trigger the output.

Figure 2: A gadget simulating an AND gate using nodes with threshold 2.

Specialized Cases: Trees and Unanimous Rules

While the general case is bleak, the paper offers some "silver linings":

• Unanimous Thresholds: If everyone requires all their neighbors to switch before they do (the most influence-resistant setting), the problem becomes equivalent to Vertex Cover. In this case, a 2-approximation is possible.
• Tree Structures: Social networks that follow a hierarchy or tree structure can be solved optimally in polynomial time using a simple dynamic programming approach (bottom-up activation).

Critical Insight

The real value of this work is its "negative" result. It serves as a warning to researchers and practitioners: Do not look for a general-purpose optimal algorithm for deterministic influence.

If your model assumes fixed thresholds (e.g., a "majority" rule), the search for the perfect seed set is mathematically futile in the general case. Instead, focus on the specific topology of your network (like trees) or revert to probabilistic models where the "greed" of submodularity can be exploited.

Conclusion

Ning Chen’s work effectively "closes" the debate on the approximability of deterministic influence. By bridging social network theory with circuit complexity and the AKS sorting network, it highlights a deep truth: complexity isn't just about the size of the network, but the logic hidden within the connections.