February 28, 2005

Small World概念說明

Small World
SmallWorld一詞最早出現在1967年由哈佛大學社會心理學家Stanley Milgram所提出。在1998年,Watts與Strogatz提出了介於規律與隨機之間的Small World模型,這是以規律網路為基礎,以機率P來重接(rewire)每一條線,當p=0時,即為最初的規律網路;當p=1,則為隨機網路,介於之間的,即為Small World,示意圖如下:

而建構WS的Small World模型,方法如下:
1.先建構一個1-lattice規律網路,其中每個節點皆具有k個連線(degree),與左右節點相連結。
2.以機率P來移除節點之間的連線。若有移除(v, v'),則再以隨機機率連接到尚未與該節點(v)有連線(v'')的任一節點。

具備k=4的1-lattice規律網路,重接線(rewire)示意圖
3.所有節點重複步驟2一次

而Small World與規律網路及隨機網路最大的不同,在於Small World它具有以下的特性:
1.較短的平均最短距離L:因為Small World在重接線時,所建立的連結會是捷徑,因此可以大幅縮短平均距離。
2.較高的叢集度C:因為Small World在重接線時,會保有部份原先規律網路的關係,使得叢集度的値不會下降的太快。


參考資料:具有Small World與Scale Free特性的網路通訊模型, 蕭炳南, 淡江大學資訊工程研究所碩士論文, 民國92年5月。

0推薦此文章
Today's Visitors: 0 Total Visitors: 8
[Trackback URL]

Reply
  • 1樓

    1樓搶頭香

    喔喔 這是有序到隨機的圖形喔
    老大財務管理上課有稍微提到混沌跟這很像
    ...其實我覺得是同一件事情啦

  • cp294879 at March 2, 2005 09:57 PM comment | prosecute
Post A Comment









Yes No



Please input the magic number:

( Prevent the annoy garbage messages )
( What if you cannot see the numbers? )
Please input the magic number

誰來收藏
Loading ...
unlog_NVPO 0