论文标题
在签名网络中组建兼容团队
Forming Compatible Teams in Signed Networks
论文作者
论文摘要
社交网络中团队形成的问题要求一组个人，他们不仅具备执行任务所需的技能，而且还可以彼此有效沟通。现有工作假设社交网络中的所有链接都是积极的，也就是说，它们表明个人之间的友谊或协作。但是，通常是签署网络的情况，也就是说，它包含与朋友和敌人关系相对应的正面和负面链接。在结构平衡的概念上，我们提供了签名网络中用户对之间兼容性的定义，以及用于计算它的算法。然后，我们在签名的网络中定义了团队组成问题，在那里我们要求一个兼容的个人团队，可以执行以较小的沟通成本执行任务。我们表明，即使没有沟通成本限制，问题也是NP-HARD，并且我们提供了解决该问题的启发式算法。我们通过实际数据提出了实验结果，以研究不同兼容性定义的性能以及算法的有效性。
The problem of team formation in a social network asks for a set of individuals who not only have the required skills to perform a task but who can also communicate effectively with each other. Existing work assumes that all links in a social network are positive, that is, they indicate friendship or collaboration between individuals. However, it is often the case that the network is signed, that is, it contains both positive and negative links, corresponding to friend and foe relationships. Building on the concept of structural balance, we provide definitions of compatibility between pairs of users in a signed network, and algorithms for computing it. We then define the team formation problem in signed networks, where we ask for a compatible team of individuals that can perform a task with small communication cost. We show that the problem is NP-hard even when there are no communication cost constraints, and we provide heuristic algorithms for solving it. We present experimental results with real data to investigate the properties of the different compatibility definitions, and the effectiveness of our algorithms.
