LDM: Elevating Node Influence Ranking via Level Propagation and Gain Functions

TL;DR

The Level and Degree Model (LDM) is a novel framework for identifying influential nodes in social networks by focusing on the "quality" of a node's neighborhood. By combining an iterative influence level update with a power-law-based gain function, LDM provides a high-accuracy, efficient alternative to traditional metrics like PageRank and K-shell decomposition.

Background & Motivation: Moving Beyond Simple Centrality

Identifying influential nodes is critical for viral marketing, rumor control, and understanding network robustness. However, existing methods often hit a wall:

• Degree Centrality is too local; it ignores whether your neighbors are themselves influential.
• PageRank is computationally intensive due to its global iterative nature.
• K-shell Decomposition is too coarse, often assigning the same influence value to thousands of nodes.

The authors of this paper argue that a node's influence should be determined not just by how many neighbors it has, but by the Influence Level of those neighbors and how they "push" the node to a higher status.

Methodology: The Level and Degree Model (LDM)

The core of LDM rests on the concept of an Influence Label ($I_i$), comprised of an influence level ($l_i$) and a node degree ($d_i$).

1. High-Quality (Hi-Q) Neighbors

LDM defines a Hi-Q neighbor as one whose influence level is greater than or equal to the current node's level. The intuition is simple: if you are surrounded by people more influential than you, your own status is likely to rise.

2. Iterative Label Update

A node's level is upgraded if the number of its Hi-Q neighbors exceeds its current level. This creates a "climbing" effect where node levels stabilize as they reach their true structural significance.

Fig 1: Demonstration of how node levels interact within the structural network.

3. The Power-Law Gain Function

To fix the K-shell problem (where many nodes end up with the same level), the authors introduce a Gain Function ($\delta$): $\delta =\alpha \cdot {\log }_{10}(1+\lambda )$ This factor accounts for "non-prime" neighbors (those with lower levels) who still contribute to a node's reach, ensuring that the ranking remains granular and follows realistic power-law distributions found in social media.

Experiments and Results

The authors validated LDM using the Independent Cascade (IC) model across four diverse datasets: Blogs, Facebook, P2P, and Email.

Performance Gains

Using Kendall’s tau ($au$) to measure the correlation between the predicted ranking and the actual spreading ability in simulations, LDM (specifically LD_2 with the gain function) proved superior:

• Blogs/Facebook: High accuracy due to clear power-law degree distributions.
• Email: Lower correlation generally for all models due to network homogeneity, yet LDM remained competitive.

Fig 2: Kendall’s tau values across different methods. Note that LD_2 (LDM with Gain) consistently outperforms LD_1 (Base LDM) and PageRank.

Table: Optimal Hyperparameters

Critical Insight & Conclusion

The LDM approach succeeds because it mimics the "Six Degrees of Separation" and social hierarchies effectively. Its complexity is $O(kn)$, which is efficient for large-scale sparse networks.

Takeaway: The key to ranking influence isn't just about who you know, but the relative "level" of your connections compared to your own. By refining the K-shell concept with a dynamic gain function, LDM provides the granularity needed for real-world viral marketing applications.

Future Work: The authors suggest moving toward Dynamic Networks, where influence is not a static property but one that evolves as the graph structure changes over time.