Full Report
Full report is available here
Abstract
Team formation is the problem of finding a team of experts that can effectively perform a task that requires a number of skills. Good communication among team members is of great importance and thus the social network of the experts must be taken into account. In this paper, we study the problem of finding a team of experts, in a social network, that also contains negative edges between experts. To the best of our knowledge, existing algorithms for team formation were designed for networks that contain only positive edges. Our goal is to minimize the communication cost function of the team's subgraph. As this problem is NP-Hard, we extend an existing approximation algorithm for team formation that is designed for this problem, to also take into account negative links. We experimented on a real dataset that contains negative edges and showed that effective teams were produced using our extension.
Introduction
To find a team of experts, that can effectively complete a project is not only a matter of them having the skills it takes, but also a matter of communicating well and without any problems with each other. While team formation as a problem has been studied a lot through the years, the social network that connects the experts hasn't been taken into consideration, in the process of finding the team, until a few years back. A group of people isn't only described by the good relationship and sympathy that two people can have for each other, but also by the dislikes and distrust among them. This problem applies in real life. Everyday in many different jobs, projects are assigned to teams of people. If in a certain team, two of the members, that have to work together to complete the project, do not like each other, the project is in danger and it can take ages to be accomplished.
While team formation as a problem has been studied a lot through the years, the social network that connects the experts has not been taken into consideration, in the process of finding the team, until a few years back. The studies of team formation that consider the social network between team members, to the best of our knowledge, have taken place for networks that only contain positive links between people.
In this project, we extend an existing algorithm for team formation, in order to produce results that have as many positive links as possible. The social network is modeled as a graph, with experts as nodes and edges between nodes that have a known way of communication, positive or negative. An edge that connects two nodes, that like and trust each other is a positive link and has a low weight as its communication cost, while an edge that connects two nodes, that dislike and distrust each other is a negative link with a high weight. Our goal is to produce teams, that consist of members that like each other and have no hatred between them. Our implementation accepts a team with an unfriendly link, only in the case that there is no other possible solution with only positive connections for a certain project.
We performed numerous experiments on a real dataset that contains both likes and dislikes between experts and compare the results of our implementation with another existing algorithm. Our algorithm produces teams with less negative links, while it still keeps the communication cost to the lowest possible.
Team formation in the presence of social network, that also contains negative relationships, that hasn't been studied before, along with the better results that have been found by the experiments conducted for this project, are our main contributions.