计算机科学与探索 ›› 2016, Vol. 10 ›› Issue (6): 773-785.DOI: 10.3778/j.issn.1673-9418.1507075
孙焕良1+,富珊珊1,刘俊岭1,2,于 戈2,许鸿斐2
SUN Huanliang1+, FU Shanshan1, LIU Junling1,2, YU Ge2, XU Hongfei2
摘要: 随着在线社会网络的迅速发展,社会网络的团队形成问题逐渐成为研究热点。现有的社会网络中团队形成问题目标是寻找一个成员间沟通代价最小的团队。然而,实际应用中团队成员间的不紧密关系使得团队的观点多样化、多角度、无偏见,可以广泛应用于形成专家评审团队、大众评审团等。基于此需求,将社会学的弱关系概念引入团队形成问题中,提出了一种社会网络中弱关系团队形成问题。该问题旨在寻找成员间为弱关系,同时满足技能、经验值要求的一个团队,为NP-hard问题。提出了3类算法解决该问题,分别为贪心算法、精确算法、α -近似算法,每类算法有各自的特点与适用范围。利用ACM和DBLP两类真实的数据集进行实验,综合评估了各类算法的效率与求解质量,证明了提出算法的有效性。