Social Connection Aware Team Formation for Participatory Tasks

Performance of a collaborative task is mostly dependent on the collective effort from participants. To accomplish a participatory task effectively and efficiently, the team formation problem (TFP) outweighs all other considerations. It is even more complicated when social connections among candidates is taken into account. As we can imagine, a large number of tasks require members of the team to be socially close. On the contrary, a portion of tasks, e.g., proposal review, pay more attention to a multidimensional view, and team members should be selected from a variety of cliques. Due to the nature of tasks, it is challenging to find a subset that meets the skill requirement of the task as well as socially diversity demand of team members from a pool of candidates. In this paper, we explore the TFP in a social network. Based on different task objectives, we first formulate the TFP as TFP with strong ties (TFP-ST) and TFP with weak ties (TFP-WT), respectively. Both TFP-ST and TFP-WT are proven to be NP-hard, and we then design corresponding heuristic algorithms to solve the two problems. Through extensive simulations, we show that the solution to TFP-ST can achieve significant improvement in terms of collaboration cost, team size, as well as running time, and the solution to TFP-WT can provide better performance than existing approaches at the same time.