Beyond Simple Dominance: Complexity and Approximation of Majority-Based Social Influence

TL;DR

In social networks, "influence" often requires more than just one contact; it requires a majority of your peers. This paper formalizes the (*)-Dominating Set, a mathematical model for this majority influence. The authors prove that finding the smallest such set is computationally "tough" (APX-hard) and provide a greedy strategy that guarantees an approximation within a factor of $O(\ln extdegree)$ of the perfect solution.

The "Why": Why 50% Neighbors?

In traditional network theory, a Dominating Set is a group of nodes such that everyone else is at least one step away. While useful for radio towers or routing, it’s a poor model for social pressure. We often don't adopt a new behavior (like a new app or a political view) just because one friend does; we do it when a significant portion of our circle does.

The (*)-dominating set requires that for every person not in the "influencer" set, at least half of their neighbors must be. This transforms the problem from a simple "reachability" task to a "threshold" task, which is significantly more difficult to optimize.

Methodology: The Geometry of Influence

The authors tackle two versions of this problem:

1. DS-(*): Find the smallest set satisfying the 50% rule.
2. CDS-(*): Find the smallest set that is both 50%-dominant and interconnected.

1. Proving Complexity (APX-Hardness)

To show how hard this is, the authors use an L-reduction from Vertex Cover on cubic graphs (VC-3). They build a custom graph $G^{\prime }$ where satisfyng the (*)-dominating condition in $G^{\prime }$ is mathematically equivalent to solving the Vertex Cover in the original graph.

2. The Greedy Approach and Submodularity

The core of the solution lies in Submodular Functions. Think of submodularity as the "law of diminishing returns": as your set grows, the extra benefit of adding one more person decreases.

The authors construct a specific function $g(A)$ that tracks how close a set is to satisfying the (*)-condition. They prove $g(A)$ is a polymatroid function, which is the "green light" needed to use a Greedy Algorithm with a guaranteed performance ratio of $H(\lceil (3/2)\delta \rceil )$.

Connectivity: The Hard Part

When you add the requirement that the influencers must be connected (CDS-(*)), the "diminishing returns" property breaks. Adding a node might connect two distant groups, creating a massive leap in progress—this is non-submodular behavior.

To solve this, the authors utilize a potential function $t(A)$ that combines:

• Influence Progress ($g(A)$)
• Connectivity Progress (number of components)

Experiments & Results: How Good is "Greedy"?

The results establish theoretical upper bounds on error. For a graph with a maximum degree $\delta$:

• DS-(*): The solution is at most $\approx \ln (1.5\delta )$ times larger than the absolute minimum.
• CDS-(*): The solution is at most $2+\ln (2.5\delta )$ times larger than the absolute minimum.

This is a major win for practitioners. It means that even though the problem is NP-hard, a simple greedy choice (repeatedly picking the node that helps satisfy the most 50% requirements) is mathematically "close enough" to the best possible strategy.

Critical Insight & Outlook

Wait, can we do better? The authors note that while they achieved logarithmic bounds, there is still a gap between the $O(\ln \delta )$ upper bound and the potential lower bounds of $O(\ln n)$.

Takeaway: This paper bridges the gap between social intuition and rigorous graph theory. By proving APX-hardness, it warns us not to look for a perfect polynomial-time algorithm, but by providing the greedy bounds, it gives us a highly efficient tool for viral marketing and network design.

Future research should investigate if these bounds hold in "scale-free" networks where a few nodes (hubs) have extremely high degrees, as the current $\ln \delta$ ratio might explode in such scenarios.