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

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