›› 2017,Vol. 32 ›› Issue (1): 139-154.doi: 10.1007/s11390-017-1710-6

所属专题: Artificial Intelligence and Pattern Recognition

• • 上一篇    下一篇

参与约束的团队形成问题

Yu Zhou1,2周瑜), Student Member, CCF, Jian-Bin Huang2,*(黄健斌), Senior Member, CCF, Member, ACM, Xiao-Lin Jia3(贾晓琳), Member, CCF, and He-Li Sun3(孙鹤立), Member, CCF   

  1. 1 School of Computer Science and Technology, Xidian University, Xi'an 710071, China;
    2 School of Software, Xidian University, Xi'an 710071, China;
    3 Department of Computer Science and Technology, Xi'an Jiaotong University, Xi'an 710049, China
  • 收稿日期:2016-01-27 修回日期:2016-09-21 出版日期:2017-01-05 发布日期:2017-01-05
  • 通讯作者: Jian-Bin Huang E-mail:jbhuang@xidian.edu.cn
  • 作者简介:Yu Zhou is a Ph.D. student in the School of Computer Science and Technology at Xidian University, Xi'an. His research interests include data mining, statistical machine learning and heterogeneous information network.
  • 基金资助:

    The work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61472299, 61540008, 61672417 and 61602354, the Fundamental Research Funds for the Central Universities of China under Grant No. BDY10, the Shaanxi Postdoctoral Science Foundation, and the Natural Science Basic Research Plan of Shaanxi Province of China under Grant No. 2014JQ8359.

On Participation Constrained Team Formation

Yu Zhou1,2周瑜), Student Member, CCF, Jian-Bin Huang2,*(黄健斌), Senior Member, CCF, Member, ACM, Xiao-Lin Jia3(贾晓琳), Member, CCF, and He-Li Sun3(孙鹤立), Member, CCF   

  1. 1 School of Computer Science and Technology, Xidian University, Xi'an 710071, China;
    2 School of Software, Xidian University, Xi'an 710071, China;
    3 Department of Computer Science and Technology, Xi'an Jiaotong University, Xi'an 710049, China
  • Received:2016-01-27 Revised:2016-09-21 Online:2017-01-05 Published:2017-01-05
  • Contact: Jian-Bin Huang E-mail:jbhuang@xidian.edu.cn
  • About author:Yu Zhou is a Ph.D. student in the School of Computer Science and Technology at Xidian University, Xi'an. His research interests include data mining, statistical machine learning and heterogeneous information network.
  • Supported by:

    The work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61472299, 61540008, 61672417 and 61602354, the Fundamental Research Funds for the Central Universities of China under Grant No. BDY10, the Shaanxi Postdoctoral Science Foundation, and the Natural Science Basic Research Plan of Shaanxi Province of China under Grant No. 2014JQ8359.

互联网上的任务分配问题已经被应用在许多领域,比如:在线劳动力市场,在线论文评审,社交活动组织等。在本文中,我们关注与在线劳动力市场相关的任务分配问题,也被称为ClusterHire问题。我们改进了已有ClusterHire问题的定义,并提出一个高效的算法INFLUENCE。此外,我为在ClusterHire问题上增加了一个参与约束。该参与约束是为了防止团队中专家的负载不均匀从而造成某些专家负担过重。对于该参与约束问题,我们设计了两个算法,ProjectFirst和ERA。ProjectFirst算法是通过不断地向当前团队中增加满足参与约束的专家,从而形成团队。与之不同的是,ERA算法是同步不断地从当前团队中删除具有最小影响力的专家,从而形成团队。实验结果显示,(1)无论是输出团队的效果,还是时间效率,INFLUENCE均比当前算法表现更优秀;(2)ProjectFirst在时间效率上要比ERA算法更好,但ERA算法在输出团队的效果上更好。

Abstract: The task assignment on the Internet has been widely applied to many areas, e.g., online labor market, online paper review and social activity organization. In this paper, we are concerned with the task assignment problem related to the online labor market, termed as ClusterHire. We improve the definition of the ClusterHire problem, and propose an efficient and effective algorithm, entitled Influence. In addition, we place a participation constraint on ClusterHire. It constrains the load of each expert in order to keep all members from overworking. For the participation-constrained ClusterHire problem, we devise two algorithms, named ProjectFirst and Era. The former generates a participationconstrained team by adding experts to an initial team, and the latter generates a participation-constrained team by removing the experts with the minimum influence from the universe of experts. The experimental evaluations indicate that 1) Influence performs better than the state-of-the-art algorithms in terms of effectiveness and time efficiency; 2) ProjectFirst performs better than Era in terms of time efficiency, yet Era performs better than ProjectFirst in terms of effectiveness.

[1] Golshan B, Lappas T, Terzi E. Profit-maximizing cluster hires. In Proc. the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2014, pp.1196-1205.

[2] Chvatal V. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 1979, 4(3):233-235.

[3] Zzakarian A, Kusiak A. Forming teams:An analytical approach. ⅡE Trans., 1999, 31(1):85-97.

[4] Lappas T, Liu K, Terzi E. Finding a team of experts in social networks. In Proc. the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, June 28-July 1, 2009, pp.467-476.

[5] Anagnostonpoulos A, Becchetti L, Castillo C, Gionis A, Leonard S. Power in unity:Forming teams in large-scale community systems. In Proc. the 19th ACM International Conference on Information and Knowledge Management, October 2010, pp.599-608.

[6] Anagnostopoulos A, Becchetti L, Castillo C, Gionis A, Leonardi S. Online team formation in social networks. In Proc. the 21st International Conference on World Wide Web, April 2012, pp.839-848.

[7] Kargar M, An A. Discovering top-k teams of experts with/without a leader in social networks. In Proc. the 20th ACM International Conference on Information and Knowledge Management, October 2011, pp.985-994.

[8] Datta S, Majumder A, Naidu K. Capacitated team formation problem on social networks. In Proc. the 18th International Conference on Knowledge Discovery and Data Mining, August 2012, pp.1005-1013.

[9] Roy S B, Lakshmanan L S V, Liu R. From group recommendations to group formation. In Proc. the ACM SIGMOD International Conference on Management of Data, May 31-June 4, 2015, pp.1603-1616.

[10] Li L Y, Tong H H, Cao N, Ehrlich K, Lin Y R, Buchler N. Replacing the irreplaceable:Fast algorithms for team member recommendation. In Proc. the 24th International Conference on World Wide Web, May 2015, pp.636-646.

[11] Li C T, Shan M K. Composing activity groups in social networks. In Proc. the 21st International Conference on Information and Knowledge Management, October 29-November 2, 2012, pp.2375-2378.

[12] Li K, Lu W, Bhagat S, Lakshmanan L V S, Yu C. On social event organization. In Proc. the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2014, pp.1206-1215.

[13] Feng K Y, Cong G, Bhowmick S S, Ma S. In search of influential event organizers in online social networks. In Proc. the ACM SIGMOD International Conference on Management of Data, June 2014, pp.63-74.

[14] Shuai H H, Yang D N, Yu P S et al. Willingness optimization for social group activity. Proceedings of the VLDB Endowment, 2013, 7(4):1035-1045.

[15] She J Y, Tong Y X, Chen L, Cao C C. Conflict-aware eventparticipant arrangement. In Proc. the 31st IEEE International Conference on Data Engineering, April 2015, pp.735-746.

[16] She J Y, Tong Y X, Chen L. Utility-aware social eventparticipant planning. In Proc. the ACM SIGMOD International Conference on Management of Data, May 31-June 4, 2015, pp.1629-1643.

[17] Shen C Y, Yang D N, Lee W C, Chen M S. Maximizing friend-making likelihood for social activity organization. In Proc. the 19th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, May 2015, pp.3-15.

[18] Armenatzoglou N, Pham H, Ntranos V, Papadias D, Shahabi C. Real-time multi-criteria social graph partitioning:A game theoretic approach. In Proc. the ACM SIGMOD International Conference on Management of Data, May 31-June 4, 2015, pp.1617-1628.

[19] Tong Y X, She J Y, Meng R. Bottleneck-aware arrangement over event-based social networks:The max-min approach. World Wide Web-Internet & Web Information Systems, 2016, 19(6):1151-1177.

[20] Dumais S T, Nielsen J. Automating the assignment of submitted manuscripts to reviewers. In Proc. the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, June 1992, pp.233-234.

[21] Karimzadehgan M, Zhai C X, Belford G. Multi-aspect expertise matching for review assignment. In Proc. the 17th ACM Conference on Information and Knowledge Management, October 2008, pp.1113-1122.

[22] Kou N M, Hou H L, Mamoulis N, Gong Z. Weighted coverage based reviewer assignment. In Proc. the ACM SIGMOD International Conference on Management of Data, May 31-June 4, 2015, pp.2031-2046.

[23] Mimno D, McCallum A. Expertise modeling for matching papers with reviewers. In Proc. the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2007, pp.500-509.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: