基于偏序任务的社会网络合作算法研究

摘要

The collaboration problem in social networks has attracted lots of interests among the data mining community .Previous work focused on finding a team with the lowest communication cost to complete all tasks in a project .However ,tasks in the realistic projects usually have partial ordering relations .Existing methods cannot deal with partial ordering relations ,and thus are not capable of obtaining an effective team .In this paper ,we study how to complete the tasks with partial ordering relations effectively ,and propose a novel collaboration problem in social networks ,named CSN‐TPR (collaboration problem in social networks based on tasks with partial ordering relations ) .Specifically , we investigate how to select an appropriate team in social networks to complete the tasks with partial ordering relations so as to minimize the total cost w hich is composed of communication cost ,time cost and budget cost .We firstly prove that CSN‐TPR is NP‐hard ,and then adopt hill‐climbing method , branch and bound strategy and dynamic programming method to propose an approximation algorithm called HillClimbingTF_BBS .HillClimbingTF_BBS can not only acquire an effective team ,but also obtain the task allocation of each team member and the start time of each task .The experimental results on real data show that HillClimbing T F_BBS can solve CSN‐T PR effectively and efficiently .%针对不同任务之间通常存在偏序关系这种实际情况，提出了基于偏序任务的社会网络合作问题（collaboration problem in social networks based on tasks with partial ordering relations ，CSN‐TPR）．该问题研究如何从社会网络中选择合适的团队来合作完成具有偏序关系的任务集，使得由通信代价、时间代价和预算代价构成的总体代价性能最优．首先证明了CSN‐TPR是NP‐hard问题，然后利用爬山法、分支限界策略和动态规划方法提出了近似算法HillClimbingTF＿BBS ．HillClimbingTF＿BBS算法不仅输出有效的团队，而且能给出团队成员的具体任务分配以及每项任务的开始时间．真实数据上的实验结果表明：HillClimbing T F＿BBS算法能有效并高效求解CSN‐T PR ．