Research And Implementation Of The Grouped Team Formation Problem In Social Networks

Given a set of experts with different skills,an expert collaboration social network and a task,the aim of the team formation problem in social networks is to form a team to complete the task.The team must satisfy the skill requirements of the task and collaborates efficiently.Only the efficient collaboration can represent the true value of a team.With the history collaboration information provided by the expert collaboration social networks,we can use automatic team formation methods in team management to get a team with efficient collaboration,so that we can improve management efficiency and productivity.Different communication cost functions have been proposed to have a good measure on the collaboration strength of a team in previous work.However,the grouped organization structure inside team is never considered,which is very common in real life scenarios.In this thesis,in consideration of the deficiencies of the previous work,a novel communication cost function for a grouped team is proposed,called Grouped Leader Distance.With this function as the objective function,the Grouped Team Formation problem is defined.In a grouped team,there is a team leader who manages multiple group leaders,and each group leader manages multiple group members.Some constraints are added in the problem definition to make it match real application scenario better.The expert assignment constraint requires that an expert can be assigned to at most one group.The group cardinality and skill cover constraint require that each group must get a certain number of group members with corresponding skills.To solve the Grouped Team Formation problem,an exact algorithm is proposed,called AP(Assignment and Pruning).Given the group leaders,assigning optimal group members can be regarded as a subproblem.It can be solved by being constructed as a classical assignment problem.The AP algorithm is based on a pruning framework.By efficiently filtering out the combinations of group leaders and assigning optimal group members as the solution of the subproblem does,the AP algorithm can get the final optimal solution.The price of obtaining the exact solution is that the AP algorithm does not work efficiently on large scale datasets.Hence,in consideration of two bottlenecks of the AP algorithm,by designing reasonable greedy rules,two heuristic algorithms with higher efficiency are proposed.Aiming at the solution of the subproblem,the Greedy AP(Greedy Assignment and Pruning)algorithm proposes two greedy strategies,the minimum value first and the least substitutes first,to select group members.Combining with the pruning framework,the Greedy AP algorithm gets the final result.The minimum value first strategy is rather intuitive,while the least substitutes first strategy is better at obtaining feasible solution.Aiming at the pruning framework,the AGG(Assignment and Greedy Group-leaders)algorithm selects group leaders by minimum value first strategy,then transforms into an assignment problem to get the assignment of group members.The Greedy AP algorithm gets better grouped team,while the AGG algorithm has better scalability.The three algorithms have own advantages and suitable scenarios respectively.In this thesis,the effectiveness and time efficiency of the proposed algorithms are evaluated by extensive experiments on both synthetic and real world datasets.The results of the experiments show that the AP algorithm proposed in this thesis has efficient pruning effects,and its time efficiency is far better than the exhaustive method.The two heuristic algorithms improve a lot on time efficiency compared with the exact algorithm.On this basis,they perform very well on effectiveness under different measures of communication cost functions.Meanwhile,the definition of the Grouped Team Formation problem is proved to be reasonable in practical scenario.