臺灣博碩士論文加值系統

近年來,許多研究從不同角度探討了基於社群網路的組隊問題；然而在過去的研究中，大多僅考量少數影響組隊的因素。另外，這些研究中所使用的能力模型僅允許使用與專案需求相同技能的人才；而不考慮相近技能之人才。為了能更貼近現實生活中的組隊需求，我們的研究中除了考量兩項影響組隊結果最大的因素：溝通及人力成本外，更比起過往之研究探討更多可能影響組隊結果的因素。我們也提出了階層式能力模型，該能力模型允許團隊中擁有與專案需求相近技能的人才、而非只能選入專案所需技能的專家，以提高組隊的彈性。我們更提出了基於多目標最佳化理論的演算法，該演算法可根據使用者在單一目標下給定的預算，找出在另一目標下最佳化的團隊。這樣的演算法可解決在現實生活中，溝通成本與人力成本常常必須有所取捨的情況，並提供不同預算下的組隊建議。在實驗中不但證明了我們的問題假設是合理的，同時所提出的演算法也能比過去的研究找到成本更低且符合專案需求的團隊。

Social network-based team formation problem has been widely studied from different aspects. However, many of the previous studies only consider few factors while forming a team. The skills in earlier works were treated equally where assigning experts possess alternative skills for a required skill is not allowed. To better fit real word scenarios, our work considers more factors including the most important two: communication cost and personnel cost. We propose a novel hierarchical skill model to let skills interchangeable. We also develop a two-step optimization framework under previous settings to deal with the trade-off between communication cost and personnel cost. It lets users could form a team based on their desired budget on one of the costs. Finally the experiments show that our proposed framework and skill model is reasonable and have better performance than earlier works.

中文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 Hierarchical Skill Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 Covering Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.3 Skill Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.4 HSM-TF Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5 Proposed Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.1 Data Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 Finding Best Team with Bounded Communication Cost . . . . . . . . . . . . . . 24
5.2.1 Selection of Initial Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2.2 Spanning the Team . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.3 Finding Pareto-optimal Teams . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.1 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.2 Comparative Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.3 Experiment Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.3.1 Task Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.3.2 Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.4 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

[1] A. Anagnostopoulos, L. Becchetti, C. Castillo, A. Gionis, and S. Leonardi. Power in unity: Forming teams in large-scale community systems. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management, CIKM ’10, pages 599–608, 2010.
[2] A. Anagnostopoulos, L. Becchetti, C. Castillo, A. Gionis, and S. Leonardi. Online team formation in social networks. In Proceedings of the 21st International Conference on World Wide Web, WWW ’12, pages 839–848, 2012.
[3] A. Baykasoglu, T. Dereli, and S. Das. Project team selection using fuzzy optimization approach. Cybernetics and Systems, 38(2):155–185, Feb. 2007.
[4] 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, May 2004.
[5] K. Deb. Multi-Objective Optimization Using Evolutionary Algorithms. Wiley Interscience Series in S. Wiley, 2001.
[6] C. Duin, A. Volgenant, and S. Voß. Solving group steiner problems as steiner problems. European Journal of Operational Research, 154(1):323 – 329, 2004.
[7] L. Egghe. Theory and practise of the g-index. Scientometrics, 69(1):131–152, Oct 2006.
[8] F. Farhadi, M. Sorkhi, S. Hashemi, and A. Hamzeh. An effective framework for fast expert mining in collaboration networks: A group-oriented and cost-based method. Journal of Computer Science and Technology, 27(3):577–590, 2012.
[9] L. C. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40(1):35– 41, 1977.
[10] A. Gajewar and A. D. Sarma. Multi-skill collaborative teams based on densest subgraphs. In Proceedings of the 2012 SIAM International Conference on Data Mining, pages 165–176, 2012.
[11] M.-C. Juang, C.-C. Huang, and J.-L. Huang. Efficient algorithms for team formation with a leader in social networks. The Journal of Supercomputing, 66(2):721–737, 2013.
[12] K. Kamel, N. Tubaiz, O. AlKoky, and Z. AlAghbari. Toward forming an effective team using social network. In 2011 International Conference on Innovations in Information Technology, pages 308–312, April 2011.
[13] M. Kargar and A. An. Discovering top-k teams of experts with/without a leader in social networks. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management, CIKM ’11, pages 985–994, 2011.
[14] M. Kargar, A. An, and M. Zihayat. Efficient Bi-objective Team Formation in Social Networks, pages 483–498. Springer Berlin Heidelberg, 2012.
[15] M. Kargar, M. ZiHayat, and A. An. Finding affordable and collaborative teams from a network of experts. In Proceedings of the 13th SIAM International Conference on Data Mining, pages 587–595, 2013.
[16] T. Lappas, K. Liu, and E. Terzi. Finding a team of experts in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 467–476, 2009.
[17] C.-T. Li, M.-K. Shan, and S.-D. Lin. On team formation with expertise query in collaborative social networks. Knowledge and Information Systems, 42(2):441–463, 2015.
[18] A. Majumder, S. Datta, and K. Naidu. Capacitated team formation problem on social networks. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’12, pages 1005–1013, 2012.
[19] G. Sabidussi. The centrality index of a graph. Psychometrika, 31(4):581–603, Dec 1966.
[20] J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su. Arnetminer: Extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’08, pages 990–998, 2008.
[21] Y.-C. Teng, J.-Z. Wang, and J.-L. Huang. Team formation with the communication load constraint in social networks. In PAKDD 2014 International Workshops, pages 125–136, 2014.
[22] C. Wang, M. Danilevsky, N. Desai, Y. Zhang, P. Nguyen, T. Taula, and J. Han. A phrase mining framework for recursive construction of a topical hierarchy. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’13, 2013.
[23] H. Wi, S. Oh, J. Mun, and M. Jung. A team formation model based on knowledge and collaboration. Expert Systems with Applications, 36(5):9121–9134, July 2009.
[24] Y. Yang and H. Hu. Team formation with time limit in social networks. In Proceedings 2013 International Conference on Mechatronic Sciences, Electric Engineering and Computer (MEC), pages 1590–1594, Dec 2013.
[25] H. Yin, B. Cui, and Y. Huang. Finding a wise group of experts in social networks. In Proceedings of the 7th International Conference on Advanced Data Mining and Applications - Volume Part I, ADMA’11, pages 381–394, 2011.
[26] E. Zitzler, D. Brockhoff, and L. Thiele. The hypervolume indicator revisited: On the design of pareto-compliant indicators via weighted integration. In Evolutionary multi-criterion optimization, pages 862–876. Springer, 2007.
[27] A. Zzkarian and A. Kusiak. Forming teams: an analytical approach. IIE Transactions, 31(1):85–97, 1999.