LDDC: Balancing Speed and Accuracy in Social Influence Maximization

TL;DR

The Linear-Decrescence Degree Centrality (LDDC) algorithm is a novel approach to the Influence Maximization (IM) problem. It uses the sociological "Three Degrees of Influence Rule" to identify TOP-K influential nodes in a network. By considering only three hops of neighbors and applying a linear decay factor, it matches the accuracy of expensive global algorithms (like Closeness Centrality) while remaining as scalable as simple degree-based methods.

Problem & Motivation: The Efficiency-Accuracy Paradox

In the era of massive social networks, identifying influential nodes is critical for viral marketing and rumor control. However, researchers have long faced a choice between:

• Local Heuristics (Degree Centrality): Very fast, but ignores the network structure, leading to poor accuracy.
• Global Centrality (Closeness/Betweenness): Excellent at identifying key bridges and hubs, but the computational cost is $O(n^3)$ or $O(nm)$, making them unusable for networks with millions of nodes.
• Greedy Algorithms: High accuracy but NP-hard complexity, requiring massive simulation time.

The authors' insight is grounded in human behavior: our influence isn't infinite. If you influence a friend, they might influence their friend, but by the fourth or fifth person down the line, your original impact is virtually zero.

Methodology: The Three Degrees of Influence

The LDDC algorithm formalizes the Three Degrees of Influence Rule—the idea that behavior and attitudes spread primarily through three degrees of separation.

The Core Formula

The influence of a node $n$ is calculated as: $LDDC(n)=|F(n)|+\alpha (|S(n)|+\beta |T(n)|)$ Where:

• $F(n)$: 1st-degree neighbors (direct friends).
• $S(n)$: 2nd-degree neighbors (friends of friends).
• $T(n)$: 3rd-degree neighbors.
• $\alpha ,\beta$: Decrescence coefficients ($0.7$ and $0.4$ respectively) that model how influence weakens as it travels further from the source.

Fig 1. Example of a social network graph where LDDC processes neighbor sets up to three degrees to calculate a node's potential impact.

Experiments & Results

The authors validated LDDC using the SIR (Susceptible-Infected-Recovered) model to simulate real-world spreading across three datasets: Dolphin (62 nodes), Email (1,133 nodes), and Blog (3,982 nodes).

1. Position Offset Method

By comparing the predicted influence rank to the "true" SIR simulation rank, the study found that LDDC consistently outperformed DC, BC, and LC. In many cases, it was identical or superior to Closeness Centrality (CC), which is much more complex to calculate.

2. High Correlation

The correlation scatterplots show a strong positive relationship between LDDC scores and the actual number of nodes "infected" in the simulation, particularly in the Blog dataset.

Fig 2. The line graph of position offset in the Blog dataset, showing LDDC tracks the "Ground Truth" much more closely than Degree or Betweenness Centrality.

Critical Analysis & Conclusion

Takeaway

The LDDC algorithm suggests that we don't need to compute the "shortest path to every other node" to find influencers. By focusing on a localized 3-hop horizon and applying a linear decay, we capture the vast majority of a node's spreading potential.

Limitations

• Static Networks: The paper focuses on non-directional, static graphs. In the real world, social edges are directed and time-evolving.
• Parameter Sensitivity: While $\alpha =0.7$ and $\beta =0.4$ worked best in these tests, these values might need tuning for different types of social platforms (e.g., Twitter vs. LinkedIn).

Future Work

The next step for this technology lies in dynamic scalability—applying these decaying influence rules to real-time data streams to stop rumors the moment they start spreading.