Paper Info
Title
Towards realistic team formation in social networks based on densest subgraphs
Abstract
Given a task T, a set of experts V with multiple skills and a social network G(V, W) reflecting the compatibility among the experts, team formation is the problem of identifying a team C ? V that is both competent in performing the task T and compatible in working together. Existing methods for this problem make too restrictive assumptions and thus cannot model practical scenarios. The goal of this paper is to consider the team formation problem in a realistic setting and present a novel formulation based on densest subgraphs. Our formulation allows modeling of many natural requirements such as (i) inclusion of a designated team leader and/or a group of given experts, (ii) restriction of the size or more generally cost of the team (iii) enforcing locality of the team, e.g., in a geographical sense or social sense, etc. The proposed formulation leads to a generalized version of the classical densest subgraph problem with cardinality constraints (DSP), which is an NP hard problem and has many applications in social network analysis. In this paper, we present a new method for (approximately) solving the generalized DSP (GDSP). Our method, FORTE, is based on solving an equivalent continuous relaxation of GDSP. The solution found by our method has a quality guarantee and always satisfies the constraints of GDSP. Experiments show that the proposed formulation (GDSP) is useful in modeling a broader range of team formation problems and that our method produces more coherent and compact teams of high quality. We also show, with the help of an LP relaxation of GDSP, that our method gives close to optimal solutions to GDSP.
Year
DOI
Venue
2013
10.1145/2488388.2488482
CoRR
Keywords
Field
DocType
team formation problem,compact team,densest subgraphs,team leader,towards realistic team formation,classical densest subgraph problem,novel formulation,social network,team c,np hard problem,team formation,new method,proposed formulation,social networks
Digital signal processing,Mathematical optimization,Locality,Social network,Computer science,Social network analysis,Cardinality,Artificial intelligence,Linear programming relaxation,Machine learning
Conference
Volume
ISBN
Citations 
abs/1505.06661
978-1-4503-2035-1
31
PageRank 
References 
Authors
0.94
15
3
Name
Order
Citations
PageRank
Rangapuram, Syama Sundar1584.45
Thomas Bühler21566.32
Matthias Hein366362.80