關(guān)于第三周學(xué)習(xí)內(nèi)容的延伸討論小世界現(xiàn)象、模型（解釋，預(yù)言）、驗(yàn)證（測(cè)量）人群與網(wǎng)絡(luò)

社會(huì)網(wǎng)絡(luò)中的計(jì)算思維方法

辨析：“小世界”的含義這個(gè)世界上的人不算多相對(duì)于世界人口，地球的尺度太小人類社會(huì)網(wǎng)絡(luò)中，任何兩個(gè)人之間最短路徑長(zhǎng)度都不超過(guò)“6”（即“六度分隔”）社會(huì)網(wǎng)絡(luò)中，任何兩人之間存在短路徑的概率很高，而且短視搜索經(jīng)過(guò)短路徑的概率也很高兩個(gè)不相識(shí)的出差人，在火車(chē)上容易聊到共同的熟人－

theworldissmall!“同班同學(xué)關(guān)系”（含小學(xué)、中學(xué)、大學(xué)等）是不是也是個(gè)“小世界”？小世界，是人類社會(huì)網(wǎng)絡(luò)中的一個(gè)規(guī)律嗎

？體會(huì)Milgram實(shí)驗(yàn)設(shè)計(jì)中的計(jì)算思維幾百名初始者，要求每人通過(guò)轉(zhuǎn)發(fā)，爭(zhēng)取讓一個(gè)指定的人收到一封信；向每個(gè)初始者提供了目標(biāo)收信人的姓名、地址、職業(yè)等個(gè)人信息；規(guī)定：參與者只能將信件直接發(fā)給相當(dāng)熟的人，并請(qǐng)他繼續(xù)轉(zhuǎn)發(fā)。因此，如果一個(gè)參與者不認(rèn)識(shí)目標(biāo)收信人，則他不能直接將信寄給他；結(jié)果，約三分之一的信件經(jīng)過(guò)平均六次轉(zhuǎn)發(fā)到達(dá)了目標(biāo)。容錯(cuò)（通過(guò)冗余）短視（分散）搜索幾百名…約三分之一到達(dá)不同的階段（除了最后）做同樣的事情遞歸給定目標(biāo)特征，通過(guò)轉(zhuǎn)發(fā)，爭(zhēng)取到達(dá)目標(biāo)假設(shè)網(wǎng)格距離特征，試給出從A到B的短視搜索路徑和最短路徑BA生活中的遞歸現(xiàn)象——

一次蓋章的悲催“遞歸”過(guò)程還可以舉出哪些體現(xiàn)遞歸現(xiàn)象的例子？漢諾塔問(wèn)題任務(wù)：A柱上的n個(gè)盤(pán)子移到C

柱上，可以借用B中轉(zhuǎn)。過(guò)程中不可“上大下小”ABC遞歸思路：如果n=2，直接做；否則，（1）將n-1個(gè)從A移到B，利用C中轉(zhuǎn)，（2）將最大的那個(gè)從A移到C，（3）將n-1個(gè)從B移到C，利用A中轉(zhuǎn)。我們能否設(shè)計(jì)某種類似實(shí)驗(yàn)？體現(xiàn)“遞歸”和“短視搜索”給一個(gè)目標(biāo)，希望能達(dá)到，但每一步只有“局部信息”引導(dǎo)著往前走，看能否達(dá)到目標(biāo)，以及經(jīng)過(guò)路徑的長(zhǎng)短摸著石頭過(guò)河？在網(wǎng)上，試從北大“走”到西藏民族學(xué)院？北京大學(xué)

相關(guān)鏈接

研究生院院長(zhǎng)聯(lián)席會(huì)

國(guó)內(nèi)大學(xué)

西藏

西藏民族學(xué)院為什么“小世界”現(xiàn)象的發(fā)現(xiàn)是令人驚奇（難以置信）的面對(duì)重要實(shí)驗(yàn)現(xiàn)象的科學(xué)態(tài)度重復(fù)實(shí)驗(yàn)，看是否偶然現(xiàn)象嘗試說(shuō)明其必然性，探明背后的機(jī)理社會(huì)現(xiàn)象也可以這樣研究？為社會(huì)網(wǎng)絡(luò)建模：構(gòu)想一種特別的圖體現(xiàn)人們建立關(guān)系的兩種基本原因（1）（2）如何生成具有“隨機(jī)邊”的網(wǎng)絡(luò)圖？如何實(shí)現(xiàn)“隨機(jī)邊”？假設(shè)你要構(gòu)造一個(gè)網(wǎng)絡(luò)，16個(gè)節(jié)點(diǎn)，首先是連接成一個(gè)環(huán)狀，然后要從每個(gè)節(jié)點(diǎn)產(chǎn)生一條到其他節(jié)點(diǎn)的隨機(jī)邊不是“隨便的邊”，而是概率意義上的“隨機(jī)邊”，即每個(gè)節(jié)點(diǎn)都有同樣機(jī)會(huì)被連接F102ED39AB7654C8運(yùn)用rand()函數(shù)，它保證每次以同樣概率返回(0,1)中的任何一個(gè)數(shù)01假設(shè)各節(jié)點(diǎn)順時(shí)針確定相對(duì)位置。從節(jié)點(diǎn)0開(kāi)始考慮0.5178*15=7.76那么節(jié)點(diǎn)1就是0.0684*15=1.03012…141501F102ED39AB7654C8rand()×150123456789ABCDEF假設(shè)各節(jié)點(diǎn)順時(shí)針確定相對(duì)位置。從節(jié)點(diǎn)0開(kāi)始考慮0.5178*15=7.76那么節(jié)點(diǎn)1就是0.0684*15=1.03課堂作業(yè)：按照所給數(shù)據(jù)和所示樣例，產(chǎn)生發(fā)自節(jié)點(diǎn)

5，8，C，F(xiàn)

的隨機(jī)邊

F102ED39AB7654C80123456789ABCDEF在這樣的網(wǎng)絡(luò)（圖）上可以證明：任何兩個(gè)節(jié)點(diǎn)之間存在短路徑的概率很高科學(xué)家們于是就傾向于相信：世界上任意兩人之間存在很短的“認(rèn)識(shí)關(guān)系鏈”幾乎是必然的。《Nature》，1998我們相信嗎？從這么簡(jiǎn)單化的抽象模型，得出的結(jié)論，能說(shuō)明社會(huì)網(wǎng)絡(luò)這么復(fù)雜事物的性質(zhì)嗎？研究人員對(duì)這模型也有質(zhì)疑它解釋不了Milgram實(shí)驗(yàn)的另一個(gè)重要現(xiàn)象：短路徑不僅存在，而且通過(guò)短視搜索能發(fā)現(xiàn)于是就有了“弱連接的概率應(yīng)該隨距離的冪次遞減”的猜想，形成

Watts-Strogatz-Kleinberg社會(huì)網(wǎng)絡(luò)模型證明了在其中短路徑不僅存在，而且通過(guò)短視搜索能發(fā)現(xiàn)。同時(shí)還得到冪次q=2是最優(yōu)的認(rèn)識(shí)。思考：如何生成具有這種隨機(jī)特征的網(wǎng)絡(luò)小測(cè)問(wèn)題關(guān)于Watts-Strogatz（WS）模型與Watts-Strogatz-Kleinberg（WSK）模型，下列哪些是不正確的陳述？WSK模型是在WS基礎(chǔ)上的擴(kuò)展WSK模型和WS模型的基本思路完全不同WS模型是WSK模型的一種特殊情況WSK模型更好地把握了Milgram實(shí)驗(yàn)的特征WSK模型推翻了WS模型研究的進(jìn)展帶來(lái)了新的質(zhì)疑難道人類社會(huì)網(wǎng)絡(luò)真是那樣的？同質(zhì)性弱連接弱連接概率隨距離冪次遞減冪次≈2??？？！關(guān)系的密切性，交往的頻繁性，機(jī)會(huì)的多少模型中的距離，對(duì)應(yīng)現(xiàn)實(shí)中的什么？在地理空間意義上－－相距范圍內(nèi)的人數(shù)在社會(huì)生活中－－共屬社團(tuán)（群體）的最小規(guī)模BDCARA(B)=?RA(C)=?RB(D)=?于是，給定每個(gè)節(jié)點(diǎn)的位置，就可以算出每個(gè)節(jié)點(diǎn)對(duì)每個(gè)節(jié)點(diǎn)的相對(duì)rank（排位）。但，怎么驗(yàn)證：人們有關(guān)系的概率隨rank遞減呢？若還有節(jié)點(diǎn)之間的關(guān)系數(shù)據(jù)，就可以看

在該rank上的連接數(shù)

－－－－－－－－－

一定rank上的總?cè)藬?shù)rank占比從這地理位置數(shù)據(jù)是怎么得到這的?社交網(wǎng)上的關(guān)系數(shù)據(jù)r概率＋LiveJournal社交網(wǎng)絡(luò)數(shù)據(jù)我們通過(guò)例子來(lái)體會(huì)這個(gè)數(shù)據(jù)處理過(guò)程假設(shè)右邊這網(wǎng)絡(luò)假設(shè)各節(jié)點(diǎn)都有某種“位置”，從而可以算相對(duì)rank下面的算例，只考慮2個(gè)節(jié)點(diǎn)（a,b），緊接著的課堂作業(yè)，考慮4個(gè)節(jié)點(diǎn)（a,b,c,d）FHGIEDJABKC給定一個(gè)節(jié)點(diǎn)，都可以算得其他每個(gè)節(jié)點(diǎn)相對(duì)于它的rankbcdefghijk2332445455a:從小到大排序（數(shù)據(jù)量很大，每個(gè)rank可能有大量重復(fù)）acdefghijk3532425455b:c,d,e,f,g,h,i,j,k:得到各自rank數(shù)據(jù)bedcfgihjk2233444555a:egdafihcjk2233445555b:c,d,e,f,g,h,i,j,k:相應(yīng)處理bedcfgihjk2233444555a:egdafihcjk2233445555b:c,d,e,f,g,h,i,j,k：相應(yīng)處理。為簡(jiǎn)單起見(jiàn)，下面算平均概率的時(shí)候只考慮a和b的rank數(shù)據(jù)FHGIEDJABKCrank2345占比1/21/41/411/2423451rank概率課堂作業(yè)：設(shè)你得到了其他節(jié)點(diǎn)相對(duì)于4個(gè)節(jié)點(diǎn)的所有rank值bcdefghijk2332445455a:acdefghijk3532425455b:abdefghijk5233544555c:abcefghijk2333445324d:試依據(jù)右邊的