標題: Team Formation with the Communication Load Constraint in Social Networks
作者: Teng, Yui-Chieh
Wang, Jun-Zhe
Huang, Jiun-Long
資訊工程學系
Department of Computer Science
關鍵字: Team formation;Degree-constrained minimum spanning tree;Social network
公開日期: 1-Jan-2014
摘要: Given a project requiring a set of skills, the team formation problem in social networks aims to find a team that can cover all the required skills and has the minimal communication cost. Previous studies considered the team formation problem with a leader and proposed efficient algorithms to address the problem. However, for large projects, a single leader is not capable of managing a team with a large number of team members. Thus, a number of leaders would be formed and organized into a hierarchy where each leader is responsible for only a limited number of team members. In this paper, we propose the team formation problem with the communication load constraint in social networks. The communication load constraint limits the number of team members a leader communicates with. To solve the problem, we design a two-phase framework. Based on the proposed framework, we first propose algorithm Opt to find an optimal team, under the communication load constraint, with minimal communication cost. For large social networks, we also propose algorithm Approx to find a nearly-optimal team. Experimental results show that algorithm Opt is able to find optimal teams and is more efficient than the brute-force algorithm. In addition, when nearly-optimal teams are acceptable, algorithm Approx is much more scalable than algorithm Opt for large social networks.
URI: http://dx.doi.org/10.1007/978-3-319-13186-3_12
http://hdl.handle.net/11536/125145
ISBN: 978-3-319-13186-3; 978-3-319-13185-6
ISSN: 0302-9743
DOI: 10.1007/978-3-319-13186-3_12
期刊: TRENDS AND APPLICATIONS IN KNOWLEDGE DISCOVERY AND DATA MINING
Volume: 8643
起始頁: 125
結束頁: 136
Appears in Collections:Conferences Paper


Files in This Item:

  1. 000354705300012.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.