圖數據挖掘：冪律分布和無標度網路
1 冪律分布和指數分布
我們在部落格中《圖數據挖掘（二）：網路的常見度量屬性 》提到，節點度分布\(p(k)\)為關於\(k\)的函數，表示網路中度為\(k\)的節點佔多大比例。我們發現，現實世界許多網路的節點度分布與冪函數乘正比：
\]
比如下圖就是對Flick社交網路中\(p(k)\)的概率分布影像的可視化：
由於對\(y=x^{-\alpha}\)兩邊取對數可以得到\(\log(y)=-\alpha \log(x)\)，因此我們使用原數據在log-log尺度上繪製影像得到：
可以看到此時冪律分布像一條斜率為\(-\alpha\)的直線。事實上，我們可以用該方法快速檢測一個數據集是否服從冪律分布。像與冪律分布\(p(k) \propto \exp (-k)\)和指數分布\(p(k) \propto k^{-\alpha}\)就可以使用取對數的方法進行區分，因為對\(y=f(x)=e^{-x}\)兩邊取對數我們得到的是\(\log(y)=-x\)。
我們繼續看在原始坐標軸下，冪律分布和指數分布的對比圖：
可以看到，當\(x\)值高於某個特定的值後，冪律分布影像會高於指數分布。如果我們在log-log或者半log(log-lin)尺度上繪製影像則可以看到
我們再來看一下現實生活中的冪律分布和其它分布的對比。事實上，航空網路的度分布常常滿足冪律分布；而高速公路網路的度分布則常常滿足泊松分布（指數族分布的一種），其均值為平均度\(\bar{k}\)。它們的對比如下圖所示：
2 冪律分布的數學性質
2.1 重尾分布
如果分布\(p(x)\)對應的互補累計分布函數(complementary cumulative distribution function，CCDF)\(P(X>x)\)滿足：
\]
則我們稱分布\(p(x)\)是重尾分布(heavy tailed distribution)。
冪律分布就是一種典型的重尾分布（就像我們前面所展示的節點度高度傾斜）。但需要注意的事，以下分布不是重尾分布：
- 正態分布：\(p(x)=\frac{1}{\sqrt{2 \pi \sigma}} e^{-\frac{(x-\mu)^2}{2 \sigma^2}}\)
- 指數分布：\(p(x)=\lambda e^{-\lambda x}\)（\(P(X>x)=1-P(X \leq x)=e^{-\lambda x}\)）。
事實上，重尾分布有著不同的變種和形式，包括：長尾分布(long tailed distribution)，齊夫定律(Zipf’s law)，帕累托定律(Pareto law，也就是所謂的「二八法則」)等。
對於重尾分布而言，其概率密度函數\(p(x)\)正比於：
- 冪律分布： \(p(x) \propto x^{-\alpha}\)
- 具有指數截止的冪律分布(power law with exponential cutoff)：\(x^{-\alpha} e^{-\lambda x}\)
- 擴展指數分布(stretched exponential)：\(x^{\beta-1} e^{-\lambda x^\beta}\)
- 對數正態分布(log-normal)：\(\frac{1}{x} \exp \left[-\frac{(\ln x-\mu)^2}{2 \sigma^2}\right]\)
2.2 歸一化常數
接下來我們考慮冪律分布
\]
的歸一化常數\(Z\)應該怎麼取。由於要讓\(p(x)\)是一個概率分布的話則需要滿足：\(\int p(x) d x=1\)。由於\(p(x)\)在\(x \rightarrow 0\)的時候是發散的，我們取一個最小值\(x_m\)，接著我們有：
&1=\int_{x_m}^{\infty} p(x) d x=Z \int_{x_m}^{\infty} x^{-\alpha} d x \\
&=-\frac{Z}{\alpha-1}\left[x^{-\alpha+1}\right]_{x_m}^{\infty}=-\frac{Z}{\alpha-1}\left[\infty^{1-\alpha}-x_m^{1-\alpha}\right]
\end{aligned}
\]
當\(\alpha>1\)時，我們有\(Z=(\alpha-1) x_m^{\alpha-1}\)。於是，可以得到歸一化後的冪律分布形式：
\]
2.3 數學期望
冪律分布隨機變數\(X\)的期望值
&E[X]=\int_{x_m}^{\infty} x p(x) d x=Z \int_{x_m}^{\infty} x^{-\alpha+1} d x \\
&=\frac{Z}{2-\alpha}\left[x^{2-\alpha}\right]_{x_m}^{\infty}=\frac{(\alpha-1) x_m^{\alpha-1}}{-(\alpha-2)}\left[\infty^{2-\alpha}-x_m^{2-\alpha}\right]
\end{aligned}
\]
當\(\alpha>2\)時，我們有
\]
若\(\alpha \leq 2\)，則\(E[X]=\infty\)，若\(\alpha\leq3\)，則\(Var[X]=\infty\)。事實上當方差太大時均值就沒有意義了。
在真實的網路中\(2<\alpha<3\)，所以\(E[X]=\text{const}\)，\(Var[X]=\infty\)。
為了印證我們上面的理論，我們通過實驗模擬當冪律分布的指數\(\alpha\)的取不同值時，從分布中所採的\(n\)個樣本的均值和方差隨著\(n\rightarrow \infty\)的變化情況：
可以看到，和我們上面的理論符合。
3 無標度網路
3.1 隨機和無標度網路的對比
網路度分布遵循冪律分布的網路我們稱為無標度(scale-free)網路（也稱無尺度網路)。所謂無標度（Scale-Free），其實來源於統計物理學裡的相轉移理。網路一階矩是平均度，二階矩是度的方差。我們在部落格《圖數據挖掘：Erdos-Renyi隨機圖的生成方式及其特性》中說過，ER隨機網路的平均度\(\bar{k}\)與度方差\(\sigma^2\)都是可以估計的，這就是所謂「有尺度」。但正如我們前面所分析的，在冪律分布網路中，方差和期望都可能不存在，這也是Barabási等人將其稱為「無尺度」的原因[2][3]。
我們下面展示了隨機網路（Erdos-Eenyi隨機圖）和無標度網路的對比：
3.2 網路的彈性
網路的彈性(resilience)意為網路對攻擊的抵抗能力，而這可以通過網路的一些度量屬性隨攻擊的變化來體現。
節點的移除方式包括兩種：
- 隨機事故(random failure): 均勻隨機地移除節點
- 針對性攻擊(targeted attack): 按照度的降序來移除節點。
網路的彈性分析對互聯網的魯棒性和流行病學都非常重要。接下來我們就來看幾種經典網路類型的彈性分析實驗。我們採取的度量屬性包括：
- 在巨大連通分量（gaint connected component）中的節點所佔的比例
- 最大連通分量中的節點之間的平均路徑長度。
可以看到，無標度網路對隨機攻擊具有彈性，但是對針對性攻擊敏感：
接下來的實驗展示了對於無標度網路而言，如需讓巨連通分量\(S\)消失，有多大比例的隨機節點必須要被移除。
\(\gamma<3\)的無限大的無標度網路在隨機攻擊下永遠不會被解體。
下面是無標度網路和隨機網路的平均路徑長度在針對性攻擊和隨機攻擊下的變化圖：
可見無標度網路對於隨機事故是有彈性的，而\(G_{np}\)對於針對性攻擊有著更好的彈性。
在現實網路中的彈性試驗情況如下圖所示(來源於[5]）：
對上述影像進行放大的結果如下圖所示，圖中E是指\(G_{np}\)而SF是指scale-free，橫坐標表示百分之多少的節點被移除。這裡我們可以看到針對性攻擊是怎樣快速地讓網路變得不連通的。
3.3 優先連接模型和富者更富現象
最後，我們來看冪律分布形成的原因。而這需要從整個網路的形成過程來思考。
我們設節點以順序\(1,2,\cdots, n\)到達。在第\(j\)步，一個新的節點\(j\)到達了並創建了\(m\)個出鏈接(out-links)，則節點\(j\)鏈接到之前的節點\(i\)(\(i<j\))的概率正比於\(i\)的度\(d_i\)：
\]
這被稱之為擇優鏈接模型(Preferential attachment)[3]，或富者更富現象，就是指新來的節點更傾向於去鏈接度已經很高的節點。而冪律就是從「富者更富」（累計優勢）中產生。現實中中常見的例子就是在論文引用中，論文新增的引用量和它已經有的引用量成正比（部落格文章的點贊也是這個道理，所以如果你看到我這篇文章贊同量很少，不要猶豫幫我點個贊啦o(╥﹏╥)o）。
為了推導冪律分布的形式，我們分析下列模型：節點以順序\(1,2,3\cdots,n\)到達。當節點\(j\)被創建時它用一個鏈接指向一個更早的節點\(i\)，節點\(i\)是按以下規則選擇的：
- \(j\)以概率\(p\)從更早的節點中均勻隨機選擇\(i\)。
- \(j\)以概率\(1-p\)鏈接到節點\(l\)，其中\(l\)被選擇的概率正比於\(d_l\)(\(l\)的入度)。
注意，因為我們的圖是有向圖，每個節點的出度都為\(1\)。
則在我們上述模型產生的網路中，入度為\(k\)的節點所佔的比例滿足：
\]
這裡\(q=1-p\)。這樣，我們就得到了指數\(\alpha=1+\frac{1}{1-p}\)的冪律度分布。
參考
- [1] Broder A, Kumar R, Maghoul F, et al. Graph structure in the web[J]. Computer networks, 2000, 33(1-6): 309-320.
- [2] wiki：無標度網路
- [3] Barabási A L, Albert R. Emergence of scaling in random networks[J]. science, 1999, 286(5439): 509-512.
- [4] Albert R, Jeong H, Barabási A L. Error and attack tolerance of complex networks[J]. nature, 2000, 406(6794): 378-382.
- [5] //web.stanford.edu/class/cs224w/
- [6] Easley D, Kleinberg J. Networks, crowds, and markets: Reasoning about a highly connected world[M]. Cambridge university press, 2010.
- [7] Barabási A L. Network science[J]. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2013, 371(1987): 20120375.
