應用於大型電信社群網路中核心人物搜尋的雲端運算平行處理演算法

Abstract

在本篇論文中，我們提出一個應用於大型電信社群網路中核心 人物搜尋的雲端運算平行處理演算法。首先我們利用分治法 (Divideand-conquer)，此一平行化的方法來從大型電信社群網路中找出 k-truss 定義下的群體，然後利用特徵向量中心度 (Eigenvector Centrality) 來定 義群體中的核心人物 (Alpha user)。除此之外，我們提出了建立在最 短路徑演算法之上的核心人物平行排序演算法，來排序、比較不同群 體的核心人物重要性。我們也提出了一個具有偵測以及拆解功能的平 行演算法來處理位於電信社群網路中的超大群社群。本篇論文中，除 了用人工資料來進行測試實驗之外，我們也將此演算法實際應用分析 於由電信公司所提供的通聯記錄所建立的真實大型電信社群網路中。

In this thesis, we propose novel MapReduce algorithms to search for and rank alpha users in massive telecom social networks. We first apply the principle of divide-and-conquer to find out trusses in a social graph and then use the eigenvector centrality to identify alpha users in the trusses in parallel. In addition, we propose ranking alpha users in distinct trusses based on their shortest path coverage. Furthermore, we propose novel algorithms to efficiently detect and decompose giant components in a social graph. In addition to synthetic social networks, we have used the proposed algorithms to analyze real smart phone social networks that are created based on call detail records collected by a telecom operator.