高效率解決社群網路中領導者架構下的組隊問題

Efficient Algorithms for the Team Formation Problem with a Leader in Social Networks

莊明欽(Ming-Chin Juang)

指導教授 ： 黃俊龍

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00695

摘要

當要開始執行一個計劃或研究時，如何組成符合需求且有效率的的團隊是一個重要的問題。在團隊組織中，具有領導者的團隊相當常見，領導者通常負責協調並管理計畫的進行。在先前的研究當中，提出了在領導者架構下的組隊問題並提出解法，來找到最佳的領導者及相對應的團隊。但在先前研究提出的演算法，將所有在社群網路中的專家都當作領導者的候選者並組織相對應的團隊，再從當中選出最佳的團隊當作答案，需要大量的運算。我們提出了兩個有效率的演算法來解決在領導者架構下的組隊問題，分別是BCPruning 演算法及SSPruning 演算法。BCPruning 演算法先尋找有領導者潛力的候選者，盡早得到良好的答案來減少不合適的候選者的運算。SSPruning 演算法利用區域性的資訊交換，為候選者計算基底分數，在為候選者組隊時可以早期發現不合適的候選者，減少運算量。我們利用了真實的資料架構專家社群網路，藉由此社群網路來評估先前及我們提出的演算法。實驗結果顯示，我們所提出的方法對於查詢速度有相當大的改善。當處理較大的社群網路時，也表現出良好的擴充性。

關鍵字

社群網路 ； 社群智慧 ； 組隊問題

並列摘要

Given a project with a list of required skills and a set of candidates, it is an important and challenging problem of finding an appropriate team of experts that have not only the required skill set but also the minimal communication cost. Prior work presented the team formation problem with a leader where the leader is responsible for coordinating and managing the project. To find the best leader and the corresponding team, the prior algorithm exhaustively evaluates each candidate and the associated team, incurring significant computational cost. In this thesis, the authors propose two efficient algorithms, namely the BCPruning algorithm and the SSPruning algorithm, to accelerate the discovery of the best leader and the corresponding team by reducing the search space of team formation for candidates. The BCPruning algorithm aims to select better initial leader candidates to obtain lower communication cost, achieving effective candidate pruning. On the other hand, the SSPruning algorithm enables each leader candidate to have a lower bound on the communication cost, leading some candidates to be safely pruned without any computation. We conduct experiments on the real dataset to evaluate the performance of the proposed algorithms. The experimental results show that the proposed algorithms outperform the prior algorithm in terms of computational time. Moreover, the experimental results indicate that the proposed algorithms are more scalable than the prior algorithm.

並列關鍵字

Social Network ； Social Intelligence ； Team Formation

參考文獻

[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 int'l conf. on Information

and knowledge management, 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, pages 839--848, 2012.

on Knowledge discovery and data mining, pages 44--54, 2006.

[4] A. Baykasoglu, T. Dereli, and S. Das. Project team selection using Fuzzy optimization approach. Cybern. Syst., 38(2):155--185, Feb. 2007.