LDDC: Balancing Accuracy and Speed in Social Influence Maximization

Executive Summary

In the era of viral marketing and rapid rumor propagation, identifying the "most influential" nodes in a social network is a critical task. This paper presents the Linear-Decrescence Degree Centrality (LDDC) algorithm, a novel heuristic that bridges the gap between simple degree-based methods and complex global path calculations. By applying a sociological lens—the Three Degrees of Influence Rule—the authors provide an elegant solution that is both computationally light and remarkably accurate.

The Problem: The Complexity-Accuracy Paradox

Influence Maximization (IM) is fundamentally NP-hard. When researchers try to solve it, they usually hit a wall:

• Heuristic Algorithms: Degree Centrality is fast ($O(1)$ per node) but "blind" to the network structure beyond immediate neighbors.
• Global Metrics: Closeness and Betweenness Centrality look at the whole graph ($O(N^2)$ or $O(NE)$), providing high accuracy but failing to scale to millions of users.
• Greedy Approaches: These provide high precision but require repeated Monte Carlo simulations, making them too slow for dynamic environments.

Methodology: The "Three Degrees" Insight

The core philosophy of LDDC is derived from research by Christakis and Fowler, who suggested that human influence typically ripples out to three degrees (friends of friends' friends) before dissipating.

The LDDC algorithm formalizes this into an influence score: $LDDC(n)=|F(n)|+\alpha (|S(n)|+\beta |T(n)|)$ Where:

• $F(n)$: Immediate neighbors (1st degree).
• $S(n)$: Second-degree neighbors.
• $T(n)$: Third-degree neighbors.
• $\alpha ,\beta$: Decay coefficients (optimized at 0.7 and 0.4 respectively).

By focusing only on three-hop neighborhoods, the algorithm avoids global graph traversals while capturing the "local cluster" influence that simple degree centrality misses.

Figure 1: Comparison of influence degrees in local centrality models.

Experiments and Results

The authors validated LDDC using the SIR (Susceptible-Infected-Recovered) model across three distinct datasets: Dolphin (small), Email (medium), and Blog (large).

1. Position Offset Analysis

To measure accuracy, the authors calculated the "Position Offset"—the difference between an algorithm's predicted rank and the true influence rank (simulated via SIR).

• Dolphin Dataset: LDDC achieved a TOP-10 offset of 14, while Degree Centrality lagged at 70.
• Performance: LDDC's accuracy consistently matched or exceeded Closeness Centrality (CC), which is far more computationally expensive.

Figure 2: Position offset trends in the Email dataset. Lower values indicate higher accuracy.

2. Scalability and Correlation

The scatterplots (e.g., for the Blog dataset) show a strong positive correlation between the LDDC score and the actual number of nodes "infected" in the SIR model. This confirms that the decaying weights ($\alpha$ and $\beta$) accurately reflect how influence weakens over distance.

Critical Analysis & Conclusion

Takeaway

LDDC proves that you don't need to know the entire structure of the internet to find an influencer; knowing who they can reach in three hops, with a penalty for distance, is a highly effective heuristic.

Limitations

• Parameter Sensitivity: The coefficients $\alpha =0.7$ and $\beta =0.4$ were determined empirically. These might vary in networks with different densities (e.g., highly dense professional networks vs. sparse interest-based blogs).
• Static Nature: The model assumes a static graph. Real-world social influence often changes as edges appear and disappear.

Future Work

The path forward involves adapting LDDC for directed graphs and weighted edges, where the "decay" might be influenced by the strength of the relationship (e.g., close family vs. casual followers) rather than just a linear constant.