Finding a team of experts in social networks

ABSTRACT

Given a task T, a pool of individuals X with different skills, and a social network G that captures the compatibility among these individuals, we study the problem of finding X, a subset of X, to perform the task. We call this the TEAM FORMATION problem. We require that members of X' not only meet the skill requirements of the task, but can also work effectively together as a team. We measure effectiveness using the communication cost incurred by the subgraph in G that only involves X'. We study two variants of the problem for two different communication-cost functions, and show that both variants are NP-hard. We explore their connections with existing combinatorial problems and give novel algorithms for their solution. To the best of our knowledge, this is the first work to consider the TEAM FORMATION problem in the presence of a social network of individuals. Experiments on the DBLP dataset show that our framework works well in practice and gives useful and intuitive results.

REFERENCES

• 1: E. M. Arkin and R. Hassin. Minimum-diameter covering problems. Networks, 36(3):147--155, 2000.
• 2: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150412]
• 3: Adil Baykasoglu , Turkay Dereli , Sena Das, PROJECT TEAM SELECTION USING FUZZY OPTIMIZATION APPROACH, Cybernetics and Systems, v.38 n.2, p.155-185, February 2007 [doi>10.1080/01969720601139041]
• 4: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 5: Michelle Cheatham , Kevin Cleereman, Application of Social Network Analysis to Collaborative Team Formation, Proceedings of the International Symposium on Collaborative Technologies and Systems, p.306-311, May 14-17, 2006 [doi>10.1109/CTS.2006.18]
• 6: Chandra Chekuri , Guy Even , Guy Kortsarz, A greedy approximation algorithm for the group Steiner problem, Discrete Applied Mathematics, v.154 n.1, p.15-34, 1 January 2006 [doi>10.1016/j.dam.2005.07.010]
• 7: S.-J. Chen and L. Lin. Modeling team member characteristics for the formation of a multifunctional team in concurrent engineering. IEEE Transactions on Engineering Management, 51(2):111--124, 2004.
• 8: C. W. Duin, A. Volgenant, and S. Vo{ss}. Solving group Steiner problems as Steiner problems. European Journal of Operational Research, 154(1):323--329, 2004.
• 9: Erin L. Fitzpatrick , Ronald G. Askin, Forming effective worker teams with multi-functional skill requirements, Computers and Industrial Engineering, v.48 n.3, p.593-608, May 2005 [doi>10.1016/j.cie.2004.12.014]
• 10: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem, Journal of Algorithms, v.37 n.1, p.66-84, Oct. 2000 [doi>10.1006/jagm.2000.1096]
• 11: M. Gaston, J. Simmons, and M. desJardins. Adapting network structures for efficient team formation. In In Proceedings of the AAAI Fall Symposium on Artificial Multi-agent Learning, 2004.
• 12: M. Jackson. Network formation. The New Palgrave Dictionary of Economics and the Law, 2008.
• 13: Gabriele Reich , Peter Widmayer, Beyond Steiner's Problem: A VLSI Oriented Generalization, Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science, p.196-210, June 14-16, 1989
• 14: H. Takahashi and A. Matsuyama. An approximate solution for the Steiner problem in graphs. Mathematica Japonica, 24:573--577, 1980.
• 15: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 16: Hyeongon Wi , Seungjin Oh , Jungtae Mun , Mooyoung Jung, A team formation model based on knowledge and collaboration, Expert Systems with Applications: An International Journal, v.36 n.5, p.9121-9134, July, 2009 [doi>10.1016/j.eswa.2008.12.031]
• 17: A. Zzkarian and A. Kusiak. Forming teams: an analytical approach. IIE Transactions, 31:85--97, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Experimentation, Theory

Keywords:
graph algorithms, social networks, team formation