Efficient algorithms for team formation with a leader in social networks

摘要

Given a project with a set of required skills, it is an important and challenging problem of find a team of experts that have not only the required skill set but also the minimal communication cost. Furthermore, in view of the benefits of greater leaders, prior work presented the team formation problem with a leader where the leader is responsible for coordinating and managing the project. To find the best leader and the corresponding team, the prior work exhaustively evaluates each candidate and the associated team, incurring substantial computational cost. In this paper, we propose two efficient algorithms, namely the BCPruning algorithm and the SSPruning algorithm, to accelerate the discovery of the best leader and the corresponding team by reducing the search space of team formation for candidates. The BCPruning algorithm aims at selecting better initial leader candidates to obtain lower communication cost, enabling effective candidate pruning. On the other hand, the SSPruning algorithm allows each leader candidate to have a lower bound on the communication cost, leading some candidates to be safely pruned without any computation. Besides, the SSPruning algorithm exploits the exchanged information among experts to aid initial candidate selection as well as team member search. For performance evaluation, we conduct experiments using a real dataset. The experimental results show that the proposed BCPruning and SSPruning algorithms are respectively 1.42-1.68 and 2.64-3.25 times faster than the prior work. Moreover, the results indicate that the proposed algorithms are more scalable than the prior work.