小世界理論 (六度分隔).

Presentation on theme: "小世界理論 (六度分隔)."— Presentation transcript:

1 小世界理論 (六度分隔)

2 華茲與史楚蓋茲 1998 企圖理解人際關係世界裡的謎團 螢火蟲一致的閃光 每一隻螢火蟲如何能預知閃光? 解開小世界的奧秘

3 米爾格蘭(Milgram) 1960 心理學家 米爾格蘭 描繪人際網路結構 在堪薩斯州隨機選出一些人寄信給他們
信中要求轉寄給他在波士頓的一位股票經紀人朋友，但是沒有給他地址 大多數信件到了他朋友手中，沒有經過多次轉寄，轉寄約六次 Six degrees of separation (六度分隔) 在地球上，人與人之間只相隔六個人

4 六度分隔

5

6 凱文•貝肯的神諭 凱文•貝肯的作品表 請問總統先生 Frost/ Nixon （2008）
交錯效應 The Air I Breathe （2007） 非法制裁 Death Sentence （2007） 開往幸福的列車 Rails & Ties （2007） 赤裸真相 Where the Truth Lies （2005） 神秘河流 Mystic River （2003） 步步危機 Trapped （2002） 家有跳狗 My Dog Skip （2000） 透明人 Hollow Man （2000） 靈異駭客 Stir of Echoes （1999）

7 凱文•貝肯的神諭 與凱文•貝肯的連結數是 2.896 影劇圈是人際關係網路的縮影 電影演員相距連結不超過 6 影劇圈
Elisabeth Shue

8 影劇圈

9 電影演員幾度分隔? 布蘭登 費雪 Brendan Fraser 克莉絲汀 史都華 Kristen Stewart
暮光之城 Twilight 2010 墨水心 Inkheart 2008 布蘭登 費雪 Brendan Fraser 克莉絲汀 史都華 Kristen Stewart   

10 The Oracle of Bacon

11 Brendan Fraser to Kristen Stewart

12 電影演員幾度分隔? 亞曼達 塞佛瑞 Amanda Seyfried 布蘭登 費雪 Brendan Fraser
墨水心 Inkheart 2008 最後一封情書 Dear John 2010 布蘭登 費雪 Brendan Fraser 亞曼達 塞佛瑞 Amanda Seyfried    

13 Brendan Fraser to Amanda Seyfried

14 電影演員幾度分隔? 史蒂芬 杜夫 Stephen Dorff 布蘭登 費雪 Brendan Fraser
頭號公敵 Public Enemies 2009 墨水心 Inkheart 2008 布蘭登 費雪 Brendan Fraser 史蒂芬 杜夫 Stephen Dorff

15 Stephen Dorff to Brendan Fraser

16 電影演員幾度分隔? 莎拉 潔西 卡帕克 Sarah Jessica Parker 麥特 戴蒙 Matt Damon
慾望城市2 Sex and The City       神鬼認證 The Bourne Ultimatum 2007

17 Sarah Jessica Parker to Matt Damon

18 習題 統計下列十組電影演員分隔度平均是多少? Michelle Rodriguez 蜜雪兒 羅莉葛茲 阿凡達 Avatar （2009）
Jason Lee 傑森 李 鼠來寶 Alvin and The Chipmunks （2007） Sanaa Lathan 莎娜 拉森 異形戰場 Alien Vs. Predator （2004） Dennis Quaid 丹尼斯奎德 明天過後 The Day After Tomorrow （2004） Emmanuelle Seigner 艾曼紐 辛葛娜 潛水鐘與蝴蝶 Diving Bell And Butterfly （2007） Anne Hathaway 安 海瑟薇 穿著Prada的惡魔 The Devil Wears Prada （2006） Maggie Q 終極警探4 Die Hard 4 （2007） Audrey Tautou 奧黛莉 朵杜 達文西密碼 Da Vinci Code （2006） Michelle Pfeiffer 蜜雪兒 菲佛 情不自禁愛上你 （2009） Dennis Franz 丹尼斯 法蘭茲 Ｘ情人 City of Angels （1998）

19 Michelle Rodriguez to Sanaa Lathan
Jason Lee to Dennis Quaid Emmanuelle Seigner to Sanaa Lathan Anne Hathaway to Maggie Q Audrey Tautou to Dennis Quaid Michelle Pfeiffer to Dennis Franz Michelle Pfeiffer to Jason Lee Audrey Tautou to Sanaa Lathan Michelle Rodriguez to Anne Hathaway Average

20 Oracle of Baseball

21 Small world experiment

22 1950~1960 艾狄胥與倫伊 匈牙利數學家艾狄胥 大多數數學家的艾狄胥數是 5或6 隨機圖 人際關係網路並無特定的結構與秩序

23 人際關係隨機圖 Mary Nancy Eve Jake Bill Sue Joe

24 公路建造問題 •五十個城市至少要建造幾條公路? 98/1225=8% (隨機連結) • 城市越多公路百分比越少 • 三百個城市只需 2 %
98/1225=8% (隨機連結) • 城市越多公路百分比越少 • 三百個城市只需 2 % • 六十億的人際網路—要連接地球上任一兩個人→→ →→ 24 !!

25 假設每個人有五十個朋友 分隔度 1 分隔度 2 分隔度 3 分隔度6時總共有 億

26 群聚現象 六十億的人際網路—如果只連接最靠近的五十個人分隔度會增加千萬倍

27 1973 格蘭若維特 《弱聯繫的力量》─弱聯繫扮演著維繫整個人際網路的關鍵角色(橋樑) 瑪莉 蘇

28 弱聯繫比強聯繫重要 想要找工作→ 弱聯繫可以讓訊息傳得遠 例如:謠言傳播 16%的人是經由常常見面的朋友找到工作，
84%的人是經由偶而或很少見面的朋友找到工作。 弱聯繫可以讓訊息傳得遠 例如:謠言傳播

29 Watts and Strogatz 1998 華茲與史楚蓋茲 有秩序的網路會造成群聚與團體 隨機的網路會製造小世界，但沒有群聚
華茲與史楚蓋茲建造一個數學網路方法，顯著呈現小世界理論的架構 圓上有1000點 每個點只與10個相鄰的點相連

30 群聚度2/3 分隔度50

31 小世界 有秩序 隨機的 P = 0 隨機度增加 P = 1

32 小世界網路的集體動力學 1998年，康奈爾大學Duncan J. Watts與論文指導教授Steven Strogatz共同提出論文「小世界網路的集體動力學』，開啟了小世界網路的研究風潮，此研究促使人們更了解真實世界裡無所不在的網路。例如辦公室裡的朋友關係圖、大學新生的校友關係圖、電力公司供電圖、捷運與公車路線圖等都可以視之為一個小世界網路。

33 Visualizing Friendships

34 Visualizing Friendships
Facebook的1名實習生，對政治疆界如何影響世界友誼感興趣。他憑著5億臉書用戶數據，畫出了1張世界地圖。 這張深藍色底的地圖以光點標示友誼，美國東半部與歐洲最亮，而臉書使用者很少的中國、及則多半是暗的。 臉書數據基礎工程團隊實習生巴特勒（PaulButler）說：「我對地理和政治疆界，如何影響人們與朋友居住地的相對關係很感興趣。」 「我想要畫出1張地圖，能顯示哪些城市有緊密友誼。」

35 facebook puts six degree of separation theory to the test
Group Info Name: Six Degrees of Separation The small world phenomenon (also known as the small world effect) is the hypothesis that everyone in the world can be reached through a short chain of social acquaintances. The concept gave rise to the famous phrase six degrees of separation after a 1967 small world experiment by social psychologist Stanley Milgram which suggested that two random US citizens were connected on average by a chain of six acquaintances. That is, a friend of a friend of a friend of a friend of a friend knows the president of the United States, or the Queen of the Netherlands, or the president of France or Osama and so on…

36

37 Ryan

38

39 Average Degree of Separation: 4.67
Randomized Connections to members of group: RYAN DOSETAREH 1. Adam Klien 2. Jeremy Adler 3. Josh Twersky 4. Rachel Saks LAUREL CONDON RYAN DOSETAREH 1.Brandon White 2. Christina Carmen Chiknas 3. Sarah Steiner 4. Jennifer Forsthoefel 5. Pippa Simmons 6. Jake Armstrong CAELEIGH BROHM RYAN DOSETAREH 1.Ben Perlow 2.Lauren Bowles 3.Brett Clark's 4.Kendrick Brinson 5.Annie Agnone 6.Katie Mercer AMANDA FORTIER RYAN DOSETAREH 1. Aaron Wersing 2. Michelle Ahoobim 3. Jordan Gimelstein 4. Faye Elizabeth Maiman CAITLIN PRINCE RYAN DOSETAREH 1. Darren Tobin 2. Robin Goodman 3. Lauren Kuncewitch 4. Matt Cardona 5. Eric King BRIAN LOMASKY RYAN DOSETAREH 1. Jonathan Freinkel 2. David Blane 3. Ashley Gross' RYAN MCGETTIGAN Average Degree of Separation: 4.67 I will redo this once the group reaches 400,000.

40 Average Degree of Separation: 4.0
At 400k: RYAN DOSETAREH 1. Peter Rivner 2. Aaron Kooden 3. Samantha Weinberg 4. Dave Arnold ANTHONY MANNA (UWO; London) RYAN DOSETAREH 1. Daveed Lift 2. Sarah Fishman 3. Austin Cabot 4. Chintan Patel AARON ESPOSITO (Indiana; Bloomington, IN) RYAN DOSETARH 1. Ari Levine 2. Danielle Alexandra Abelson's CHAD MURRAY; Greeley, CO) RYAN DOSETAREH 1. Hooman Nourparvar 2. Michael Goldin ALEX TELLECHEA (Auburn University, AL) RYAN DOSETAREH 1. Alina Birger 2. Taylor Popp 3. Ainslee Marsden 4. Farrah Fraser 5. Andrew Fraser 6. Casimar Fraser 7. Tiffany Brunke PATRICK LeBLANC (Algonquin Colllege; Ottawa) RYAN DOSETAREH 1. Carlie Stein 2. Patricia Dampf 3. Julie Schwarz 4. Molly Garner 5. Lauren Anne Dixon REBECCA DONKER (Syracuse, NY) Average Degree of Separation: 4.0

41 Six Degrees Mission GAME

42 Sciscape新聞內容[Jul 10, 2000] 一般科學：複雜系統之強健性與冪次定律
編輯：rogers 許多自然界或人為的系統都能遵守統計上的冪次定律(power law),比如說當事件和事件規模具有函數關係時, 事件將隨著事件規模的增加而呈指數式的遞減. 這些事件包含森林大火之範圍大小, 停電時間, 颶風所造成的損失, 透過網路傳送的檔案, 地震等等. 而指數律正是 Self organized criticality 及edge of chaos 狀態的明顯特徵之一. 加州大學 Jean Carlson 以及加州理工 John Doyle 提出 highly optimized tolerance 理論, 他們宣稱, 對於由許多子系統所連結成的複雜系統, 不管是自然演進還是人為設計, 當該系統可以有效的容忍某些不確定因素時 (具強健性), 那麼這系統對於其它未被考慮到的不確定因素將變得更敏感, 也就是說, 強健性和敏感度具有相互遞換的效果, 其中, 這不確定因素包含系統內部的不確定因素以及外在環境的干擾. 就如同能量守恆與熵, 如果試圖去打破這強健性原則, 都會面臨失敗. 以生態系統為例, 如果生態可以容忍氣溫變化, 濕度, 養分等巨幅變化, 那麼這生態卻可能無法容忍一些意料之外的小干擾, 如基因突變 , 外來族群遷入, 或新的病毒. 這些干擾可能會造成生態巨大的改變. 文獻中指出當一複雜系統處於 highly optimized tolerance 狀態, 該系統將滿足冪次律, 且強健性原則導致該系統具有 "強健, 但易被破壞" 之特性. 研究者在文獻中提出幾個生物學及工程例子來支持他們的論點, 並提供相關領域參考. 論文出處: J. M. Carlson and John Doyle, Highly Optimized Tolerance: Robustness and Design in Complex Systems, Physical Review Letters -- March 13, Volume 84, Issue 11, pp

43 Sciscape新聞內容[Aug 28, 2005] 物理：模擬小世界網路的臨界指標 編輯：HCC
比利時荷語魯汶大學的研究顯示，如果調整網路hub分配點使之對鄰近點的影響性較其他一般節點(node)為小，可以模擬小世界網路(small-world networks)的臨界指標(critical thresholds)。 1998年，康奈爾大學Duncan J. Watts與論文指導教授Steven Strogatz共同提出論文「小世界網路的集體動力學』，開啟了小世界網路的研究風潮，此研究促使人們更了解真實世界裡無所不在的網路。例如辦公室裡的朋友關係圖、大學新生的校友關係圖、電力公司供電圖、捷運與公車路線圖等都可以視之為一個小世界網路，於此網路內包含了一些特定節點稱之為hubs的分配點，此些分配點擁有更大的節點連結數量，因此任一節點透過hubs分配點只消幾個步驟即可與另一節點取得聯繫。例如於境外移入傳染病過程中，某些入境患者即為hubs分配點，傳染途徑透過hubs分配點即可獲得追蹤。 研究人員於實際生活上的小世界網路可觀察到臨界指標值，例如瘟疫的爆發決定於疾病的傳染程度或人群的接觸數目，不過網路理論至今尚不能很好的模擬出臨界指標。 比利時荷語魯汶大學Joseph Indekeu與其同事的研究顯示，小世界網路可以模擬其臨界指標(critical thresholds)，只要對網路hub分配點進行微調，使之對鄰近點的影響性較其他一般節點為小即可。例如李四端、汪笨湖可為政論網路小世界裡面的hub分配點，所有政論節目觀眾的關聯性都可能指向李、汪兩位先生，不過朋友對你投票取向的影響程度，可能較此些政論節目主持人為大，所以網路hub分配點的影響性可以微調。Joseph Indekeu的研究報告指出，微調於數學運算相當於切斷hub分配點的連結關係，Joseph Indekeu認為研究結果也許有助於防止電力中斷或瘟疫爆發等現象。 我們把SARS病患隔離於專屬醫院，或者關掉政論節目，不也正與Joseph Indekeu的理論相契合嗎？ --參考來源： Physics News Update: Networking Can Be Critical, Literally

44 Sciscape新聞內容[Dec 18, 2000] 物理：強壯的網際網路 編輯：John C. H. Chen
網際網路抵抗外界破壞的能力可能是遠遠超過想像的。就算是99%的連結遭到破壞，照樣可以連結到全世界。 。他們分別使用處理點連結的擴散理論(percolation theory)及上文提到的如果將一部網路主機視為一個節點並設其連結數目為k，則這類節點在總連結中的比例大約正比於k^(-a)。這個比例稱為"與尺度無關的冪次分布"(scale free power law distribution)和網路的規模無關。這種分布的最大特徵是衰減的速度比指數衰減來的慢的多，也就是當其中一部份的節點被破壞時，大多數的電腦仍保有相當多的連結。 這個結論得到了兩組研究人員的支持機率分布驗證了網路在喪失某些節點時的行為。除了上述的結論之外，他們發現選取特定高度連結的主機加以破壞將容易破壞整個網路的連結。這個結果將有處於網路工程師增加網路受到攻擊時的抵抗力。 原始論文 Cohen et al, Phys. Rev. Lett, 20 Nov, 2000 Callaway et al., Phys. Rev. Lett. to be publish --參考來源： Physics News Update 513-1, The Internet is Surprisingly Robust

45 Sciscape新聞內容[Apr 09, 2001] 一般科學：電腦病毒在網路上的傳播方式 編輯：HCC
過去科學家錯認電腦病毒以類似生物病毒的方式散佈。然而一篇剛發表的研究報告透露，網際網路結構上的弱點導致電腦病毒傳染並不像生物病毒傳播一樣必須超過一個最低門檻數目，此現象會讓網路非常容易遭受病毒的攻擊。 西班牙Politecnica de Catalunya大學的物理學家 Pastor Satorrass與其合作夥伴曾利用一個研究病毒感染的標準數學模式來模擬一般病毒的傳播，結果顯示受病毒感染的個體數目要超過一個最低門檻，否則病毒會自然的消失；然而將此模式應用於無尺度(scale-free)的電腦網路，發現要產生傳染的最低門檻數目並不存在，電腦病毒即使以非常緩慢的速度傳播，在網路上依然可以倖存。 原因在於電腦網路屬於無尺度的網路結構，在這種網路結構裡面的許多節點，其與其他節點的連結數目並不具有一個平均值，不若格狀網路結構，每個節點都與周遭四個節點連結，至於隨意式(random) 網路結構裡的所有節點，雖然可以任意連結，但仍能以統計方式計算出節點的平均連結值，隨意式網路的節點其節點連結數目會大於平均連結值的機會很低。 無尺度網路中的部份節點，會以較高的數目進行連結，大部分的節點則只以低數目連結，﹝例如學校某個研究室內的電腦只與一部電腦連接，而電腦中心一部伺服器主機則連接了近百部電腦﹞，而且遠端節點之間具有許多的捷徑，所以相距甚遠的電子郵件伺服器憑著幾個跳躍就完成連接，由於上述的電腦網路結構特徵，讓網路非常容易遭受病毒的攻擊。 原始論文： Romualdo Pastor-Satorras and Alessandro Vespignani, Epidemic Spreading in Scale-Free Networks, Physical Review Letters, pp , Vol. 86, April 2, 參考來源： Nature Science Update: Networking can be hazardous Physical Review Focus: Internet Plagues Spread Rapidly

46 Sciscape新聞內容[Sep 13, 2004] 物理：『有失必有得』，保護網路的新構想
編輯：Chiachen Chang 現實生活中網路結構常見於我們的四周，例如電信網路、電力網路、網際網路甚至人際關係網路等等。由於這些無所不在的網路支撐起我們每天的生活，因此如何保護整個網路的運作順暢，便成為一項重要的課題。 儘管網路的組成錯綜複雜，但其中的拓樸結構卻是有跡可尋的。研究顯示出，若節點的連結數目為 k，則這類節點在整個網路中的分佈遵守一個標度律：k-a。換句話說，網路中大部分的節點其連結數目都是很小的。而這類的網路遇到隨機失誤(random failure)的時候，絕大部分的網路節點還能夠保持在正常運作的狀態。但是如果我們針對這類網路中的某幾個主要節點(有大量連結的節點)進行攻擊，整個網路就會因此而癱瘓無法運作。一個著名的例子是去年八月十四日發生在美國東岸的停電事件，因為東北部某處的供電系統網路運作不穩，導致 Ohio 州的一個發電廠(節點)癱瘓，最後引起了美國東北部的大規模停電事件。因為這次的教訓，使得不少網路理論學家開始注意網路運作與節點攻擊的問題。 最近德國 Max Planck Institute for the Physics of Complex systems 的數學家 Adilson Motter 在物理學評論通訊(Physical Review Letters)上發表了針對節點攻擊下，如何避免網路發生大規模癱瘓的模型。就概念上來看，Motter 的構想其實可以類比於國家公園常用來防止森林大火蔓延的一項技巧：開闢防火巷，將大片的森林用防火巷分割成數個大塊，如此一來大火就不會蔓延整片森林。 但在網路結構中如何選定『防火巷』卻是一個需要巧思的問題。Motter 的方法是在網路癱瘓初期移除連結最少的一些節點。進一步來說就是：在癱瘓發生初期，我們必須分析每個節點產生的負荷與其所管制(channel)的網路流量兩者的比例，如果比例很懸殊，那麼這個節點對整個網路流的貢獻相對來說是比較小的，因此我們可以將這個節點自網路中移除。Motter 針對一個有五千個節點的理想網路做數值模擬的結果顯示，這個方法可以很有效的降低癱瘓區域的擴散，使得網路中大部分的區域得以運作正常。 Motter 的這項工作引起不少網路理論以及實務學家的注意，其中當然不乏質疑的聲音。最主要的質疑來自於 Motter 所以引用的網路模型過於理想化，與現實生活中的實際網路結構與性質有段差距。儘管如此，Motter 的『防火巷』構想確實有其獨創之處，而且Motter 的方法並沒有對網路結構與資料流的特性做任何假設，故其理論有其一般性。但如何改進這個構想使其可以更進一步匹配實際的網路結構則有待進一步的努力。 原始論文： Cascade Control and Defense in Complex Networks A. E. Motter, Phys. Rev. Lett. 93, (2004) --參考來源： Physics News Update: Defending Networks Against Cascading Failure Removing Nodes in a Network Can Protect Against Cascading Failures, Physics Today, September 2004, P.22.

47 期末考 簡述細胞自動機的特點。 假設一維細胞自動機的運算規則如下表
以■代表1 □代表0完成下列表格

48 期末考 一九九八年，美國康乃爾大學華茲（Watts）與史楚蓋茲（Strogatz）的「小世界」理論一出，為網絡研究帶來一股清新的風氣，只要能用網絡來建立模式的自然或人為系統，似乎都可見「小世界」的身影。幾乎同時期，法魯托斯（Faloutsos）兄弟從觀察網際網路（Internet），巴拉巴西（Barabási）的研究群從觀察全球資訊網所發現的冪次律，也不斷在各種的網絡模式裡出現。說明Barabasi所發現的全球資訊網的冪次律分布現象。 為什麼「富者愈富」是網路的小世界架構的天然引擎。 除了全球資訊網，舉例說明其他網路也具有小世界架構「富者愈富」的現象。 年紐約時報作了一個好玩的遊戲稱為「陸文斯基的六度分隔」比方說，陸文斯基和辣妹合唱團只相隔幾步而已。辣妹合唱團主演的電影「天旋地轉」中，演員喬治文特出現過。喬治文特和泰迪丹森一起演出電視影集「歡樂酒店」，泰迪丹森的太太是瑪莉史汀柏根道，兩人在瑪莎葡萄園結婚時柯林頓參加了。試計算你與美國柯林頓總統有幾度分隔。

49 期末報告 Six Degress of Separation
Six Degress of Separation: Ron Paul & Marc Jacobs OK… I thought it would be fun to play 6 degrees of Separation!  This is a game that became a spin-off with the 80’s trivia time blower, Six Degrees of Kevin Bacon. You know, the test of the truly small world, where you pick any famous person and you have to connect them to Kevin Bacon in film roles in 6 degrees or less. But, this is a luxe bag blog, so instead of Kevin Bacon, I’ll be connecting to Marc Jacobs in honor of his wildly successful collaboration with Louis Vuitton, and his engenius insight to bring Takashi Murakami into the mix, which has just been celebrated like mad this week in grand opening exhibit this week at MOCA in LA. I wanted to pick someone who I could think of absolutely no similarities or connections with Marc.  I thought it would be timely to do some of the 2008 Presidential Candidates, as I figured all but H.R.C (who may just  be a close and personal friend, since MJ did a bunch of cool promo pieces for her recently) probably fall into this catagory! As a nod to the amazing grassroots effort and insane but creative marketing methods put forth by the Ron Paul campaign- I thought I’d start there. I also thought it would be fun to see if I get any of those zainy Ron Paul rEVOLution postings on my blog as a result! Everyone else seems to be shy about commenting… so I thought I’d see if this would bring some comments out of the woodwork!!! I won’t be using film roles for my connections, but just any pictures of two people together!!!

50 Ron Paul 美國共和黨籍眾議員 2008 Ron Paul & Sarah Palin

51 Marc Jacobs 美國時尚設計師 路易威登的創意總監

52 Six Degrees of Marc Jacobs…Ron Paul
Here we have Ron Paul & Ronald Reagan on Airforce One in 1976. Then of course you have Ronald Reagan and Steven Spielberg after the ET showing in the White House.

53 Steven Spielberg directed Drew Barrymore in ET
Steven Spielberg directed Drew Barrymore in ET. Why does it always make me kind of sad to see pictures of her as a little girl? Drew Barrymore not only starred with Luke Wilson in Home Fries, but they had a little thing going on for a while.

54 Luke Wilson played alongside Reese Witherspoon in the Legally Blonde movies…
Marc Jacobs Reese is a big fan of MJ’s. Here she is at Kate Hudson’s Halloween party Saturday night. After seeing the MJ tutu pics, the cheerleading costume is pretty much par for the course.

55 期末報告 範例1 範例2