PIDS: Decoding the Hardness and Efficiency of Influence Propagation in Social Networks

TL;DR

This paper provides a definitive study on the Positive Influence Dominating Set (PIDS) and its "Total" variant (TPIDS). The authors bridge the gap between complexity theory and practical social network analysis by proving tight inapproximability bounds—essentially showing that greedy algorithms are the best we can do for general graphs—while uncovering that real-world Power-law and Dense networks allow for much more efficient, constant-factor approximations.

Context & Motivation: The ρ-Fraction Challenge

In social dynamics, people rarely adopt a behavior based on a single contact. Instead, they require a fraction ρ of their social circle to adopt it (e.g., peer pressure in smoking or drinking). This leads to the PIDS problem: find the smallest set of seed nodes $P$ such that every node outside $P$ has at least $\rho$ fraction of its neighbors in $P$.

Previous research identified that this task is NP-hard, but the "hardness gap"—the difference between what we know is impossible to compute and what current algorithms achieve—remained wide. The authors sought to find the "Threshold of Hardness" and provide specialized solutions for non-random realistic networks.

Methodology: From Set Cover to Social Graphs

The core of the theoretical proof lies in a sophisticated reduction from Feige’s Set Cover gadget. Unlike prior works that used Set Cover as a "black box," the authors re-engineered the gadget to regulate node degrees.

The SCB-PIDS Reduction

They constructed a bipartite graph consisting of Elements ($U$) and Sets ($S$), and crucially added auxiliary sets $D$ and $D^{\prime }$ to force specific selection behaviors in the optimal solution. This allowed them to map the hardness of Set Cover (which is $lnn$) directly onto the PIDS problem.

Figure 1: The architecture used to transfer NP-hardness from Bounded Set Cover to PIDS.

General Approximation via CMM

The authors proved that PIDS is a subclass of the Constrained Multiset Multicover (CMM) problem. By doing so, they provided a unified proof that a simple greedy algorithm achieves an $ln\Delta +O(1)$ approximation ratio, which their hardness results show is essentially optimal.

Specialized Graph Classes: Power-law & Dense Networks

The most impactful part for practitioners is the analysis of Power-law networks (typical of OSNs like Twitter or Facebook). Utilizing the $P(\alpha ,\beta )$ random graph model and the Riemann Zeta function, they proved:

• In power-law graphs, the optimal PIDS size is often linear $\Omega (n)$.
• Insight: If the optimal set is large (a constant fraction of the network), even simple degree-based selection heuristics provide a constant-factor approximation, making large-scale viral marketing theoretically viable.

For Dense Graphs ($|E|=\Omega (|V{|}^2)$), they utilized a "hairy clique" model to prove that the TPIDS size is always at least $\Omega (\sqrt{|V|+|E|})$.

Figure 2: A 'hairy' clique construction proving the lower bound of TPIDS size in dense graphs.

Algorithms for Trees

While general graphs are hard, trees offer a path to optimality. The authors presented a Linear-Time DFS-based algorithm ($O(|V|)$) that replaces older $O(n^2)$ dynamic programming approaches. The algorithm works by visiting nodes in post-order and making greedy decisions based on an "uncovered" neighbor count ($r_p$).

Critical Insight & Conclusion

This paper serves as a theoretical anchor for social network influence. It tells us two things:

1. General Hardness: In an arbitrary graph, don't waste time looking for an algorithm better than Greedy; it's mathematically unlikely to exist.
2. Real-world Optimism: In real social networks (Power-law), high-degree nodes are so influential that straightforward selection strategies are surprisingly close to the mathematical optimum.

Takeaway: The "Positive Influence" requirement ($\rho \cdot d(v)$) is a much stricter constraint than simple domination, yet the structural regularity of social networks mitigates this complexity.