臉書─小小世界

Facebook - A smaller world

高瑋琳

指導教授 ： 傅恆霖

國立交通大學/理學院/應用數學系暨研究所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00285

摘要

``六度分隔理論''告訴我們：任兩個陌生人之間，平均最多只要透過六個人就可以認識。這世界人口如此地多，人際網路卻是個小世界。隨著網際網路的盛行，社群網路臉書的崛起，人和人的距離似乎又拉近了許多。實驗發現，在臉書上，任兩個陌生人的平均距離最多只需要五步，世界似乎更小了。在這篇論文中，我們提出了一個動態隨機圖模型來模擬臉書，將每一個用戶看成點，好友關係看成邊，試著去刻畫隨機圖在時間很大的時候的樣貌。在模型的建構過程中，我們用不同的機率分佈來加入新的點和邊，和刪去舊有的點和邊，引入優先附加和相對弱者易被淘汰的概念，以符合臉書上的實際狀況。我們發現，這個模型的度分佈(degree distribution)也滿足冪次律(power-law)─小世界網路(small world network)的明顯特徵。因此，我們可以推斷，臉書也是一個小世界。

關鍵字

小世界網路 ； 冪次律 ； 臉書

並列摘要

``Six degree of Separation'' told us: any two individuals, selected randomly from almost anywhere on the planet, can know each other via a chain of average no more than six intermediate acquaintances. There are more tens of millions of people around the world, but the social network is a small world. With the dramatic growth of the World Wide Web and the Internet, even the rise of the social network-Facebook, the distance between two people seems much shorter than before. Through the experiment result, on Facebook, any two individuals are connected in five steps or fewer, on average. The world seems smaller. In this thesis, we construct a dynamic random graph model to simulate Facebook.
We regard each user of Facebook as a vertex and the friendship between two users as an edge, and try to depict the pattern of the random graph as time being approximately infinity. In the process of the construction, we applied different probability distributions to adding new vertices and edges, and deleting existing vertices and edges. Based on the preferential attachment and the idea of the weaker tends to be weeded out, the model seems to conform with Facebook. Furthermore, we prove that the degree distribution satisfies the power-law, a common feature of the small world networks. Therefore, we conclude that Facebook is also a small world.

並列關鍵字

small world ； power law ； facebook

參考文獻

[1] A. L, Barabasi and R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509-512.

degrees of separation. CoRR, abs/1111.4570, 2011.

[3] F. Chung and L. Lu, Coupling online and oine analyses for random

[5] A. Cami, Techniques for analyzing dynamic random graph models of

web-like networks: An overview, Networks 51 (2008) 211-255.