CKS: A Community-Based K-shell Decomposition Approach Using Community Bridge Nodes for Influence Maximization (Student Abstract)

Inder Khatri, Aaryan Gupta, Arjun Choudhry, Aryan Tyagi, Dinesh Kumar Vishwakarma, Mukesh PrasadAAAI 2023 · DOI

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:

  1. 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.
  2. 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.
  3. 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.
Figure 1: Comparison of Average Shortest Path Length (ASPL) between seed nodes. CKS (blue) maintains higher spatial diversity among seeds, indicating its effectiveness in picking bridge nodes.
  • 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.
Figure 2: Comprehensive performance comparison of CKS against baselines across four datasets. The grid displays Final Infected Scale (FIS) and Average Shortest Path Length (ASPL) results, demonstrating CKS's consistent dominance.

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

BibTeX
@inproceedings{khatri2023cks,
  author = {Inder Khatri and Aaryan Gupta and Arjun Choudhry and Aryan Tyagi and Dinesh Kumar Vishwakarma and Mukesh Prasad},
  title = {{CKS: A Community-Based K-shell Decomposition Approach Using Community Bridge Nodes for Influence Maximization (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i13.26980},
}
Figure