社群網路中資訊傳播分析模型

Abstract

近年來，社群網路已成為人們分享、傳播資訊的重要管道。分析社群網路中的資訊傳播，也因此成為了重要的研究議題。過去的方法多著重於如何從社群網路中，找出最有影響力的人。然而，觀察資訊傳播的過程，能更有助於了解資訊是如何傳播、如何開始及結束。由於社群網路包含許多不同的社群，資訊的傳播常會因社群的分布而有所受限。再則，目前社群網路的使用者總數已經高達十億，在分析如此龐大的資料量時，雲端運算的架構則成為了不可或缺的角色。因此，在本篇論文中，我們提出一個以MapReduce為基礎的資訊傳播分析模型，來模擬在社群網路中，資訊傳播的過程。我們提出的模型分為兩個階段，在第一個階段，首先用矩陣來代表社群網路中，人與人的關係。由於一個人的人際關係有其上限，所以此矩陣通常是一個相當稀疏的矩陣。接著，我們利用馬可夫分群演算法來將所有使用者分群並將矩陣重新排列成帶狀矩陣。由於在此矩陣中，大部份的值都為零，所以我們得以加速並省下記憶體的使用量。在第二個階段，我們利用馬可夫鏈模型來模擬資訊傳播的過程，並找出在資訊傳播完畢後所形成的社群。因此，我們提出的模型可以模擬資訊傳播的過程，並找出在資訊傳播前後所形成的不同的社群，進而找出每個人或每個社群的影響範圍。由於我們的模型，採用帶狀矩陣與MapReduce的架構，它可以分析相當大的社群網路，我們的模型亦可以找出橋接者社群與散佈者社群，有助於我們確認每個社群所扮演的角色。

Analyzing information propagation in social networks has attracted more and more attention. Most previously proposed methods focus on finding the most influential people. However, monitoring the process of information propagation can help us better understand how the information spreads and where the information spread stops. Since a social network contains many communities, the spread of information is usually bounded within communities. The size of a social network is now up to billions. As a result, analyzing user behavior in social networks by a cloud computing infrastructure is indispensable. Therefore, in this thesis, we propose an effective information propagation model on the MapReduce framework. The proposed model contains two phases. In the first phase, we use a matrix to represent the relationship among users in the social network. Since a user in the social network usually has a limited number of relationships, the matrix is usually quite sparse. Next, we use the Markov Cluster Algorithm to cluster users into communities and re-arrange the matrix into a band matrix so that we can save a large amount of computation time and memory usage since most of the elements in the matrix are zero. In the second phase, we use Markov Chain Model to simulate the process of information propagation and find the communities after propagation. Since the proposed model exploits the MapReduce framework and band matrices to perform matrix multiplications, it allows us to deal with a large scale of social networks. Moreover, it can detect the communities before propagation (BC) and after propagation (AC) so that we are able to discover the boarder of information propagation for each user and for each BC. Finally, the proposed model can find bridge and spreader communities, which are helpful for us to identify the role played by each community.