MPPIDS: Efficiently Influencing Social Networks with Partial Coverage

TL;DR

In the vast landscape of Online Social Networks (OSNs), influencing every single user is a "mission impossible" due to budget constraints. This paper introduces the Minimum Partial Positive Influence Dominating Set (MPPIDS) problem. Instead of total coverage, it asks: How can we influence at least p% of the network with the fewest seeds? The authors provide a greedy algorithm with a $\gamma H(\Delta )$ approximation ratio and prove that in Power-law graphs (like Facebook or Twitter), this approach yields a constant factor approximation, making it highly effective for real-world scaling.

Motivation: The Cost of Perfection

The classical Dominating Set (DS) and its variant Positive Influence Dominating Set (PIDS) assume a binary stability: a node is "influenced" if a certain percentage of its neighbors are. However, requiring 100% of nodes to satisfy this condition is often overkill.

The authors argue that in social interventions (e.g., stopping smoking or promoting a viral product), achieving a high percentage $p$ is sufficient. The challenge is that "Partial" problems are frequently more computationally complex than "Total" ones because the algorithm must decide not just who to pick, but who to ignore to minimize costs.

Methodology: Dual-Fitting & Greedy Selection

The authors generalize the problem into the Minimum Cost Partial Set Multicover (PSMC).

1. The Greedy Strategy

The algorithm operates on a simple but powerful "Cost-Effectiveness" metric: $ce(S)=\frac{c(S)}{extnumberofcurrentlyaliveelementsinS}$ A node is "alive" if it hasn't yet met its requirement of being covered by $\lceil \rho d(v)\rceil$ neighbors. The algorithm iteratively picks the set $S$ with the lowest $ce(S)$ until the $k=\lceil pn\rceil$ coverage threshold is met.

2. Theoretical Backbone: Dual-Fitting

To prove how good this greedy approach is, the authors use Dual-Fitting. They construct a feasible solution for the dual of the Linear Programming relaxation of PSMC. By scaling the greedy costs, they show that the total cost of their selection is at most $\gamma H(\Delta )$ times the optimal cost.

Note: The figure above illustrates the fundamental structure of social network influence models used in the study.

Why Power-Law Graphs Matter

Social networks are not random; they follow a Power-law distribution ($n_i\propto i^{-\beta }$). Most nodes have few connections, while a few "hubs" have many.

The paper's most significant contribution is the proof that in such graphs, the optimal size of an MPPIDS is proportional to the total number of nodes ($V=\Omega (n)$).

• The Insight: Because the optimal solution is large, even a "naive" feasible solution stays within a constant factor of the optimum.
• Impact: While the approximation ratio might look scary in general graphs ($\gamma H(\Delta )$), it collapses to a constant in the real-world networks we actually care about.

Experimental Analysis & Results

The study establishes:

1. General Performance: For general graphs, the ratio is $\gamma H(\Delta )$, where $\gamma$ increases as the required coverage $p$ increases.
2. Power-law Robustness: Any algorithm producing a feasible solution for PPIDS in a power-law graph $P(\alpha ,\beta )$ with $\beta >1$ achieves a constant performance ratio.

The derivation above proves the $\Omega (n)$ lower bound, which is the cornerstone for the constant approximation claim.

Critical Insights & Conclusion

This research provides a rigorous mathematical foundation for "good enough" social influence.

• Takeaway: If you are running a campaign on a Power-law network, a greedy approach isn't just a heuristic—it's theoretically sound and provides guaranteed performance.
• Limitations: The current $\gamma$ bound requires $k$ to be relatively large ($k>(1-1/\eta )n$). Future work is needed to explore lower coverage thresholds where $\eta$ (related to degree variance) becomes a dominant factor.
• Future Work: Transitioning these static models into dynamic temporal networks where influence decays over time would be the next logical step for this research.