Abstract
Studies in Management and Sociology indicate that the diversity of job-related attributes of group members (group diversity) is crucial for boosting the group performance, because the diversity brings different knowledge and enables more innovative ideas and solutions. In addition, the social tightness of the group members is also important for effective communication, which is also an important factor for group performance. In this paper, we propose a new research problem, named Social-aware Diversity-optimized Group Extraction (SDGE), which considers the above two important factors jointly to extract a socially tight group with optimized group diversity from the social network. We formally formulate the SDGE problem and propose algorithm Group Shrinking for Diversity Maximization (GSDM), which is a 3-approximation algorithm for SDGE. We prove the performance guarantee of GSDM and conduct extensive experiments on real datasets to evaluate the performance of GSDM. The results indicate that GSDM outperforms the other baselines in both solution quality and efficiency.