Research Of Team Formation With Weak Ties In Social Networks

In recent years,with the rise of online social networking platform,a large number of users established social relations in social networks by mutual friends or mutual concern,which forms the online social network with massive nodes.The data of online social network contains rich and valuable knowledge.And it is a challenge to query and mining the data,which results in the emergence of many research direction,such as community discovery,influence analysis,team formation in social networks and so on.The problem of team formation aims at finding a team of experts who not only satisfy the requirements of the given task but also connect each other closely.The existing researches on team formation in social network stressed on the strong relationship among experts,which will reduce communication cost between members so that they can complete the task successfully.However,in practical applications,there are a lot of demands that need members in a team have weak ties,which can guarantee that the team has the diversified attitudes and no prejudice.Based on this requirement,this paper proposes a problem of team formation with weak ties in social networks by introducing the concept of weak ties in sociology.This problem is to find a team with weak ties between members and to satisfy the requirement of skills and experience.For example,in project evaluation,we want to find the team of experts which have weak ties between each other and each members have high experience value,through this we can guarantee the impartial evaluation results.The public judge team is widely used in the resolution of trade dispute and TV program selection.If members in a team have weak ties that can avoid convergence evaluation results,so that to guarantee the fairness of the results.In the spreading efficiency,such as advertising on social networking platform,if advertisers can focus their limited resources on the nodes that have high influence and weak ties between each other,they will avoid the local transmission of information only among the closely tied nodes.And by doing that,advertisers could make the information spread widely and enhance the advertising effect.This paper uses hop and edge weights between nodes to measure weak ties and shows the problem is NP-Hard.We proposes three kinds of algorithms to solve problem,the greedy algorithm,exact algorithm,?-approximation algorithm.They all have their own characteristics and application area.Among them,the greedy algorithm includes two kinds of greedy strategy,greedy strategy based on node score and the greedy strategy connecting node score and graph structure.Although greedy algorithm is efficient and suitable for massive data,it can't guarantee solution quality.Exact algorithms adopt the backtracking and dynamic programming algorithm,which suit for small datasets.The a-approximation algorithm is based on the exact dynamic programming algorithm,which only reserves the solution that can guarantee approximate rate.By doing this,the algorithm not only gets high-quality solutions but also guarantees approximation rate.The paper conducts extensive experiments to evaluate the performance of different algorithms and the results of queries through real ACM and DBLP author datasets.Experiment results show that the dynamic programming algorithm obtains an order of magnitude speed-up comparing backtracking algorithm and approximate algorithm also have high efficiency.Finally,this paper also analyzes the result of queries and the influence of team.The experiments show that the greedy strategy connecting node scores and graph structure is better than only based on scores in the quality of result and approximate algorithm is superior to the former.At the same time,this paper analyzes the influence of team by counting the maximum influence nodes and communities of team.The results show that the weak ties team has greater influence.