RNR: Bridging the Gap Between Greedy Accuracy and Heuristic Speed in Influence Maximization

TL;DR

The problem of Influence Maximization (IM)—finding a small set of "seed" nodes to trigger the largest possible cascade in a network—has long been a battleground between slow, accurate Greedy algorithms and fast, imprecise heuristics. RNR (Reversed Node Ranking) breaks this dichotomy by using iterative global ranking to achieve high-resolution node selection that rivals Greedy performance at a fraction of the cost.

The Resolution Crisis in Social Networks

Most efficient IM algorithms rely on local scores like Degree Centrality. However, local metrics suffer from a "resolution crisis": in large networks, thousands of nodes might share the same degree, yet their actual influence power varies wildly based on their position in the global topology.

Previous heuristics also struggled with the Rich-Club Effect, where top spreaders are often clustered together. If you pick five celebrities who are all friends with each other as your seeds, their influence overlaps significantly, wasting your budget.

Methodology: The Logic of Reversed Ranking

The core Innovation of RNR lies in its iterative scoring formula and its use of Reversed Ranks rather than raw values.

1. Why Reversed Rank?

Instead of using a raw score (like degree), RNR assigns each node a weight based on its position in a sorted list. If there are $N$ nodes, the top-ranked node gets a weight of $N$, the second gets $N-1$, and so on. This ensures:

• Unique Weights: Every node has a distinct influence potential.
• Global Context: The rank reflects a node's standing relative to the entire network.

2. The Iterative Equation

The RNR value of a node $v$ is calculated as: $RNR(v)=reversed\_rank(v)+{\sum }_{u\in neigh(v)}reversed\_rank(u)imesp(v,u)$ This formula captures the classic intuition: a node is influential if it has a high rank or if it is connected to other high-ranking nodes. The algorithm iterates until the rankings stabilize, ensuring local connectivity and global position are balanced.

Table 1: Comparison showing RNR's high-resolution ranking vs. traditional metrics.

Two Models, Two Strategies

The authors make a crucial observation: The Independent Cascade (IC) model and the Weighted Cascade (WC) model react differently to overlapping influence.

• RNR-ND (Neighbor Delete): When a seed is picked, its neighbors are removed. This "brute force" avoidance of the rich-club effect is perfect for the IC model, where the constant spreading probability makes neighbor overlaps highly redundant.
• RNR-NW (Neighbor Weaken): Instead of deleting neighbors, it reduces their contribution mathematically. This "soft" approach is better for the WC model, where influence is naturally dampened by node degree, making the rich-club effect less damaging.

Experimental Showdown

The researchers tested RNR against standards like PageRank, DegreeDiscount, and CELF (Greedy) on networks ranging from 1,500 to 146,000 nodes.

Figure: RNR-ND (Purple) matches or exceeds the Greedy benchmark (Cyan) in influence spread under the IC model.

Key Results:

1. Superior Accuracy: Under the IC model, RNR-ND consistently outperformed PageRank and DegreeDiscount, and even beat the Greedy algorithm on three out of five datasets.
2. Scalability: While Greedy reached its computational limit on the WordNet dataset (146k nodes), RNR processed it efficiently.
3. Spreading Speed: Beyond the final reach, RNR seeds activated nodes faster in the early time steps, a critical factor for time-sensitive viral marketing.

Critical Insight: The "Why" Behind the Success

Why does RNR work so well? It’s because it treats IM as a dynamic re-ranking problem rather than a static scoring problem. By combining global ranking (via reversed ranks) with adaptive local optimization (ND or NW strategies), it mimics the look-ahead capability of Monte Carlo simulations without the actual simulation cost.

Conclusion and Future Outlook

The RNR algorithm proves that we don't need to choose between speed and accuracy. By respecting the unique features of the spreading model (IC vs WC) and using high-resolution ranking, we can find optimal spreaders in massive social networks in real-time.

Future work is expected to focus on optimizing the $O(N\log N)$ sorting bottleneck, potentially opening the door to influence maximization in billion-scale graphs.