人群與網(wǎng)絡(luò)20143周翻轉(zhuǎn)課堂

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

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

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

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

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

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

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

相關(guān)鏈接

研究生院院長聯(lián)席會

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

西藏

西藏民族學(xué)院為什么“小世界”現(xiàn)象的發(fā)現(xiàn)是令人驚奇（難以置信）的面對重要實(shí)驗(yàn)現(xiàn)象的科學(xué)態(tài)度重復(fù)實(shí)驗(yàn)，看是否偶然現(xiàn)象嘗試說明其必然性，探明背后的機(jī)理社會現(xiàn)象也可以這樣研究？為社會網(wǎng)絡(luò)建模：構(gòu)想一種特別的圖體現(xiàn)人們建立關(guān)系的兩種基本原因（1）（2）如何生成具有“隨機(jī)邊”的網(wǎng)絡(luò)圖？如何實(shí)現(xiàn)“隨機(jī)邊”？假設(shè)你要構(gòu)造一個網(wǎng)絡(luò)，16個節(jié)點(diǎn)，首先是連接成一個環(huán)狀，然后要從每個節(jié)點(diǎn)產(chǎn)生一條到其他節(jié)點(diǎn)的隨機(jī)邊不是“隨便的邊”，而是概率意義上的“隨機(jī)邊”，即每個節(jié)點(diǎn)都有同樣機(jī)會被連接F102ED39AB7654C8運(yùn)用rand()函數(shù)，它保證每次以同樣概率返回(0,1)中的任何一個數(shù)01假設(shè)各節(jié)點(diǎn)順時針確定相對位置。從節(jié)點(diǎn)0開始考慮0.5178*15=7.76那么節(jié)點(diǎn)1就是0.0684*15=1.03012…141501F102ED39AB7654C8rand()×150123456789ABCDEF假設(shè)各節(jié)點(diǎn)順時針確定相對位置。從節(jié)點(diǎn)0開始考慮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ò)（圖）上可以證明：任何兩個節(jié)點(diǎn)之間存在短路徑的概率很高科學(xué)家們于是就傾向于相信：世界上任意兩人之間存在很短的“認(rèn)識關(guān)系鏈”幾乎是必然的?！禢ature》，1998我們相信嗎？從這么簡單化的抽象模型，得出的結(jié)論，能說明社會網(wǎng)絡(luò)這么復(fù)雜事物的性質(zhì)嗎？研究人員對這模型也有質(zhì)疑它解釋不了Milgram實(shí)驗(yàn)的另一個重要現(xiàn)象：短路徑不僅存在，而且通過短視搜索能發(fā)現(xiàn)于是就有了“弱連接的概率應(yīng)該隨距離的冪次遞減”的猜想，形成

Watts-Strogatz-Kleinberg社會網(wǎng)絡(luò)模型證明了在其中短路徑不僅存在，而且通過短視搜索能發(fā)現(xiàn)。同時還得到冪次q=2是最優(yōu)的認(rèn)識。思考：如何生成具有這種隨機(jī)特征的網(wǎng)絡(luò)小測問題關(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)展帶來了新的質(zhì)疑難道人類社會網(wǎng)絡(luò)真是那樣的？同質(zhì)性弱連接弱連接概率隨距離冪次遞減冪次≈2??？？！關(guān)系的密切性，交往的頻繁性，機(jī)會的多少模型中的距離，對應(yīng)現(xiàn)實(shí)中的什么？在地理空間意義上－－相距范圍內(nèi)的人數(shù)在社會生活中－－共屬社團(tuán)（群體）的最小規(guī)模BDCARA(B)=?RA(C)=?RB(D)=?于是，給定每個節(jié)點(diǎn)的位置，就可以算出每個節(jié)點(diǎn)對每個節(jié)點(diǎn)的相對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ù)我們通過例子來體會這個數(shù)據(jù)處理過程假設(shè)右邊這網(wǎng)絡(luò)假設(shè)各節(jié)點(diǎn)都有某種“位置”，從而可以算相對rank下面的算例，只考慮2個節(jié)點(diǎn)（a,b），緊接著的課堂作業(yè)，考慮4個節(jié)點(diǎn)（a,b,c,d）FHGIEDJABKC給定一個節(jié)點(diǎn)，都可以算得其他每個節(jié)點(diǎn)相對于它的rankbcdefghijk2332445455a:從小到大排序（數(shù)據(jù)量很大，每個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)處理。為簡單起見，下面算平均概率的時候只考慮a和b的rank數(shù)據(jù)FHGIEDJABKCrank2345占比1/21/41/411/2423451rank概率課堂作業(yè)：設(shè)你得到了其他節(jié)點(diǎn)相對于4個節(jié)點(diǎn)的所有rank值bcdefghijk2332445455a:acdefghijk3532425455b:abdefghijk5233544555c:abcefghijk2333445324d:試依據(jù)右邊的