交通地理學與網路科學/網路形成

網路形成模型

本節將討論網路形成模型，也稱為“生成網路模型”。這些模型解釋了為什麼網路應該具有某些預先確定的引數（例如冪律度分佈）。也就是說，它們模擬建立網路的機制，並探索某些假設的生成機制所產生的網路結構。“如果結構類似於我們在現實世界中觀察到的網路結構，它表明 - 儘管沒有證明 - 類似的生成機制可能在現實網路中發揮作用。”(Newman，2010)

優先連線

觀察到許多網路的度分佈近似遵循冪律，至少在分佈的尾部是這樣。在 1970 年代，Derek Price 首次提出了一個解釋這種現象的網路形成模型，該模型受到了經濟學家 Herbert Simon 和統計學家 Udny Yule（Yule 過程）作品的啟發。Price 擴充套件了 Simon 對“富者愈富”（也稱為冪律分佈）在網路背景下的數學解釋，將其稱為“累積優勢”（在 1999 年由 Barabasi 和 Albert 稱為優先連線）。

Price 模型

Price 特別將此過程應用於引文網路模型。在這個模型中，論文不斷出版（逐個新增），但並不一定以恆定的速度出版，較新的論文引用較舊的論文。該網路中的邊是定向的，可以建立但永遠不會銷燬。Price 模型的核心假設是，新出現的論文以與已引用次數成正比的機率引用以前出現的論文，再加上一個常數 a，其中 a>0。考慮一個 Price 模型網路，其中 $q_{i}$ 表示頂點 i 的入度。現在假設一個新頂點被新增到網路中。那麼引用特定頂點（例如 *i*）的機率與 $q_{i}+a$ 成正比。對上述項進行歸一化，我們得到由新引入的頂點引用特定頂點（例如 *i*）的機率為：

$p_{i}={\frac {q_{i}+a}{\sum (q_{i}+a)}}$

如果給定論文的平均引用次數為 c，根據網路屬性，具有一定的方差，那麼隨著網路規模變得非常大，網路中具有入度 q 的頂點的比例變為：(Newman，2010 pp- 490-494)

$p_{q}={\frac {B(q+a,2+a/c)}{B(a,1+a/c)}}$

其中

q=入度

a=常數

c=網路的平均出度（或平均參考文獻大小）

其中 Beta 函式定義為 $B(x,y)={\frac {\Gamma (x)\Gamma (y)}{\Gamma (x+y)}}$

而 Gamma 函式為 $\Gamma (x)=\int _{0}^{\infty }t^{x-1}e^{-t}\,dt$

此外，Beta 函式對於 x 的大值會以冪律下降，指數為 y。應用此公式，我們發現對於 q 的大值 (q>>a)，度分佈變為

$p_{q}\sim q^{-(2+{\frac {a}{c}})}$

因此，Price 對引文網路的模型產生了具有冪律尾部的度分佈。更一般地說，每篇論文可以被視為一個節點，每個引文是一個連結。這裡，連結以與到達該節點的連結數量成正比的機率新增到現有節點中。

Barabasi 和 Albert 模型

巴拉巴西-阿爾伯特模型在 1990 年代獨立開發，是當今最知名的生成網路模型。與普萊斯模型類似，頂點被逐個新增到一個不斷增長的網路中，並連線到現有頂點。然而，這些連線是無向的，並且每個頂點所做的連線數量恰好為 c（與普萊斯模型不同，普萊斯模型允許 c 在每次步驟中發生變化）。連線的比例與無向度 k 成正比。透過將巴拉巴西-阿爾伯特模型視為普萊斯模型的一個特例，紐曼在 2010 年證明了：

$p_{k}={\frac {2c(c+1)}{k(k+1)(k+2)}}$

對於 k ≥ c

其中

c=每個頂點所做的連線數

k=頂點的度數

$p_{k}$ 是具有 k 度的頂點的比例。

在這種情況下，當 k 變得非常大時，度數分佈變為：

$p_{k}\sim k^{-3}$

優先依附模型的擴充套件和進一步特性

模型屬性/擴充套件	直觀原理	結果分佈	貢獻者
加入建立時間	透過優先依附，較早的頂點將有更多時間獲得連結。	包含領先的代數因子，不遵循冪律分佈	(Dorogovsev, Mendes, & Samukhim, 2000)
入射元件的大小	從頂點 i 可以透過遵循有向路徑到達的頂點集的分佈	對於元件大小 << 網路大小，遵循冪律分佈	(Newman, 2010)
增加額外邊	在兩個現有頂點之間新增連線	冪律分佈	(Krapivsky, Rodgers, & Redner, 2001)
刪除邊	考慮反向優先依附，度數越高，越有可能失去一條邊	到一定程度上的冪律分佈，然後是拉伸指數	(Moore, Ghoshal, & Newman, 2006)
非線性優先依附	考慮頂點度的非線性依附過程，而不是線性過程	拉伸指數	(Krapivsky, Redner, & Leyvraz, Connectivity of Growing Random Networks, 2000)
質量或吸引力不同的頂點	質量和吸引力被納入依附過程	取決於“適應度”值的分佈	(Bianconi & Barabasi, 2001)

思考問題

還有什麼其他網路的形成可以用優先依附來準確描述（考慮普萊斯模型或巴拉巴西-阿爾伯特模型）？

線上模擬

NetLogo 模型庫：優先依附

頂點複製模型

雖然優先處理提供了對冪律度數分佈的合理解釋，但它並不是網路增長的唯一方法（紐曼，2010）。假設新新增的頂點複製了現有頂點的一部分連線，而其餘部分由其他現有頂點填充（例如，一篇新論文複製了現有論文的一部分參考文獻）。正如紐曼在 2010 年分析的那樣，在這個模型下，大型網路的度數分佈將漸近地遵循冪律分佈（紐曼，2010）。

網路最佳化模型

以前的網路結構主要基於連續的隨機過程，這些過程對正在建立的大規模結構視而不見。一種可能更適合交通網路的網路增長機制是結構最佳化。在這種情況下，最佳化涉及旅行時間和成本之間的權衡。這種機制最簡單的形式之一是由費雷爾·坎喬和索爾在 2003 年開發的。該模型試圖最小化以下質量函式（費雷爾·坎喬和索爾，2003）

$E(e,l)=\lambda e+(1-\lambda )l$

其中

e=網路中的邊數

l=頂點對之間的平均測地距離（不滿意度量）

λ=範圍為 0≤λ≤1 的引數

在這個模型中，維護網路的成本用變數 m 表示。這與說運營航空公司的成本與它運營的航線數量成正比是一樣的，例如。以航空公司為例，變數 l 將是完成一次旅程所需的平均航段數量。這顯然是對複雜網路的簡化。引數 λ 在具有儘可能少邊的網路和完全連線的網路之間提供平衡。從該模型可以看出，透過將中等權重置於 λ 上，l 被最小化，最優結果是星形圖。這解釋了為什麼中心樞紐系統如此高效的簡單原因（紐曼，2010）。事實證明，非星形圖解僅在以下情況下出現： $\lambda <{\frac {2}{n^{2}+2}}$ .

如費雷爾·坎喬和索爾所確定的，該模型的度數分佈隨著 λ 值的變化從指數分佈到冪律分佈不等。這僅針對區域性最小值提出。

Gastner 和紐曼在 2006 年透過考慮旅程的航段數量以及所走過的地理距離，對費雷爾·坎喬和索爾提出的模型進行了概括（紐曼，2010）。術語 l 被 t 代替，其中 t=u+vr（紐曼，2010）。在這個表示式中，u 和 v 是與連結上的固定時間和速度（1/速度）相關的常數，r 是在連結上行駛的距離。例如，u 可以被認為是機場的登機、等待、滑行等時間，速度是飛行過程中平均速度的倒數。這將空間方面引入模型，而以前只考慮了拓撲考慮因素。然而，該模型也僅產生數值結果。

思考問題

透過改變 Gastner 和 Newman 模型中 u 和 v 的值，可以對所得網路的幾何形狀得出什麼假設？

進一步閱讀

網路形成模型綜述：穩定性和效率作者：Matthew O. Jackson

計量學和其他累積優勢過程的通用理論作者：Derek de S. Price

運輸網路中層次結構的出現作者：Bhanu M. Yerra 和 David M. Levinson

另請參見

參考文獻

Barabasi, A.-L. 和 Albert, R. (1999). 隨機網路中縮放的出現。科學，286，509-512。

Bianconi, G. 和 Barabasi, A.-L. (2001). 複雜網路中的玻色-愛因斯坦凝聚。物理評論快報，86，5632-5635。

Dorogovsev, S. N.，Mendes, J. F. 和 Samukhim, A. N. (2000). 具有優先連線的增長網路的結構。物理評論快報，85，4633-4636。

Ferrer i Cancho, R. 和 Sole, R. V. (2003). 複雜網路的統計力學 (第 625 卷)。(R. Pastor-Satorras、M. Rubi 和 A. Diaz-Guilera 編輯) 柏林：施普林格出版社。

Gastner, M. T. 和 Newman, M. E. (2006). 空間分佈網路的最佳設計。物理評論 E，74，016117。

Jackson, M. O. (2005). 網路形成模型綜述：穩定性和效率。在 G. Demange 和 M. Wooders (編輯) 中，經濟學中的群體形成：網路、俱樂部和聯盟 (第 1 章)。劍橋：劍橋大學出版社。

Krapivsky, P. L.，Redner, S. 和 Leyvraz, F. (2000). 增長隨機網路的連線性。物理評論快報，85，4629-4632。

Krapivsky, P. L.，Rodgers, G. J. 和 Redner, S. (2001). 增長網路的度分佈。物理評論快報，86，5401-5404。

Moore, C.，Ghoshal, G. 和 Newman, M. E. (2006). 節點新增和刪除的演化網路模型的精確解。物理評論 E，74 (3)，036121。

Newman, M. E. (2010). 網路：導論。紐約州紐約：牛津大學出版社。

Price, D. d. (1976). 計量學和其他累積優勢過程的通用理論。美國資訊科學學會期刊，27，292-306。

Rodrigue, J.-P.，Comtois, C. 和 Slack, B. (2009). 運輸系統地理學 (第二版)。紐約州紐約：勞特里奇出版社。

Simon, H. A. (1955). 關於一類偏態分佈函式。生物統計學，42 (3/4)，425-440。

Wilensky, U. (2005). NetLogo 優先連線模型。http://ccl.northwestern.edu/netlogo/models/PreferentialAttachment. 連線學習與計算機建模中心，西北大學，伊利諾伊州埃文斯頓。

Wilensky, U. (1999). NetLogo。http://ccl.northwestern.edu/netlogo/. 連線學習與計算機建模中心，西北大學，伊利諾伊州埃文斯頓。

Yerra, B. M. 和 Levinson, D. M. (2005). 運輸網路中層次結構的出現。區域科學年鑑，39，541-553。