Abstract: As the online social network grows rapidly, the team formation problem becomes more and more popular. Previous research on team formation aimed at finding a team of experts with the lowest communication cost. However, in expert or public jury, as untighten relationship can guarantee diversified attitudes and refrain from prejudice, there are numerous quests which to find a weak connected team. Based on this requirement, this paper proposes the problem of team formation with weak ties in social networks by introducing the concept of weak ties in sociology. This problem aims to find a team with weak ties between members and satisfy the requirement of skills and experience, it is an NP-hard problem. This paper designs three kinds of algorithms for the problem, they are greedy algorithm, exact algorithm and α-approximate algorithm. Every kind of algorithm has distinct property and scope. The experimental results on ACM and DBLP real datasets show the quality and confirm the effectiveness and efficiency of proposed algorithms.

Key words: social network, team formation, weak ties, greedy algorithm, exact algorithm, approximate algorithm

摘要： 随着在线社会网络的迅速发展，社会网络的团队形成问题逐渐成为研究热点。现有的社会网络中团队形成问题目标是寻找一个成员间沟通代价最小的团队。然而，实际应用中团队成员间的不紧密关系使得团队的观点多样化、多角度、无偏见，可以广泛应用于形成专家评审团队、大众评审团等。基于此需求，将社会学的弱关系概念引入团队形成问题中，提出了一种社会网络中弱关系团队形成问题。该问题旨在寻找成员间为弱关系，同时满足技能、经验值要求的一个团队，为NP-hard问题。提出了3类算法解决该问题，分别为贪心算法、精确算法、α -近似算法，每类算法有各自的特点与适用范围。利用ACM和DBLP两类真实的数据集进行实验，综合评估了各类算法的效率与求解质量，证明了提出算法的有效性。

关键词: 社会网络, 团队形成, 弱关系, 贪心算法, 精确算法, 近似算法