社群網路下考量溝通負載平衡之組隊問題

Abstract

社群網路中的組隊問題討論當有一個計劃需要執行時，如何找到適當的隊伍使整個隊伍能夠完成計畫所需要的技術是相當重要的，在這當中隊員間溝通的難易度和團隊的組織架構也將會影響到計畫執行的效率。在先前的研究當中，考慮到領導者架構下的組隊問題，但是此架構下並未考慮到領導者所需負擔的龐大溝通。因此我們提出了溝通負擔平衡的組隊問題，並設計出兩個階段的解題架構，分別是先找到滿足計畫所需能力的所有隊伍以及建立隊伍的組織架構。在分析完直觀地暴力法後，我們另外也提出了ACOpt和ACappx兩個較有效率的演算法。ACOpt對於每個隊伍都會計算該隊伍在建立成組織之後的基底分數，透過這個分數來排除掉不適合的隊伍，節省建立組織的運算量。而ACAppx則是利用近似的演算法來尋找隊伍的組織架構。我們利用了真實的資料專家社群網路來評估我們提出的演算法。在實驗結果中我們發現，透過我們所提出的ACOpt 和ACAppx 可以讓查詢速度加快，並在規模較大的社群網路中有良好的擴充性。

Given a project or task requiring a set of skills, the team formation problem in social net-works aims to find a team that can handle all the skills and the communication cost of the team is minimal. In previous work, the team formation problem with a leader is studied while the problem ignored the burdensome communication cost for the leader as the team size grows up. To overcome this situation, the authors proposed the communication load balanced team for-mation problem and design a two-stage architecture to solve the problem. The Brute-Force can find the team having the minimal load balanced communication cost but the computational cost for the method is heavy in a large scale social network. The ACOpt is proposed to maintain a lower bound of a team thus avoid some teams from structure building. The ACAppx applies the approximation method in previous work to accelerate the process of structure building. Exper-imental results show that the proposed ACOpt and ACAppx can reduce the execution time and are more scalable in large scale social network.