Discovering top-k teams of experts with/without a leader in social networks
Authors:
Open Access
- 24 October 2011
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 985-994
Abstract
We study the problem of discovering a team of experts from a social network. Given a project whose completion requires a set of skills, our goal is to find a set of experts that together have all of the required skills and also have the minimal communication cost among them. We propose two communication cost functions designed for two types of communication structures. We show that the problem of finding the team of experts that minimizes one of the proposed cost functions is NP-hard. Thus, an approximation algorithm with an approximation ratio of two is designed. We introduce the problem of finding a team of experts with a leader. The leader is responsible for monitoring and coordinating the project, and thus a different communication cost function is used in this problem. To solve this problem, an exact polynomial algorithm is proposed. We show that the total number of teams may be exponential with respect to the number of required skills. Thus, two procedures that produce top-k teams of experts with or without a leader in polynomial delay are proposed. Extensive experiments on real datasets demonstrate the effectiveness and scalability of the proposed methods.Keywords
This publication has 11 references indexed in Scilit:
- Keyword search in graphsProceedings of the VLDB Endowment, 2011
- Power in unity2010
- A team formation model based on knowledge and collaborationExpert Systems with Applications, 2009
- Finding a team of experts in social networks2009
- Querying Communities in Relational DatabasesInternational Conference on Data Engineering, 2009
- Keyword proximity search in complex data graphs2008
- Network Formation2008
- PROJECT TEAM SELECTION USING FUZZY OPTIMIZATION APPROACHCybernetics and Systems, 2007
- Group formation in large social networks2006
- Forming effective worker teams with multi-functional skill requirementsComputers & Industrial Engineering, 2005