對社會網路的抽樣方法

A sampling method for social networks

林鼎鈞(Ting-Chun Lin)

指導教授 ： 吳邦一

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

摘要

現今社會網路的規模，因為Facebook和Twitter等社群網路服務(SNSs)的發展而變得非常巨大，在一個網路中可能有數百萬個甚至數十億的使用者，如果我們用整個網路去做分析的話會變得沒有效率，所以，如何從原圖抽樣出一個好的樣本是很重要的。在這篇論文中，我們檢驗了一些已知的抽樣方法並且提出一個新的方法。

關鍵字

圖形抽樣 ； 演算法 ； 社會網路

並列摘要

Nowadays, the scales of social networks become very huge since the increasing popularity of Social Networking Services (SNSs) such as Facebook and Twitter. There can be millions or even billions users in the network. It would be very inefficient if we use the whole network to analyse. Therefore, how to sample a good subgraph from the original graph is important. In this thesis, we examined several sampling methods and propose a new one.

並列關鍵字

graph sampling ； algorithm ； social networks

參考文獻

[1] Y.-Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong, "Analysis of topological characteristics of huge online social networking services," in Proceedings of the 16th international conference on World Wide Web, 2007, pp. 835-844.

[3] R. Albert, H. Jeong, and A.-L. Barabási, "Internet: Diameter of the world-wide web," Nature, vol. 401, pp. 130-131, 1999.

[4] A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," science, vol. 286, pp. 509-512, 1999.

[6] C. Bennett, "More efficient classification of web content using graph sampling," in Computational Intelligence and Data Mining, 2007. CIDM 2007. IEEE Symposium on, 2007, pp. 485-490.

[8] S. Chib and E. Greenberg, "Understanding the metropolis-hastings algorithm," The American Statistician, vol. 49, pp. 327-335, 1995.