Methods For Team Formation With Strong Ties And Weak Ties In Social Networks

To finish complex projects, we need to form a team to collaborate in daily life. The researches on social networks show that the relationships among team members have a significant influence on the productivity of the team and the success of the project. Thus, when forming a team, we should take both the skills of members and their social relationships into consideration. Currently, Team Formation Problem has become a hot topic in both academia and industry.When forming a team to implement a project, we want that the team members are close to each other, which means that it's a team with strong ties. It can reduce the cost of communication and collaboration among the team members and promote the completion of projects. When forming a team to review a project, the team with weak ties would be better. The unfamiliarity among team members can avoid the following blindly action and ensure the objectiveness of the comments.In this thesis, we focus on the research about team formation in a social network. The research is conducted on two aspects:team with strong ties and team with weak ties. The main contents are:Method for team formation with strong ties under the success rate constraints:The difference of success rate among people is ignored by current researches, which may cause the failure of a project. This paper is the first one to take success rate as a constraint. The purpose is to form a team with strongest ties and the success rate requirement of every task should be reached. By modelling the problem to a combinatorial optimization problem and proving it's a NP-hard problem, we design an algorithm based on the minimum Steiner tree problem. The time complexity of our algorithm is 0(n3).Method for team formation with weak ties:The model for measuring the weak ties in teams is complicated in current research. In this thesis, a new model is proposed. The level of weak ties is measured by the minimum collaboration cost among team members. After modelling the problem to an optimization problem and proving it's a NP-hard problem, we design a heuristic algorithm. The time complexity of the algorithm is 0(|C(trarest)|·n2).To verify the efficiency of algorithms proposed in this thesis, sufficient experiments based on the social network structure mined from real data have been conducted. By comparing the results of team collaboration cost, minimum collaboration cost, team size and running time with the algorithms based on greedy rule, we prove that the algorithms proposed in this thesis are efficient.