Local Search for Diversified Top-k s-plex Search Problem (Student Abstract)

Jun Wu, Minghao YinAAAI 2021 · DOI

Abstract

Identifying influential communities in massive networks is a critical task in data mining. While cliques represent perfectly connected groups, they are often too rigid for real-world datasets. The $s$-plex model offers a more flexible alternative, allowing for missing links. This paper introduces the Diversified Top-$k$ $s$-plex (DTKSP) search problem, which aims to find $k$ maximal $s$-plexes that maximize vertex coverage and diversity. We prove that DTKSP is NP-hard and propose TOPKSPLEX, a local search algorithm. Evaluations on 139 massive real-world graphs show that TOPKSPLEX consistently outperforms industrial-grade MILP solvers in both solution quality and efficiency.

Introduction

In network analysis, finding cohesive subgroups is essential for understanding social dynamics, biological interactions, and citation patterns. Traditionally, cliques—subgraphs where every vertex is connected to every other vertex—have been used to define these communities. However, real-world data is frequently incomplete or noisy, making the strict clique requirement impractical.

The $s$-plex model relaxes this constraint: in an $s$-plex, each vertex is non-adjacent to at most $s$ other vertices within the group. While finding a single large $s$-plex is useful, many applications require a set of $k$ distinct groups. Simply selecting the $k$ largest $s$-plexes often results in highly overlapping sets that represent the same underlying community. To address this, we define the Diversified Top-$k$ $s$-plex (DTKSP) problem, which seeks to maximize the total number of unique vertices covered by $k$ maximal $s$-plexes while minimizing redundancy.

Methodology

The DTKSP problem is formulated as a Mixed Integer Linear Program (MILP) with a dual objective: maximizing the union of vertices in the selected $s$-plexes and ensuring diversity. We demonstrate that this problem is NP-hard by reduction from the maximum $k$-cover problem.

To solve DTKSP efficiently on large-scale networks, we developed TOPKSPLEX, a local search heuristic. The algorithm employs a "swap" strategy:

  1. Candidate Generation: It constructs new maximal $s$-plexes, prioritizing vertices that are currently underrepresented in the solution set.
  2. Diversity Evaluation: It calculates a score for each $s$-plex based on its "private vertices"—those that belong exclusively to that $s$-plex.
  3. Refinement: If a new candidate $s$-plex provides better coverage than the current "worst" $s$-plex (the one with the fewest private vertices), the swap is performed.

Experimental Results

We evaluated TOPKSPLEX using 139 massive real-world graphs from the Rossi and Ahmed repository, spanning social, biological, and citation networks. By varying the parameters $k$ and $s$, we generated 2,224 distinct test instances. We compared our algorithm against the industrial-grade MILP solver, CPLEX 12.9.

TOPKSPLEX demonstrated significant advantages:

  • Robustness: CPLEX failed to provide solutions for 204 instances within a one-hour time limit, whereas TOPKSPLEX solved all 2,224 instances.
  • Quality: On the instances where CPLEX succeeded, TOPKSPLEX found better or equal solutions in 98.6% of cases (1,993 out of 2,020).
  • Speed: TOPKSPLEX achieved these results with a 360-second cutoff, an order of magnitude faster than the time allotted to CPLEX.
Comparison of TOPKSPLEX and CPLEX performance across 139 massive graphs for varying s values.

The table above highlights the performance gap, showing that TOPKSPLEX consistently finds better solutions across different "looseness" parameters ($s$) and handles all instances where the industrial solver failed.

Conclusion

The TOPKSPLEX algorithm provides a powerful tool for discovering diverse and influential communities in massive networks. By focusing on private vertices and employing an efficient local search, it overcomes the scalability limitations of exact MILP solvers. Future work will involve exploring the theoretical approximation bounds of the heuristic and investigating the impact of initial construction phases on final solution quality.

Summary updated

BibTeX
@inproceedings{wu2021local,
  author = {Jun Wu and Minghao Yin},
  title = {{Local Search for Diversified Top-k s-plex Search Problem (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i18.17961},
}
Figure