Team Formation Optimization Problem Considering Interpersonal Relationship Preference

Platform-intervened and task-oriented team formation in social networks is widely used in online labor markets and crowdsourcing platforms,such as Upwork,and tasks can be divided into cost-sensitive and quality-sensitive types.In addition,user self-organized team formation is also popular in event-based social networks sites,such as Meetup.Traditional studies focus on cooperation in teamwork and use communication cost and other concepts to describe it.However,they neglect social demands and emotion of team members.Inspired by Mayo hunman relations theory,the thesis introduces the feature of interpersonal relationship preference to express the satisfaction of team members.Then we model the characteristics of tasks and activities and study team formation optimization problems in social networks.For the cost-sensitive tasks in platform-intervened mode of team formation,traditional methods tend to select workers with lower expected revenue and wider skills,but ignore their social demands.In order to reduce cost,the thesis proposes that platform could form teams with harmonious interpersonal relationship so that workers maybe be willing to lower their expected salary.Firstly,the above problem is modeled as combinatorial optimization and proved to be NP-Hard.Next a depth-first backtracking algorithm is proposed to accurately search teams with the lowest salary cost.A heuristic algorithm in polynomial time is designed for large-scale scenarios to bulid teams that have low salary cost,where three steps are recursively adopted by pre-selecting workers,reversely choosing subteams and deleting matching skills.Finally,the results of simulation experiments show that both algorithms can reduce salary cost more effectively under different scenarios,compared with Minimal Cost Contribution.For the quality-sensitive tasks in platform-intervened mode of team formation,previous work usually set thresholds to select capable workers,or introduce capability detection mechanisms to eliminate members with poorly performce,without considering influence of interpersonal relationship perference.Firstly,the thesis establishes a prediction model where workers' performance is affected by the relationships in team,based on the study of skills grading,and define team quality combined with the importance of skills.Then,the problem is studied to search for teams with the best quality in terms of number of workers and budget.And a heuristic algorithm is designed to form high-quality teams by searching and matching appropriate workers.Finally,simulation experiments show that the above algorithm provides a higher quality team solution,where workers could perform better compared with two greedy algorithms,within an acceptable running time(seconds).For the user self-organized mode of team formation,previous studies neglect to distinguish the communication patterns in different activities.Firstly,the thesis divides activities into independent and communicative types,and establish two kinds of utility models combining participants' interpersonal relationship preference with their interests in activity topics,then define the total utility of all activities as social welfare.Next,we study the social event organization problem that limit the number of people to maximize social welfare.A heuristic algorithm with hybrid strategy is proposed,which dynamically form teams and adjust teams' scale to fully coordinate the coupling effect between team members.Based on the results of simulation experiments in various scenarios,the algorithm can faster form teams with higher social welfare,compared with Dynamic Greedy algorithm.