Finding Social Teams

Crowd-Sourcing, the idea of harnessing the expertise of millions of users to solve complex tasks, has gained considerable attention in recent years. One of the active areas of research here is on finding how to form the best team for a collaborative task. In this paper, we define the team formation problem in presence of user capacities. We highlight that along with the social connections among the team members, it is also a key issue to consider the capacities of individuals, in order to form effective teams. We model the effectiveness of a team using different metrics based on communication cost. Specifically, given the social network, the individual skill-sets and capacities and a task, we want to select a team with least communication cost whose skill-set meets the task requirement and no user is expected to work beyond her capacity. We prove that our problem is NP-Hard and present two practical and efficient approximation algorithms Diam-TF and Steiner-TF for our problem. We also present a heuristic for the Steiner-TF problem which is slightly more accurate albeit a small increase in the running time. Finally, we validate the efficacy and trade-offs of our algorithms through detailed experiments performed over real-world collaboration data collected from online open source project development sites.