圖數據挖掘：冪律分佈和無標度網絡
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.
