ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (11): 2654-2665.doi: 10.7544/issn1000-1239.2016.20150617

• 信息处理 • 上一篇    

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

刘勇,韩雪,李金宝,任倩倩,王楠   

  1. (黑龙江大学计算机科学技术学院 哈尔滨 150080) (黑龙江省数据库与并行计算重点实验室(黑龙江大学) 哈尔滨 150080) (acliuyong@sina.com)
  • 出版日期: 2016-11-01
  • 基金资助: 
    国家自然科学基金项目(61370222,61300225);黑龙江省自然科学基金项目(F201430);黑龙江省高校科技创新团队建设计划项目(2013TD012);黑龙江省教育厅科技研究项目(12531476);哈尔滨科技创新人才研究专项资金项目(2012RFQXG096)

Collaboration Algorithm in Social Networks Based on Tasks with Partial Relation

Liu Yong, Han Xue, Li Jinbao, Ren Qianqian, Wang Nan   

  1. (School of Computer Science and Technology, Heilongjiang University, Harbin 150080) (Key Laboratory of Database and Parallel Computing of Heilongjiang Province (Heilongjiang University), Harbin 150080)
  • Online: 2016-11-01

摘要: 针对不同任务之间通常存在偏序关系这种实际情况,提出了基于偏序任务的社会网络合作问题(collaboration problem in social networks based on tasks with partial ordering relations, CSN-TPR).该问题研究如何从社会网络中选择合适的团队来合作完成具有偏序关系的任务集,使得由通信代价、时间代价和预算代价构成的总体代价性能最优.首先证明了CSN-TPR是NP-hard问题,然后利用爬山法、分支限界策略和动态规划方法提出了近似算法HillClimbingTF_BBS.HillClimbingTF_BBS算法不仅输出有效的团队,而且能给出团队成员的具体任务分配以及每项任务的开始时间. 真实数据上的实验结果表明: HillClimbingTF_BBS算法能有效并高效求解CSN-TPR.

关键词: 社会网络, 合作, 偏序关系, 爬山法, 分支限界

Abstract: 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 which 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 HillClimbingTF_BBS can solve CSN-TPR effectively and efficiently.

Key words: social networks, collaboration, partial relation, hill-climbing, branch and bound

中图分类号: