摘要
In this article, we propose to study a novel research problem to boost group performance, that is, social-aware diversity-optimized group extraction (SDGE), which takes into consideration the two important factors: 1) group diversity and 2) social tightness. We prove the NP-hardness of SDGE and propose an effective algorithm, named group shrinking for diversity maximization (GSDM) with a performance guarantee, that is, GSDM is a three-approximation algorithm to the SDGE problem studied in this article. We further propose three effective pruning strategies that are able to boost the efficiency of GSDM but do not deteriorate its performance. We conduct extensive experiments on multiple large-scale real datasets to evaluate the performance of GSDM. The experimental results show that our proposed GSDM outperforms the other baseline approaches significantly, in terms of solution quality and efficiency. Moreover, the experimental results also confirm that our proposed pruning strategies indeed boost the efficiency of the algorithm.