在签名网络中组建兼容的团队(Social and Information Networks)

  • 2020 年 1 月 16 日
  • 筆記

在社交网络中,团队形成的问题需要一组人,他们不仅具备完成任务所需的技能,而且还能有效地相互沟通。现有的工作假定社会网络中的所有联系都是正的,即它们表示个体之间的友谊或协作。然而,在通常情况下网络是有符号的,也就是说,它包含了正链和负链,对应着与朋友和敌人的关系。在结构平衡概念的基础上,我们提供了一个有符号的网络中用户对兼容性的定义,以及计算它的算法。然后,我们定义了有符号网络中的团队形成问题,在这个问题中,我们要求一个兼容的个人团队,能够以较小的通信成本执行一项任务。结果表明,即使在没有通信成本约束的情况下,该问题也是困难的,并给出了求解该问题的启发式算法。我们用实际数据给出了实验结果,以研究不同兼容性定义的性质和我们的算法的有效性。

原文题目:Forming Compatible Teams in Signed Networks

原文: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.

原文作者:Ioannis Kouvatis, Konstantinos Semertzidis, Maria Zerva, Evaggelia Pitoura, Panayiotis Tsaparas

原文链接:https://arxiv.org/abs/2001.03128