閱讀筆記：社交網路長什麼樣？

The Anatomy of the Facebook Social Graph 主要討論的是真實世界的社交網路所構成的無向圖的性質。論文作者使用了來自臉書的數據，包括了大約7.21億的活躍用戶。這裡的活躍用戶是論文作者定義的，指的是在2011年五月的最後28天內有登陸臉書賬號，且有至少一個好友的用戶。該論文的作者主要通過對社交網路圖的圖性質，例如度分布，連通圖大小等，進行計算，來觀察自然圖的性質。作者使用了兩個數據集，一個是全球的，一個是只是美國自身的。

度分布（Degree Distribution）。所謂某個結點的度指的是與該結點相連的邊，在無向圖中，因為邊的連接是雙向的，所有沒有入度和出度的區別，也就是入度等於出度。在社交網路里，一個結點的度數等於其好友數。

首先說結論：社交網路的自然圖也遵從冪定律（常見的自然圖大多有這個性質）。

在左邊的圖中，好友少於20的部分不符合冪定律，原因是臉書會採取各種措施幫助擁有少於20好友的用戶增加好友（例如更頻繁的郵件通知），多於20的沒有了措施。有人擁有多達5000好友（可能5000是好友數上限？）。從統計上來講，大部分用戶的好友數少於200，全球的用戶好友數的中位數是99。

全球範圍內的網路和美國境內的網路的模式很像。

路徑長度（Path Lengths）。這裡的路徑長度，指的是任意兩個結點之間相連的最短路徑的長。論文作者首先找出了大圖裡的所有連通分量，然後對連通分量內的所有的結點對的路徑長度進行了統計，確認了一個事實：在給定一個連通分量里，六度分隔存在的。說通俗一點，所謂的從自己開始經過6個人，能知道世界上所有的人的這個說法的弱化版，是存在於社交網路中的。具體來看看統計：

對於全球用戶來講，92%對關係的存在是在5度以內（隔四個人），99.6%對關係在6度內。關係對的平均長度為4.7，即隔4.7個人即可認識所有的人。

對於美國用戶來講，99.6%對關係在5度以內，99.7%在6度以內，平均為4.3。

這實在是一個amazing的結論。

分量大小（Component Size）。這裡的分量指的是連通分量。所謂連通分量，是指在圖的某個子圖中，任意兩個結點都有至少一條路徑相連。

基本的觀察室，大部分的群體大小都很小，但是大部分人（99.1%的用戶）是在一個大分量里。第二大的分量不過2000人之多。

待續。。。

推薦閱讀：