Popularity and Similarity

01-29

在社會網路中，有一個很有趣的現象，叫做 popular is attractive. 意思是說，如果一個人在某個圈子裡人脈非常廣，那麼新加入這個圈子的人有很大的可能性也會跟這個人成為朋友。然而有另一個很有趣的現象，說的是相似的會有吸引力。玩豆瓣的人會感受的所謂的興趣相似成為好朋友的機率可能要比自己跟一個不相關的網紅成為朋友的概率更大。

所以實際上在一個真實的網路中，流行和相似，決定了新加入一個圈子的人會跟哪些人成為朋友。這樣一個簡單的概念，似乎決定了很多社會規律，甚至很多自然規律。類似的規律在很多的抽象出來的網路裡面都被觀察到了。一個跟我們生活聯繫很緊密的例子是互聯網。互聯網上相互鏈接的頁面，越是被鏈接多的頁面，新出現的鏈接是跟它有關的概率就越大。所以流行就有吸引力。

節點、度和冪律

▲ 網路裡面的節點（node），邊（edge）和度（degree）

很多網路呈現出一個非常神奇的冪律特徵，也就是說節點的度 k 出現的概率是冪律的， $Psim k^{-gamma}$ 。例如互聯網的鏈接[1,2,3]，演員的合作網路（人脈）[3]，甚至電網的分布[3]。

▲ 一些網路的冪律分布。橫軸是網路中節點的度，縱軸是這個度在網路中出現的概率。Barabasi (1999).

流行即吸引

正如一開始討論的，流行可以是吸引的，人脈最廣的人對其它人的吸引力最大。其它的類似的例子，比如寫博客的時候，往往會跟一些非常流行的網站相鏈接，例如百度（Google），知乎，豆瓣，微博等等。

那麼流行即吸引這個現象，跟冪律分布有什麼關係呢？

對於冪律分布，有一個很有名的理論是通過「流行即吸引」這樣的簡單的原則來實現的[2]。Dorogovtsev 等人用一個動態的方法生成網路，發現如果這個生成的方法遵從「流行即吸引」的原則，這個網路就可能成為冪律分布的網路。具體的方法是：

每個節點加入網路的時候，會跟產生 m 條邊，也就是跟 m 個之前的節點相連；
新加入的節點跟之前的節點相連的概率是跟之前節點的度 k 有關的， $P_{mathrm{attractiveness},i}sim k_i + A$ 也就是之前的某個節點 i 吸引新節點與起鏈接的概率是跟這個節點 i 的度線性相關的。這裡 $A$ 代表了一個節點的內稟的吸引力，因為即便它本身沒有鏈接，也會對新節點有 $A$ 的吸引力。

按照這樣的規則生成的網路，可以證明其最後度的分布是冪律的[2]

$begin{equation}nP sim k^{-gamma}nend{equation}$

其中 $gamma$ 是跟 m 和 A 有關的，

$gamma = 2+A/m$

也就是說，流行即吸引會產生簡單的冪律分布，而且參數足夠來調節不同的冪律指數現象。[4]

流行X相似

但是我們前面提到了相似這個很重要的點，即相似也吸引。那麼相似和流行這兩個因素共同作用的結果，可以用來解釋現象么？或者說可以是冪律的分布么？

Papadopoulos 等人在 2012 年的一篇叫做 Popularity versus similarity in growing networks 的文章中使用了「流行X相似」同時起作用的模型。他們發現這樣的模型：

節點的連接可以理解成雙曲空間上的最緊鄰相連；
可以用來解釋冪律分布。

為了展示第一條，作者發明了一個簡單的模型：新節點會去連接「流行乘以相似」的值最小的節點，這樣使得相似可以起到很重要的作用。這樣的說法可能會比較模糊，因為實際上這裡面所謂「流行」的數值小和「相似」數值小，都是指的更加流行和更加相似，只是我們選擇的定義如此奇怪。

作者的這個模型是在一個圓盤上實現的。

圓盤的中心是時間最早的時刻，越往外，時間就是越晚。而且節點是每個一個單位時間就出現的。由於越早出現的網路越容易接受更多的鏈接，所以其實徑向也是用來測量流行程度的。我們把節點 i 的徑向坐標記作 $t_i$ 。
圓盤的角度用來測量相似性。兩個節點之間的角度上越靠近，就越相似。 $theta_{ij}=lvert theta_i - theta_j rvert$ ，其中 $theta_i$ 和 $theta_j$ 是節點 i 和節點 j 的角度值。這個值越小，兩個節點就越相似。

▲ 圓盤上兩個節點之間的角度值之差的絕對值用來測量兩個節點的相似程度。例如上圖中2和3之間的角度更加相近，而2和1之間的角度相差更大，所以我們說。 Papadopoulos et al (2012).

▲ 圓盤上每個點都可以用一組坐標來表示。
所以每個節點可以用坐標 $(t_i,theta_i)$ 來定位。現在有個節點 i 加入到了這個網路中來，如何跟其它的節點產生鏈接呢？現在假定有一個節點 j，如果 $theta_{ij}t_j$ 要小於所有其它的節點，那麼節點 i 和 j 就會相連。如果我們要求每個新加入的節點會跟 m 個節點相連，那麼就一次計算 $theta_{ij}t_j$ ，取最小的 m 個節點與新節點相連。

但是，一個非常奇蹟的事情是，如果我們重新定義徑向坐標的意義，取之前的定義的自然對數：

$r=ln t$

同時，我們說這個圓盤是一個雙曲空間，而不是歐式空間。這樣在圓盤上計算距離的方法就是[6]

$x_{ij} = r_i + r_j + ln(theta_{ij}/2)$

我們把 $r_i$ 這些定義放進去

$x_{ij}=ln(t_i t_j theta_{ij}/2)$

我們會發現之前說的最小化 $t_jtheta_{ij}$ 等價與最小化距離 $x_{ij}$ 。

所以我們現在可以自信的說，新加入的節點會連接在雙曲空間上與其最近的 m 個節點。

▲ 這是雙曲空間上的節點連接最緊鄰的例子。新加入的節點 20 ，連接了節點 8,7,2，因為這些節點是距離它最近的。紅色的區域的邊界其實是一個等距離的邊界，在這條線上的所有的點都是距離節點 20 相同的，紅色內部是小於這個邊界上的距離的點。Papadopoulos et al (2012).

那麼為什麼這樣一個簡單的變換讓大家激動不已呢？在物理上我們知道 Minkowski 空間裡面計算距離，其實就是雙曲空間的距離計算，這樣就讓我們有一些關於宇宙終極規律和網路動力學的相關性的遐想[7]。當然，最重要的原因還是因為這個方法給出了距離計算，是的我們討論網路的時候有了一個更加嚴謹的規則，同時還考慮到這是流行與相似的競爭相互作用結果。

當然作者們也做了數值的模擬，重現了一些冪律分布，解釋了一些現象，這些都是簡單的計算/編程，如下圖。

▲ 來自 https://www.pinterest.com/pin/35043703323744195/

參考文獻

[1] Stefan Bornholdt, Holger Ebel (2000). World-Wide Web scaling exponent from Simons 1955 model

[2] S.N. Dorogovtsev, J.F.F. Mendes, A.N. Samukhin (2000). WWW and Internet models from 1955 till our days and the "popularity is attractive" principle

[3] A.-L. Barabási, & R. Albert (1999). Emergence of Scaling in Random Networks. Science, 286(5439), 509–512.?

[4] Dorogovtsev 等人還發現「流行即吸引」這裡面吸引的程度，僅僅是 $P_{mathrm{attractiveness},i}sim k_i + A$ ，而不能是 $P_{mathrm{attractiveness},i}sim k_i^alpha + A$ , $alpha neq 1$ .

[5] Fragkiskos Papadopoulos, Maksim Kitsak, M. ángeles Serrano, Marián Bogu?á & Dmitri Krioukov (2012). Popularity versus similarity in growing networks. Nature 489, 537–540.

[6] 這個公式其實是針對曲率 K=-4 的。但是整個這個理論與具體的曲率無關。

[7] 其實有篇論文 Krioukov, D., Kitsak, M., Sinkovits, R. S., Rideout, D., Meyer, D., & Bogu?á, M. (2012). Network Cosmology. Scientific Reports, 2, 793.

[8] 題圖來自https://www.pinterest.com/pin/503066220853773369/