Introduction
In the field of Influence Maximization (IM), the objective is to identify a small set of "seed" nodes that trigger the largest possible information cascade across a social network. Traditional centrality measures often focus on "core" nodes—those with the highest global connectivity. However, real-world networks typically exhibit strong community structures where these core nodes tend to cluster together. This leads to the "rich club effect," where the influence of selected seeds overlaps significantly, trapping information within a few sub-groups.
To address this, the authors propose CKS (Community-Based K-shell), a novel centrality measure designed to identify "bridge nodes." These nodes sit at the intersections of multiple communities, acting as gateways that facilitate global spread rather than localized saturation.
Methodology: The CKS-Score
The CKS approach utilizes a three-step pipeline to rank node influence by combining localized structure with global diversity:
- Community K-Shell (CKS): The network is first partitioned into communities using the Louvain algorithm. These communities are then isolated by temporarily removing inter-community edges. Within each isolated group, a local K-shell decomposition is performed, assigning nodes a score based on their position relative to the community's local core.
- K-Shell Entropy (KSE): To ensure a seed node can effectively distribute information across all layers of a community, the authors introduce an entropy-based metric. KSE measures the diversity of a node's connections across different local shells, prioritizing nodes that connect to both the core and the periphery.
- CKS-Score Calculation: The final score is a weighted sum of a node's KSE and connectivity across all adjacent communities. This formula naturally prioritizes bridge nodes that connect to large, significant communities.
Experimental Evaluation
The researchers evaluated CKS on four diverse, real-world networks: Twitch (gamers), soc-Hamsterster (social), p2p-Gnutella04 (file-sharing), and email-univ (communication). CKS was compared against four state-of-the-art baselines: Betweenness Centrality (BC), Closeness Centrality (CC), Neighborhood Coreness (ENC), and Local Structure/Closeness (GLR).
Key Results
- Superior Infection Scale: Simulations using the Independent Cascade (IC) model showed that CKS consistently achieved a larger "Final Infected Scale" (FIS) than all baselines across all datasets, regardless of the spreader fraction or activation probability.
- Spatial Diversity of Seeds: CKS achieved a higher "Average Shortest Path Length" (ASPL) between seed nodes. This confirms that the algorithm successfully selects seeds that are geographically spread out across the network, minimizing redundant influence.
- Computational Efficiency: CKS proved significantly faster than global measures like BC and CC. For instance, on the p2p-Gnutella04 dataset, CKS completed in approximately 83 seconds, whereas BC required over 1200 seconds.
Discussion and Insights
The central insight of this work is that a node's value is defined not just by its total degree, but by its role as a gateway. By isolating communities before performing K-shell decomposition, CKS uncovers influential bridge nodes that are often overshadowed by global structures in standard analyses. Furthermore, the use of entropy ensures that once a community is reached, the information is well-distributed across its internal layers, preventing the cascade from stalling in the periphery.
Limitations and Future Work
As a student abstract, this study opens several avenues for future research. The current model assumes a static network, whereas real-world social structures are dynamic and evolve over time. Additionally, the sensitivity of CKS to different community detection algorithms (e.g., Infomap or Leiden) remains to be explored. Finally, testing the scalability of CKS on massive graphs with millions of nodes will be crucial for industrial applications.
Summary updated