Given a task $\mathcal{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 \subseteq V$ that is both competent in performing the task $\mathcal{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.
翻译:鉴于一个任务$mathcal{T}美元,一组具有多种技能和社交网络$(V,W)美元,反映了专家之间的兼容性,团队组建的问题是,要确定一个既有能力执行任务,又能够合作的团队$C subseteq V$(Mathcal{T}美元),这一问题的现有方法的假设限制性过强,因此无法模拟实际情景。本文件的目的是在现实的环境下考虑团队组建问题,并以最密集的子谱为基础,提出一种新颖的提法。我们的提法允许对许多自然要求进行建模,例如(一)纳入指定的团队领导和(或)一个特定专家小组;(二)限制团队的规模或更一般的成本(三)在地理或社会意义上执行团队的地理位置上实施。 拟议的提法导致一个典型的精密子绘图问题(DSP)的概括化版本,这是一个NP硬的问题,在社会网络分析中有许多应用。在本文中,我们提出了一种更精确的、更精确的版本方法,我们提出了一种我们GSSP的构建方法。