×

zbMATH — the first resource for mathematics

Social structure optimization in team formation. (English) Zbl 1349.90547
Summary: This paper presents a mathematical framework for treating the Team Formation Problem explicitly incorporating Social Structure (TFP-SS), the formulation of which relies on modern social network analysis theories and metrics. While recent research qualitatively establishes the dependence of team performance on team social structure, the presented framework introduces models that quantitatively exploit such dependence. Given a pool of individuals, the TFP-SS objective is to assign them to teams so as to achieve an optimal structure of individual attributes and social relations within the teams. The paper explores TFP-SS instances with measures based on such network structures as edges, full dyads, triplets, k-stars, etc., in undirected and directed networks. For an NP-Hard instance of TFP-SS, an integer program is presented, followed by a powerful Lin-Kernighan-TFP (LK-TFP) heuristic that performs variable-depth neighborhood search. The idea of such \(\lambda\)-opt sequential search was first employed by Lin and Kernighan, and refined by Helsgaun, for successfully treating large Traveling Salesman Problem instances but has seen limited use in other applications. This paper describes LK-TFP as a tree search procedure and discusses the reasons of its effectiveness. Computational results for small, medium and large TFP-SS instances are reported using LK-TFP and compared with those of an exact algorithm (CPLEX) and a Standard Genetic Algorithm (SGA). Finally, the insights generated by the presented framework and directions for future research are discussed.

MSC:
90B70 Theory of organizations, manpower planning in operations research
91D30 Social networks; opinion dynamics
90B10 Deterministic network models in operations research
90C27 Combinatorial optimization
Software:
LKH; CPLEX; BBMCL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abbasi A, Altmann J. On the correlation between research performance and social network analysis measures applied to research collaboration networks. In: 44th Hawaii international conference on systems science (HICSS-44), January 4-7, Hawaii, USA; 2011.
[2] Agrawal R, Golshan B, Terzi E. Forming beneficial teams of students in massive online classes. In: Proceedings of the first ACM conference on Learning@ scale conference. ACM; Atlanta, Georgia, USA: 2014. p. 155-6.
[3] Agustín-Blas, L. E.; Salcedo-Sanz, S.; Ortiz-García, E. G.; Portilla-Figueras, A.; Pérez-Bellido, Á. M.; Jiménez-Fernández, S., Team formation based on group technologya hybrid grouping genetic algorithm approach, Comput Oper Res, 38, 2, 484-495, (2011) · Zbl 1232.68099
[4] Albert, R.; Barabási, A.-L., Statistical mechanics of complex networks, Rev Mod Phys, 74, 1, 47, (2002) · Zbl 1205.82086
[5] Aral, S.; Muchnik, L.; Sundararajan, A., Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks, Proc Natl Acad Sci, 106, 51, 21544-21549, (2009)
[6] Arulselvan, A.; Commander, C. W.; Elefteriadou, L.; Pardalos, P. M., Detecting critical nodes in sparse graphs, Comput Oper Res, 36, 7, 2193-2200, (2009) · Zbl 1158.90411
[7] Awal, G. K.; Bharadwaj, K., Team formation in social networks based on collective intelligence-an evolutionary approach, Appl Intell, 41, 2, 627-648, (2014)
[8] Baker, K.; Powell, S., Methods for assigning students to groupsa study of alternative objective functions, J Oper Res Soc, 53, 4, 397-404, (2002) · Zbl 1130.90334
[9] Balasundaram, B.; Butenko, S.; Hicks, I. V., Clique relaxations in social network analysisthe maximum k-plex problem, Oper Res, 59, 1, 133-142, (2011) · Zbl 1218.90228
[10] Balkundi, P.; Barsness, Z.; Michael, J. H., Unlocking the influence of leadership network structures on team conflict and viability, Small Group Res, 40, 3, 301-322, (2009)
[11] Bergey, P.; King, M., Team machinea decision support system for team formation, Decis Sci J Innov Educ, 12, 2, 109-130, (2014)
[12] Bettinelli, A.; Liberti, L.; Raimondi, F.; Savourey, D., The anonymous subgraph problem, Comput Oper Res, 40, 4, 973-979, (2013) · Zbl 1349.05321
[13] Borgatti, S. P., Centrality and network flow, Soc Netw, 27, 1, 55-71, (2005)
[14] Borgatti, S. P.; Halgin, D. S., On network theory, Organ Sci, 22, 5, 1168-1181, (2011)
[15] Ceravolo, D. J.; Schwartz, D. G.; Foltz-Ramos, K. M.; Castner, J., Strengthening communication to overcome lateral violence, J Nurs Manag, 20, 5, 599-606, (2012)
[16] Chatterjee, S.; Carrera, C.; Lynch, L. A., Genetic algorithms and traveling salesman problems, Eur J Oper Res, 93, 3, 490-510, (1996) · Zbl 0912.90276
[17] Chen, S.-J.; Lin, L., Modeling team member characteristics for the formation of a multifunctional team in concurrent engineering, IEEE Trans Eng Manag, 51, 2, 111-124, (2004)
[18] Contractor, N. S.; Wasserman, S.; Faust, K., Testing multitheoretical, multilevel hypotheses about organizational networksan analytic framework and empirical example, Acad Manag Rev, 31, 3, 681-703, (2006)
[19] Cutshall, R.; Gavirneni, S.; Schultz, K., Indiana University’s Kelley school of business uses integer programming to form equitable, cohesive student teams, Interfaces, 37, 3, 265-276, (2007)
[20] Dorn C, Dustdar S. Composing near-optimal expert teams: a trade-off between skills and connectivity. In: On the move to meaningful internet systems: OTM 2010. Springer; Hersonissos, Crete, Greece: 2010. p. 472-89.
[21] Farasat A, Menhaj MB, Mansouri T, Moghadam MRS. Aro: a new model-free optimization algorithm inspired from asexual reproduction. Appl Soft Comput 2010;10(4):1284-92.
[22] Fitzpatrick E, Askin R, Goldberg J. Using student conative behaviors and technical skills to form effective project teams. In: 31st annual frontiers in education conference, 2001, vol. 3. IEEE; Reno, NV, USA: 2001. p. S2G-8.
[23] Fitzpatrick, E. L.; Askin, R. G., Forming effective worker teams with multi-functional skill requirements, Comput Ind Eng, 48, 3, 593-608, (2005)
[24] Gamboa, D.; Rego, C.; Glover, F., Data structures and ejection chains for solving large-scale traveling salesman problems, Eur J Oper Res, 160, 1, 154-171, (2005) · Zbl 1067.90140
[25] Garey, M. R.; Johnson, D. S., Computers and intractability, vol. 174, (1979), Freeman New York · Zbl 0411.68039
[26] Gaston M, Simmons J, DesJardins M. Adapting network structures for efficient team formation. In: Proceedings of the AAAI 2004 fall symposium on artificial multi-agent learning; 2004.
[27] Girvan, M.; Newman, M. E., Community structure in social and biological networks, Proc Natl Acad Sci, 99, 12, 7821-7826, (2002) · Zbl 1032.91716
[28] Goyal A, Bonchi F, Lakshmanan LV. Learning influence probabilities in social networks. In: Proceedings of the third ACM international conference on Web search and data mining. ACM; New York City, New York, USA: 2010. p. 241-50.
[29] Hahn, J.; Moon, J. Y.; Zhang, C., Emergence of new project teams from open source software developer networksimpact of prior collaboration ties, Inf Syst Res, 19, 3, 369-391, (2008)
[30] Helsgaun, K., An effective implementation of the lin-kernighan traveling salesman heuristic, Eur J Oper Res, 126, 1, 106-130, (2000) · Zbl 0969.90073
[31] Juang, M.-C.; Huang, C.-C.; Huang, J.-L., Efficient algorithms for team formation with a leader in social networks, J Supercomput, 1-17, (2013)
[32] Kargar M, An A, Zihayat M. Efficient bi-objective team formation in social networks. In: Machine learning and knowledge discovery in databases. Springer; Bristol, UK: 2012. p. 483-98.
[33] Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining. ACM; Washington, DC, USA: 2003. p. 137-46. · Zbl 1337.91069
[34] Kim BW, Kim JM, Lee WG, Shon JG. Parallel balanced team formation clustering based on mapreduce. In: Advances in computer science and ubiquitous computing. Springer; 2015. p. 671-5.
[35] Kothari, R.; Ghosh, D., Insertion based lin-kernighan heuristic for single row facility layout, Comput Oper Res, 40, 1, 129-136, (2013) · Zbl 1349.90566
[36] Lappas T, Liu K, Terzi E. Finding a team of experts in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM; Paris, France: 2009. p. 467-76.
[37] Leite AR, Borges AP, Carpes LM, Enembreck F. Improving the distributed constraint optimization using social network analysis. In: Advances in artificial intelligence - SBIA 2010. Springer; São Bernardo do Campo, Brazil: 2011. p. 243-52.
[38] Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling-salesman problem, Oper Res, 21, 2, 498-516, (1973) · Zbl 0256.90038
[39] Mahar, S.; Winston, W.; Wright, P. D., Eli lilly and company uses integer programming to form volunteer teams in impoverished countries, Interfaces, 43, 3, 268-284, (2013)
[40] Manser, T., Teamwork and patient safety in dynamic domains of healthcarea review of the literature, Acta Anaesthesiol. Scand., 53, 2, 143-151, (2009)
[41] Nascimento, M. C.; Pitsoulis, L., Community detection by modularity maximization using grasp with path relinking, Comput Oper Res, 40, 12, 3121-3131, (2013) · Zbl 1348.91237
[42] Newman, M. E., Modularity and community structure in networks, Proc Natl Acad Sci, 103, 23, 8577-8582, (2006)
[43] Pattillo, J.; Youssef, N.; Butenko, S., On clique relaxation models in network analysis, Eur J Oper Res, (2012) · Zbl 1247.91162
[44] Pirim, H.; Ekşioğlu, B.; Perkins, A. D.; Yüceer, Ç., Clustering of high throughput gene expression data, Comput Oper Res, 39, 12, 3046-3061, (2012) · Zbl 1349.62554
[45] Rego, C.; Gamboa, D.; Glover, F.; Osterman, C., Traveling salesman problem heuristicsleading methods, implementations and latest advances, Eur J Oper Res, 211, 3, 427-441, (2011) · Zbl 1237.90209
[46] Robins, G.; Pattison, P.; Kalish, Y.; Lusher, D., An introduction to exponential random graph \((¡ \operatorname{i} ¿ \operatorname{p} ¡ / \operatorname{i} ¿ ¡ \sup ¿^\ast ¡ / \sup ¿)\) models for social networks, Soc Netw, 29, 2, 173-191, (2007)
[47] Ronald, B., Structural holes: the social structure of competition, (1992), Cambridge Harvard
[48] Ruef, M.; Aldrich, H. E.; Carter, N. M., The structure of founding teamshomophily, strong ties, and isolation among us entrepreneurs, Am Soc Rev, 195-222, (2003)
[49] Salari, M.; Naji-Azimi, Z., An integer programming-based local search for the covering salesman problem, Comput Oper Res, 39, 11, 2594-2602, (2012) · Zbl 1251.90338
[50] San Segundo, P.; Rodríguez-Losada, D.; Jiménez, A., An exact bit-parallel algorithm for the maximum clique problem, Comput Oper Res, 38, 2, 571-581, (2011) · Zbl 1231.90369
[51] San Segundo, P.; Tapia, C., Relaxed approximate coloring in exact maximum clique search, Comput Oper Res, 44, 185-192, (2014) · Zbl 1307.90153
[52] Shi, Z.; Hao, F., A strategy of multi-criteria decision-making task ranking in social-networks, J Supercomput, 1-16, (2013)
[53] Snijders, T. A.; Van de Bunt, G. G.; Steglich, C. E., Introduction to stochastic actor-based models for network dynamics, Soc Netw, 32, 1, 44-60, (2010)
[54] Squillante, M., Decision making in social networks, Int J Intell Syst, 25, 3, 255, (2010)
[55] Wasserman, S.; Faust, K., Social network analysis: methods and applications, vol. 8, (1994), Cambridge University Press
[56] Wi, H.; Oh, S.; Mun, J.; Jung, M., A team formation model based on knowledge and collaboration, Expert Syst Appl, 36, 5, 9121-9134, (2009)
[57] Zhang, L.; Zhang, X., Multi-objective team formation optimization for new product development, Comput Ind Eng, 64, 3, 804-811, (2013)
[58] Zhang, Z.-x.; Luk, W.; Arthur, D.; Wong, T., Nursing competenciespersonal characteristics contributing to effective nursing performance, J Adv Nurs, 33, 4, 467-474, (2001)
[59] Zhong, X.; Huang, Q.; Davison, R. M.; Yang, X.; Chen, H., Empowering teams through social network ties, Int J Inf Manag, 32, 3, 209-220, (2012)
[60] Zhu, M.; Huang, Y.; Contractor, N. S., Motivations for self-assembling into project teams, Soc Netw, 35, 2, 251-264, (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.