當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

利用 Logarithmic Binning （Log-Binning）方法绘制幂律分布（Power-law Distributions）曲线

發布時間：2024/3/24 编程问答 33 豆豆

生活随笔收集整理的這篇文章主要介紹了利用 Logarithmic Binning （Log-Binning）方法绘制幂律分布（Power-law Distributions）曲线小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

文章目錄

1. 度分布繪制的幾種方法
2. Log-Binning 注意事項
3. 取平均值過程的改進

1. 度分布繪制的幾種方法

復雜網絡節點的度分布是分析網絡屬性的一個組成部分。該過程從獲得 $N_{k}$ 開始，即度數為 $k$ 的節點數。這可以通過直接測量或模型來提供。從 $N_{k}$ 我們計算出 $p_{k}=N_{k}/N$ 。問題是，如何繪制 $p_{k}$ 以最好地提取其屬性。

圖度分布在不同標度坐標下的表示

使用 Log-Log 圖

在無標度網絡中，具有一或兩條鏈路的眾多節點與少數節點共存，其中少數節點為具有數千甚至數百萬鏈路的節點。使用線性 $k$ 軸壓縮無數小 $k$ 區域中的節點，使它們不可見。類似地，由于 $k = 1$ 和大 $k$ 的 $p_{k}$ 可能存在數量級差異，如果我們在線性垂直軸上繪制 $p_{k}$ ，大 $k$ 的值將顯示為零（圖 4.22a）。對數圖的使用避免了這些問題。

我們可以使用 10 次方的對數軸（圖 4.22b），或者我們可以繪制 $log?k\log k$ 函數的 $log?k\log k$ 。請注意， $p_{k}=0$ 或 $k = 0$ 的點不會在 $log?-log?\log \text{-} \log$ 圖上顯示，因為 $log?0=?∞\log0=-\infty$ 。

避免 Linear Binning

最有缺陷的方法（但在文獻中經常出現）是在對數圖上簡單地繪制 $p_{k}=N_{k}/N$ （圖 4.22b）。這稱為線性分箱（Linear Binning），因為每個 $bin\text{bin}$ 具有相同的大小 $Δk=1\Delta k=1$ 。對于無標度網絡，Linear Binning 會在大 $k$ 處產生顯而易見的平臺，由形成水平線的大量數據點組成（圖 4.22b）。這個平臺有一個簡單的解釋：通常我們只有一個高度節點的樣本，因此在高 $k$ 區域中，我們要么有 $N_{k}=0$ （沒有具有 $k$ 度的節點），要么有 $N_{k}=1$ （具有 $k$ 度的單個節點）。

因此，Linear Binning 將提供 $p_{k}=0$ （未在對數圖上顯示）或 $p_{k}=1/N$ （適用于所有 hubs），在 $p_{k}=1/N$ 處生成一個平臺。

這個平臺會影響我們估計度指數 $γ\gamma$ 的能力。例如，如果我們嘗試使用 Linear Binning 對圖 4.22b 中所示的數據擬合冪律，則獲得的 $γ\gamma$ 與實際值 $γ=2.5\gamma =2.5$ 完全不同。原因是在 Linear Binning 下，我們在小 $k$ 的 $bin\text{bin}$ 中有大量節點，這使我們能夠自信地在這種情況下擬合 $p_{k}$ 。在大 $k$ 的 $bin\text{bin}$ 中，我們的節點太少，無法對 $p_{k}$ 進行適當的統計估計。相反，新出現的平臺會使得擬合參數偏離。然而，正是這種高 $k$ 狀態在確定 $γ\gamma$ 中起關鍵作用。增加 $bin\text{bin}$ 大小不會解決這個問題。因此，建議避免對肥尾分布進行 Linear Binning。

使用 Logarithmic Binning

?Logarithmic Binning 糾正了 Linear Binning 的非均勻采樣。對于 Log-Binning，我們讓 $bin\text{bin}$ 大小隨程度增加，確保每個 $bin\text{bin}$ 具有相當數量的節點。例如，我們可以選擇 $bin\text{bin}$ 大小為 $2$ 的倍數，這樣第一個 $bin\text{bin}$ 的大小為 $b_{0}=1$ ，包含所有 $k = 1$ 的節點；第二個大小為 $b_{1}=2$ ，包含度數 $k = 2, 3$ 的節點；第三個 $bin\text{bin}$ 的大小為 $b_{2}=4$ ，包含度數 $k = 4, 5, 6, 7$ 的節點。通過歸納，第 $n$ 個 $bin\text{bin}$ 的大小為 $2^{n-1}$ ，包含度數為 $k=2^{n-1},2^{n-1}+1,...,2^{n}-1$ 的節點。請注意， $bin\text{bin}$ 大小可以隨任意增量增加， $b_{n}=c^{n}$ ，其中 $c > 1$ 。度分布由 $p?k?=Nn/(Nbn)p_{\left \langle k \right \rangle}=N_{n}/\left(Nb_{n} \right)$ 給出，其中 $N_{n}$ 是在大小為 $b_{n}$ 的 $binn\text{bin}_{n}$ 中找到的節點數， $?kn?\left \langle k_{n} \right \rangle$ 是 $binn\text{bin}_{n}$ 中節點的平均度數。

圖 4.22c 顯示了 Logarithmic Binning 的 $p_{k}$ 。請注意，現在擴展到高 $k$ 平臺，其本來在 Linear Binning 下不可見。因此，Logarithmic Binning 也可以從稀有的高度節點中提取有用信息。由于上述操作相當于把每個 $bin\text{bin}$ 中的度的 $p_{k}$ 進行平均，所以最終在高 $k$ 的 $bin\text{bin}$ 中有些 $p_{k}$ 是 0，所以平均之后的值要小于 $p_{k}=1/N$ ，這是要值得注意的。

使用累積分布（Cumulative Distribution）

?從 $p_{k}$ 的尾部提取信息的另一種方法是繪制互補累積分布，
$Pk=∑q=k+1∞pq,(1)P_{k}=\sum^{\infty}_{q=k+1}p_{q},\tag{1}$
這再次增強了高k區域的統計顯著性。如果 $p_{k}$ 遵循冪律 $pk=k?γp_{k}=k^{-\gamma}$ ，則累積分布縮放為
$pk～k?γ+1.(2)p_{k}\sim k^{-\gamma+1}.\tag{2}$
累積分布再次消除了 Linear Binning 觀察到的平臺,并擴展了區域（圖 4.22d），從而可以更準確地估計度指數。

2. Log-Binning 注意事項

當橫坐標并非為離散的變量時，需要先把連續變量粗粒化，然后利用每個格子代替

k

值進行上述操作；

但是 Logarithmic Binning 中，橫坐標取的是線性區間的中間值，而畫圖時為對數區間，所以這個上面可能需要有所商量，即有可能取對數區間最優；

特別值得注意的是，當我們把上述 Log-Binning 之后的區間畫在

log?\log

圖中的時候，其點的橫坐標并非是等間隔均勻分布的，當格子的下標比較大的時候，橫坐標才會逼近等間隔分布。用度分布的例子，證明如下：

Log-Binning 的格子為：
$k=1,k=2,3,k=4,5,6,7,...,k=2n?1,2n?1+1,...,2n?1(3)k=1,k=2,3,k=4,5,6,7,...,k=2^{n-1},2^{n-1}+1,...,2^{n}-1\tag{3}$
平均度 $?kn?\left \langle k_{n} \right \rangle$ 的分布為：
$?kn?=Sn?1+1+Sn2=2n?1?1+1+2n?12=3×2n?2?12(4)\begin{aligned} \left \langle k_{n} \right \rangle&=\frac{S_{n-1}+1+S_{n}}{2}\\\tag{4} &=\frac{2^{n-1}-1+1+2^{n}-1}{2}\\ &=3\times2^{n-2}-\frac{1}{2} \end{aligned}$
當 $n→∞n\rightarrow\infty$ 時， $?kn?\left\langle k_{n} \right\rangle$ 在 $log?\log$ 坐標下的值為：
$?kn?log?=log?(?kn?)=log?(3×2n?2?12)≈log?(3×2n?2)≈(n?2)log?(2)+log?(3)≈nlog?(2)+log?(34)≈nlog?(2)(5)\begin{aligned} \left\langle k_{n} \right\rangle_{\log}&=\log\left( \left\langle k_{n} \tag{5}\right\rangle \right) \\ &=\log\left( 3\times2^{n-2}-\frac{1}{2} \right)\\ &\approx \log\left( 3\times2^{n-2} \right)\\ &\approx (n-2)\log\left( 2 \right)+ \log\left( 3\right)\\ &\approx n\log\left( 2 \right)+ \log\left( \frac{3}{4}\right)\\ &\approx n\log\left( 2 \right) \end{aligned}$

即在 $log?\log$ 坐標下， $?kn?\left\langle k_{n} \right\rangle$ 的間距為 $log?(2)\log(2)$ 。

另外觀察上述推導過程，最終的間距只與選擇的比值 $q$ 有關，即間距為 $log?(q)\log(q)$ 。下面對一般情況下的離散變量進行證明，假設初值 $b_{1}=a_{1}$ ，比值 $q > 1$ ，則前 $n$ 項的求和為：
$Sn=a1(1?qn)1?q(6)S_{n}=\frac{a_{1}(1-q^{n})}{1-q}\tag{6}$
平均度 $?kn?\left \langle k_{n} \right \rangle$ 的分布為：
$?kn?=Sn?1+1+Sn2=(1+q)a1qn?12(q?1)+a11?q+12≈(1+q)a1qn?12(q?1)(7)\begin{aligned} \left \langle k_{n} \right \rangle&=\frac{S_{n-1}+1+S_{n}}{2}\\\tag{7} &=\frac{(1+q)a_{1}q^{n-1}}{2(q-1)}+\frac{a_{1}}{1-q}+\frac{1}{2}\\ &\approx \frac{(1+q)a_{1}q^{n-1}}{2(q-1)} \end{aligned}$

當 $n→∞n\rightarrow\infty$ 時， $?kn?\left\langle k_{n} \right\rangle$ 在 $log?\log$ 坐標下的值為：
$?kn?log?=log?(?kn?)=log?((1+q)a1qn?12(q?1))=log?((q+1)a12(q?1)q)+nlog?(q)≈nlog?(q)(8)\begin{aligned} \left\langle k_{n} \right\rangle_{\log}&=\log\left( \left\langle k_{n} \tag{8}\right\rangle \right)\\ &=\log\left(\frac{(1+q)a_{1}q^{n-1}}{2(q-1)} \right)\\ &=\log(\frac{(q+1)a_{1}}{2(q-1)q})+n\log(q)\\ &\approx n\log(q) \end{aligned}$
證畢。

代碼

%計算log-binning function [edges_exponent,N_hist_exponent]=LogBinning(N_hist,edges,first_bin,exponent_base) %N_hist為數據，edges為橫坐標（其length比N_hist多1），first_bin為橫坐標第一個格子大小； %exponent_base為比值； %edges_exponent為橫坐標，N_hist_exponent為縱坐標值；first_bin=1; exponent_base=2;upper_limit=first_bin; %代表總的格子數； length_edges=length(edges); count_exponent=1; edges_exponent(1)=(edges(upper_limit+1)+edges(1))/2; N_hist_exponent(1)=sum(N_hist(1:upper_limit))/upper_limit; while (upper_limit+exponent_base^count_exponent+1)<=length_edgesupper_limit1=upper_limit+exponent_base^count_exponent;count_exponent=count_exponent+1;edges_exponent(count_exponent)=(edges(upper_limit1+1)+edges(upper_limit+1))/2;N_hist_exponent(count_exponent)=sum(N_hist((upper_limit+1):upper_limit1))/(upper_limit1-upper_limit);upper_limit=upper_limit1; endupper_limit1=upper_limit+exponent_base^count_exponent; count_exponent=count_exponent+1; edges_exponent(count_exponent)=(2*edges(upper_limit+1)+(upper_limit1-upper_limit)*(edges(3)-edges(2)))/2; N_hist_exponent(count_exponent)=sum(N_hist((upper_limit+1):end))/(upper_limit1-upper_limit); upper_limit=upper_limit1;edges_exponent=edges_exponent'; N_hist_exponent=N_hist_exponent'; end

其中作為在 $log?\log$ 橫坐標下的 edges_exponent 值的間隔為：

log10(edges_exponent(2:end))-log10(edges_exponent(1:(end-1)))ans =0.6021 0.3979 0.3424 0.3203 0.3104 0.3056 0.3033

由于其比值選的也是 $2$ ，所以最終的間距逐漸趨近為 $log?(2)=0.30103\log(2)=0.30103$ 。

3. 取平均值過程的改進

如果橫坐標為連續變量，則圖中的前幾個點（從左數）會往上翹起來，并且大部分點相對理論值會偏右（或上）。這是因為，此時由于對連續變量進行 hist 的時候，會取區間的整個數值的平均值，所以當這個區間內的前后有數值上的單調性（如果左高右低），此值會被區間內左側的值拉高，高于區間中間位置的值的大小。解決的辦法是把 hist 的區間數取大，進而減小區間的大小，減小拉高的高度。但是值得注意的是，這個區間也不能取的太小，太小的話可能會因為漲落的原因，使數據點低垂下去，或者翹起來。所以需要根據數據的具體情況進行調整。

其實這也一定程度上顯露了區間位置被選在線性區間中間這個操作的缺點。當我們取橫坐標為 $log?\log$ 之后的值的平均值的時候，可以克服這個缺點：

另外上面點在橫坐標上的分布其實也不均勻。下面對一般情況下的離散變量（連續變量可以通過粗粒化轉化為離散變量）進行證明，假設初值 $b_{1}=a_{1}$ ，比值 $q > 1$ ，則前 $n$ 項的求和為：
$Sn=a1(1?qn)1?q(9)S_{n}=\frac{a_{1}(1-q^{n})}{1-q}\tag{9}$

當 $n→∞n\rightarrow\infty$ ，且 $q > 1$ 時， $?kn?\left\langle k_{n} \right\rangle$ 在 $log?\log$ 坐標下的值為：
$?kn?log=log?(Sn?1)+log?(Sn)2=log?(Sn?1Sn)2=log?(a12(1?qn?1)(1?qn)(1?q)2)2≈log?(a12q2nq(1?q)2)2≈2nlog?(q)+log?(a12q(1?q)2)2≈nlog?(q)+12log?(a12q(1?q)2)≈nlog?(q)(10)\begin{aligned} \left\langle k_{n} \right\rangle_{log}&=\frac{\log(S_{n-1})+\log(S_{n})}{2}\\\tag{10} &=\frac{\log(S_{n-1}S_{n})}{2}\\ &=\frac{\log(\frac{a_{1}^{2}(1-q^{n-1})(1-q^{n})}{(1-q)^{2}})}{2}\\ &\approx \frac{\log(\frac{a_{1}^{2}q^{2n}}{q(1-q)^{2}})}{2}\\ &\approx \frac{2n\log(q)+\log(\frac{a_{1}^{2}}{q(1-q)^{2}})}{2}\\ &\approx n\log(q)+\frac{1}{2}\log(\frac{a_{1}^{2}}{q(1-q)^{2}})\\ &\approx n\log(q)\\ \end{aligned}$
比較之前得到的在線性區間下的結果，當 $n→∞n\rightarrow\infty$ 時，兩者一致。

另外當 $a_{1}$ 較小， $q$ 較大時，點在橫坐標上的分布會比較均勻。

另外注意到：相比等間隔的離散點，把不等間隔取成等間隔的過程，也是一個 Linear-Binning 的過程，所以也會輕微的使得散點向左偏移。待考慮是否可以去除這個取等間隔的步驟？？？即在把不等間隔取成等間隔的過程之后，保留原始的不等間隔橫坐標，在求對數區間的值的時候，利用原始的橫坐標（ $log?\log$ 之后）作為權重來求取平均值。
代碼

%計算log-binning，輸出線性坐標下的橫坐標和縱坐標； function [edges_exponent,N_hist_exponent]=LogBinning(N_hist,edges,first_bin,exponent_base) %N_hist為數據，edges為橫坐標（其length比N_hist多1），first_bin為橫坐標第一個格子大小； %exponent_base為比值； %edges_exponent為橫坐標，N_hist_exponent為縱坐標值；first_bin=1; exponent_base=2;upper_limit=first_bin; %代表總的格子數； length_edges=length(edges); count_exponent=1; edges_exponent(1)=10^((log10(edges(upper_limit+1))+log10(edges(1)))/2); N_hist_exponent(1)=sum(N_hist(1:upper_limit))/upper_limit; while (upper_limit+exponent_base^count_exponent+1)<=length_edgesupper_limit1=upper_limit+exponent_base^count_exponent;count_exponent=count_exponent+1;edges_exponent(count_exponent)=10^((log10(edges(upper_limit1+1))+log10(edges(upper_limit+1)))/2); %注意橫坐標需要取對數坐標下的中間值，求完之后為了防止混淆，再退化為線性坐標；N_hist_exponent(count_exponent)=sum(N_hist((upper_limit+1):upper_limit1))/(upper_limit1-upper_limit);upper_limit=upper_limit1; end% 注意此時超出范圍，需要額外處理； upper_limit1=upper_limit+exponent_base^count_exponent; count_exponent=count_exponent+1; edges_exponent(count_exponent)=10^((log10(edges(upper_limit+1))+log10(edges(upper_limit+1)+(upper_limit1-upper_limit)*(edges(3)-edges(2))))/2); N_hist_exponent(count_exponent)=sum(N_hist((upper_limit+1):end))/(upper_limit1-upper_limit); upper_limit=upper_limit1;edges_exponent=edges_exponent'; N_hist_exponent=N_hist_exponent'; end

另外在初始文獻中，作者是分段使用 Log-Binning 方法的，只是在后段的平臺附近使用，而前段正常，這也是可以借鑒的，畢竟這種方法主要是在平臺段起作用。

參考文獻：

barabasi，network science，chapter4.

Power-law Distributions in Information Science - Making the Case for Logarithmic Binning

Log Binning of Data using matlab

Log binning distribution using python networkx?

??????

總結

以上是生活随笔為你收集整理的利用 Logarithmic Binning （Log-Binning）方法绘制幂律分布（Power-law Distributions）曲线的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。