Efficient algorithms for team formation with a leader in social networks

Ming Chin Juang, Chen Che Huang, Jiun-Long Huang*

*Corresponding author for this work

Research output: Contribution to journalArticle

24 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)721-737
Number of pages17
JournalJournal of Supercomputing
Volume66
Issue number2
DOIs
StatePublished - 25 Mar 2013

Keywords

  • Social intelligence
  • Social network
  • Team formation

Fingerprint Dive into the research topics of 'Efficient algorithms for team formation with a leader in social networks'. Together they form a unique fingerprint.

  • Cite this