About scale-free的相關簡報
http://enews.kmu.edu.tw/2004-04-06/topics3.htm
蛋白質交互作用
蛋白質交互作用也可以用網路的觀念來分析,不僅可以直接在 2 維上觀察,並可用網路的系統分析來探討多達數千交互作用的機制。 Barabasi 研究群針對 1870 個酵母菌蛋白質所形成的 2240 個蛋白質交互作用網路進行分析,發現一個結點連接到其他結點的機率分佈呈 power-law 分佈 ( 機率 P( 連接數 )=k -r , k= 連接數, r=2.2~2.4) ,這種網路稱為 scale-free 網路。同研究群在另一個相關研究中,針對在 WIT(http://wit.mcs.anl.gov/WIT2/) 中 43 個物種的代謝途徑網路分析也發現,儘管所分析的物種涵蓋三個生物界,而且代謝途徑的組成份子不同,但它們的網路特性都是具有 scale free 特性。 scale-free 網路有別於指數 (exponential) 網路,針對每個結點的網路連接數來說,後者是非常平均,通常每個結點都有類似的連接數 ( 發現一個結點連接到其他結點的機率分佈呈近似 Poisson 分佈,機率 P( 連接數 )=e -(k-<k>) , k= 連接數, <k>=k 的平均數 ) ,而前者網路中擁有少連接的結點較多,而擁有較多連接的結點數依 power law 減少。
exponential 網路:是一種均質 (homogeneous) 網路,每個結點均勻地散亂連結。
scale-free 網路:為異質 (heterogeneous) 網路,在這種網路中,可以觀察到少數結點擔任樞紐 (hub) 的角色, hub 與很多結點相連接,而這些 hub 又互相彼此連接。如果隨機去除 scale-free 網路的結點,網路的整體性幾乎不會受到影響,這表示錯誤容忍度 (error tolerance) 很高,但是選擇性地去除 hub ,則網路立刻破碎成不相連接的小網路,這表示脆弱性 (fragility) 高。
http://scc.bookzone.com.tw/sccd/news.asp?ser=336
新聞來源:SciScape.org
電腦病毒在網路上的傳播方式
過去科學家錯認電腦病毒以類似生物病毒的方式散佈。然而一篇剛發表的研究報告透露,網際網路結構上的弱點導致電腦病毒傳染並不像生物病毒傳播一樣必須超過一個最低門檻數目,此現象會讓網路非常容易遭受病毒的攻擊。
西班牙Politecnica de Catalunya大學的物理學家 Pastor Satorrass與其合作夥伴曾利用一個研究病毒感染的標準數學模式來模擬一般病毒的傳播,結果顯示受病毒感染的個體數目要超過一個最低門檻,否則病毒會自然的消失;然而將此模式應用於無尺度(scale-free)的電腦網路,發現要產生傳染的最低門檻數目並不存在,電腦病毒即使以非常緩慢的速度傳播,在網路上依然可以倖存。
原因在於電腦網路屬於無尺度的網路結構,在這種網路結構裡面的許多節點,其與其他節點的連結數目並不具有一個平均值,不若格狀網路結構,每個節點都與周遭四個節點連結,至於隨意式(random) 網路結構裡的所有節點,雖然可以任意連結,但仍能以統計方式計算出節點的平均連結值,隨意式網路的節點其節點連結數目會大於平均連結值的機會很低。
無尺度網路中的部份節點,會以較高的數目進行連結,大部分的節點則只以低數目連結,﹝例如學校某個研究室內的電腦只與一部電腦連接,而電腦中心一部伺服器主機則連接了近百部電腦﹞,而且遠端節點之間具有許多的捷徑,所以相距甚遠的電子郵件伺服器憑著幾個跳躍就完成連接,由於上述的電腦網路結構特徵,讓網路非常容易遭受病毒的攻擊。
原始論文: Romualdo Pastor-Satorras and Alessandro Vespignani, Epidemic Spreading in Scale-Free Networks, Physical Review Letters, pp. 3200-3203, Vol. 86, <date month="4" day="2" year="2001">April 2, 2001</date>.
e-戰爭
為了克服隨機性的故障,網際網路和WWW付出許多代價來提升網路的穩健性。然而, 一群物理學家指出,這樣的網路架構雖然具有高度的隨機錯誤容忍性,但對於有計劃的,智慧型的攻擊卻顯得相當的脆弱。
對於工業國家而言,一種新式的游擊戰正在成形,那就是 e-war:當通訊網路被癱瘓時, 國家的經濟幾乎瞬間就陷入停擺。對於越依賴電子通訊的國家, 這個問題就越值得重視。
在 1960 年代,匈牙利數學家 Paul Erdos 探討指數式架構(exponential structure)。 指數式架構的特性是:大多數節點的連接數目大致相同,即具有同質性 (homogenous),只有少數節點連接數目較少。如城市與城市之間的道路連結就是屬於這種架構。
在印弟安那州 Notre Dame 大學,以 Barabasi 為首的團隊指出,至今還有一種網絡架構被忽視,那就是 scale-free 架構。這種架構的特性就是:大多數的節點只與其它一兩個節點相連結,但有少數節點卻被大量的連結,即非同質性 (inhomogenous)。現行之網際網路,空中交通,WWW 即屬於這類架構。
這兩種架構對於失效的容忍度有相當大的差異. Barabasi 團隊指出當連接開始隨機失效時,在指數式架構中,任意兩點間的最短距離被破壞,較長的迂迴通路開始增加。但對 scale-free 架構而言,既使有二十分之一的連接被破壞,大多數節點還是可以經由最短距離達到目的地。然而。如果有人有計劃的破壞具有大量連接的節點時,不少區域將被孤立,無法經由任何通路與其它節點聯繫。因此,預防關鍵節點的駭客入侵,就顯得格外重要。
論文出處:
Albert, R., Jeong, H. & Barabási, A.-L. Error and attack tolerance of complex networks. Nature 406, 378-382 (2000). 本人閱讀心得^0^: 我認為無尺度網路是接近random但又不是全然random的狀態,因為除了整體的Network必定是動態的之外,個體間的互動行為也是具有一定的群聚及連結現象,如文中提到的Hub和Authority,這樣異質的特徵如果以社會學的觀點解釋,local角度以下的個體間其實是具有某種自由意識的偏好,因而造成了社群的形成。 我相信scale-free的網路是具有小世界的現象的,因為正如老師課堂上曾強調的:具有衍生群落,和允許捷徑的特性發生時,Small World便會發生,這也是網路上的動態學研究上的一大突破。 正因這樣具有普遍性的一個現象被闡述後,我們逐漸可以感受到,越來越多的domain皆試圖證明其是否具有Small World現象,而答案也有幾乎都是肯定的,從電腦病毒的傳播、生物體內神經元的傳播、電力系統的連鎖反應、6個人的小世界實驗等等。 當然,除了普遍性的證明外,探討其中連結發生的因素和key point也是非常重要的,這對於有效的預防或抑制一些有害事件的發生會有很大的幫助,如SARS、流行性感冒等傳染性疾病傳播的模式、電腦病毒,和不斷電系統的設計。
Previous in This Category: 複雜電網的大停電事故研究綜述 Next in This Category: 弱連結(Weak Ties)

Sealed (Dec 9)
Only members can post a comment, Login first