[Academic Tech Insight] Breaking the Scalability Barrier: A Locally Greedy Approach to MPIDS

TL;DR

Finding the minimum set of "influencers" who can reach at least half the neighbors of every individual in a massive social network is a classic APX-hard problem (MPIDS). While global greedy strategies are the standard, they crawl when networks scale into the millions. This paper proposes a Locally Greedy Algorithm that restricts its search space to the neighbors of unsatisfied nodes and processes nodes from low-to-high degrees. The result? A massive speedup (often 100x+) and equal or better solution quality.

The Core Motivation: Why Global Greed Fails

In the context of social networks, the Minimum Positive Influence Dominating Set (MPIDS) is more than a theoretical exercise. It’s a tool for curbing the spread of misinformation or "negative emotions." If you can influence a set of people such that every user has at least 50% of their friends in that set, you effectively control the network's consensus.

The problem is that existing algorithms like those by Wang et al. or Raei et al. are globally greedy. In every iteration, they scan every potential node in the graph to find the one that contributes the most "coverage." For a network with $N$ nodes, this leads to $O(N^2)$ or even $O(N^3)$ complexity. In the era of billion-user platforms, $O(N^2)$ is essentially "mission impossible."

Methodology: The Power of Locality

The authors' "Locally Greedy" (Algorithm 1) shifts the paradigm by introducing two key inductive biases:

1. Local Neighborhood Search: When a node $v$ is "unsatisfied" (meaning less than half its neighbors are in the dominating set), the algorithm doesn't look at the whole graph. It only looks at the neighbors of $v$ to find the best candidate to add.
2. Smallest-Degree First: It processes nodes in ascending order of their degrees. The intuition here is that low-degree nodes are "pickier"—they have fewer neighbors to choose from. By satisfying them first, the algorithm naturally builds a foundation that high-degree nodes (who are easier to satisfy) can benefit from later.

Note: The algorithm maintains two counters: $\Delta A(v)$ (how many more neighbors $v$ needs) and $unsat(v)$ (how many neighbors of $v$ are currently unsatisfied).

Performance: Small Scale to Big Impact

The efficiency gain is most visible when we look at the complexity: $O(n\log n+m)$, where $m$ is the number of edges. This is nearly linear for sparse social networks.

Quantifying the Speedup

In the Email-Enron dataset (~36k nodes), the classic Raei algorithm takes 7.386 seconds, whereas the Locally Greedy approach finishes in 0.065 seconds. That's a 113x speedup.

Quality Check

Crucially, moving to a local strategy didn't hurt the results. In fact, for the CA-CondMat network, the algorithm found a PIDS of size 9,801, whereas previous SOTA (Mai et al.) was stuck at 9,847.

Table showing that Locally Greedy (last column) consistently achieves the lowest or near-lowest PIDS size and the lowest execution time.

Deep Insight: Why Smaller Degrees First?

The "Smallest-Degree First" strategy is a clever exploitation of the Power-Law nature of social networks. High-degree nodes (hubs) are likely to be neighbors with many low-degree nodes. By satisfying the "leaf" nodes first, the hubs are essentially satisfied as a "by-product." If you did the opposite, you would likely pick hubs early on, but still be forced to pick many inefficient leaf neighbors later to satisfy the fringes of the graph.

Critical Analysis & Future Outlook

While the algorithm is incredibly fast and effective for static graphs, social networks are dynamic. A potential limitation of this work is its reliance on a static undirected (or simple directed) topology.

Future Prospects:

• Dynamic Adaptation: Can this local greedy approach be updated incrementally as new edges form?
• Directed Graphs: The authors touched on directed graphs (e.g., Slashdot, Google+), but the interaction between "influence" and "following" in directed settings offers much richer ground for local optimization.

In conclusion, this paper proves that for huge NP-hard graph problems, the local view is often the most efficient view.