基於強健連結以偵測社會網路上之真實朋友

Detecting Real Friends in a Social Network Based on Strong Links

黃耀霆(Yao-Ting Huang)

指導教授 ： 吳邦一

國立中正大學/工學院/資訊工程學系/碩士(2012年)

摘要

在這篇論文中，我們提出了一個結構分析方法用於偵測社會網路中的真假朋友關係，根據社會科學的平衡理論以及觀察到的使用者行為，我們定義了一個圖形最佳化問題並設計演算法，更重要的是，為了呈現新模型的效用，我們在模擬社會網路的隨機圖上進行一些實驗，由實驗結果可得知我們的新模型是有效的。除此之外，我們還將我們的啟發式演算法應用在社群偵測上，我們利用幾個現實世界的公開資料庫進行實驗測試，根據實驗結果，我們證實了我們提出的方法是有用的。

關鍵字

社會網路分析 ； 演算法 ； 最佳化問題 ； 結構分析 ； 社群偵測

並列摘要

In this thesis, we propose a method of structural analysis for detecting true/false friend links in an Internet social network. By the balance theory in social science and observed user behaviors, we define a graph optimization problem. We examine the computational complexities and develop heuristic algorithms. More importantly, to show the effectiveness of the new model, we perform experiments on random graphs which simulate the user behavior on Internet social networks. We show the precisions/recalls of both true and false edges. The experimental results show that the new model is effective. Besides detecting true/false friend links, we apply our heuristic algorithms to community detection. We experimented on several benchmarks from the real world and show the performance of the proposed method. According to the experimental results, we verify that the proposed method is useful.

並列關鍵字

social network analysis ； algorithm ； optimization problem ； structural analysis ； community detection

參考文獻

[1] D. Aloise, S. Caeri, G. Caporossi, P. Hansen, L. Liberti, S. Perron, and L. Liberti, Column Generation Algorithms for Exact Modularity Maximization in Networks, Physical Review E, 82:046112, 2010.

[3] C. Bron and J. Kerbosch, Algorithm 457: Finding All Cliques of an Undirected Graph, Communications of the ACM, 16(9):575-577, 1973.

[4] S. Caeri, P. Hansen, and L. Liberti, Loops and Multiple Edges in Modularity Maximization of Networks, Physical Review E, 81:046102, 2010.

[5] D. Chen, Y. Fu, and M. Shang, A Fast and Efficient Heuristic Algorithm for Detecting Community Structures in Complex Networks, Physica A: Statistical Mechanics and its Applications, 388(13):2741–2749, 2009.

[6] A. Clauset, M. E. J. Newman, and C. Moore, Finding Community Structure in Very Large Networks, Physical Review E, 70(6):066111, 2004.