樹的異速標度律

出自集智百科
跳轉到: 導覽搜尋
樹的實例,節點中的數字為Ai,旁邊的數字為Ci

所謂樹的異速標度律是指Ci和Ai之間的冪律關係:


C_i=cA_i^{\eta}

其中Ai是指以任意節點i為根的子樹所包含的節點的個數,而Ci則是指該子樹上所有節點的Aj之和,即:


C_i=\sum_{j\in Tree_i}A_j

其中Treei表示以i為根的子樹。c為一常數,η為異速標度律指數,它表示該樹的垂直化程度。若整個樹越扁平,則η指數越小,反之η越大。

右圖展示了一棵樹的實例,每個節點的Ai寫在了節點中,而Ci則寫到了每個節點的旁邊。


目錄

鏈和星狀結構

為了展示η指數與樹的扁平化程度之間的關係。我們來看兩個極端的例子,一個是星型的網路,它是一種極端的扁平化結構,另外一個是一條鏈,它是一種極端的垂直的結構[1]

Chain-star.PNG

假設樹中的節點總數就是N,對於左圖鏈狀結構來說,從尾端數第i個節點的:


A_i=i

該節點的Ci為:


C_i=\sum_{j=1}^i A_j=\sum_{j=1}^ij=\frac{j(j+1)}{2}=\frac{A_i(A_i+1)}{2}\sim A_i^2

因此,鏈狀網路的異速標度律指數為2。而對於星型節點來說,所有葉節點的Ai=Ci=1,但是樹根的

A_i=N

而:

C_i=N+1\times N=2N=2A_i\sim A_i

所以,對於星形樹來說,異速標度律指數η=1。對於更一般的樹,它一定介於完全的鏈狀結構和星型結構之間,因此冪律指數η就介於1和2之間。

生成樹的異速標度律

Frank和Murrell等人更進一步地探索了樹狀結構與異速標度律指數之間的關係[2]。首先,它們構建了一個簡單的隨機生成樹模型,該模型模擬了樹的隨機生長。該模型有兩個參數β和θ,它們控制了整個樹的形狀。β控制的是與根節點直接相連的節點佔總節點數的比例,θ控制的是樹的平均深度。

首先,讓βN個節點附著在根節點上,形成第一層節點; 然後,在每一時刻,就會有一個節點加入該樹狀結構中,其中這個新加節點j會隨機地附著在某一個該樹上的節點i上作為i的子節點,那麼,附著在i上的概率由i所在樹的深度決定,即按照概率:


P_{ij}=\frac{t_i^{-\theta}}{\sum_{k\in Tree}t_k^{-\theta}}

其中tk表示k節點所在的深度。也就是說j會優先附著在ti較大的節點上。如果θ越大,則j更偏好離根較近的節點,反之則更傾向於附著在較深的節點上。 所以如果θ越大,β越小,就會得到越深的樹。

下面,我們來看兩棵由模型生成的樹(β相同,都為0.1):

TreeExample.PNG

接下來,我們就可以變換不同的θ和β的組合而創造不同的樹結構,並計算出這些樹的η數值[2]

Spanningtreeallometry.PNG

這是2張等高線圖,其中橫坐標和縱坐標分別為θ和β,等高線標示了η(上)和平均路徑長度(下,也就是樹的平均深度)。可以看出,隨著θ的升高,η在變小,同時平均路徑長度在變小,這說明樹在變得不斷地扁平。同時,隨著β的升高,η和平均路徑長度也在變小。由此可以看出,實際上η和平均路徑長度是正相關的,如下圖[2]

Meanlengthandeta.PNG

η的含義

在文章[3][1]中,作者將η解釋為輸運樹的效率,其中輸運效率是指從源(根)到所有節點的平均路徑長度。因此,路徑越短,整個樹越有效率。

如果從扁平化和垂直化的角度來說,η也可以理解為網路的集中性程度。如果將整個樹理解為一個公司的組織架構,那麼η越大,結構越垂直化,因此權利越集中在樹的上層,反過來,樹狀結構越扁平,權利越分散。

參考文獻

  1. 1.0 1.1 Garlaschelli, Diego; Caldarelli, Guido; Pietronero, Luciano (2003). "Universal scaling relations in food webs". Nature 423: 165-168.
  2. 2.0 2.1 2.2 Frank, F.; Murrell, D. (2005). "A simple explanation for universal scaling rela- tions in food webs". Ecology 86: 325-3263.
  3. Banavar, J.; Rinaldo, A. (1932). "Size and form in efficient transportation networks". Nature 399: 130-132.


相關WIKI

流網路的異速標度律

複雜網路

個人工具
名字空間
動作
導覽
工具箱