網(wǎng)絡(luò)結(jié)構(gòu)與效應(yīng)原理：第20章 小世界現(xiàn)象

小世界現(xiàn)象StanleyMilgram,1933-1984TheSmall-worldProblem,PsychologyToday,1967（第20章）要點(diǎn)與目標(biāo)小世界的基本性質(zhì)短路經(jīng)可發(fā)現(xiàn)最佳距離2小世界的研究范式實(shí)驗(yàn)發(fā)現(xiàn)模型解釋模擬驗(yàn)明大數(shù)據(jù)實(shí)證已有知識(shí)和地理/網(wǎng)絡(luò)距離的作用“小世界”的研究之路Milgram的實(shí)驗(yàn)（1967）第一個(gè)驚奇：六度分隔！第二個(gè)驚奇：那些信居然能沿短路徑到達(dá)！Watts-Strogatz的社會(huì)網(wǎng)絡(luò)模型，對(duì)第一個(gè)驚奇給予了解釋（1998）Watts-Strogatz-Kleinberg模型，對(duì)第二個(gè)驚奇給予了解釋（2000）W-S-K模型在多個(gè)大規(guī)模OSN中得到驗(yàn)證（2005）實(shí)驗(yàn)現(xiàn)象理論解釋測(cè)量驗(yàn)證3StanleyMilgram的實(shí)驗(yàn)幾百名“初始者”，要求每人努力通過轉(zhuǎn)發(fā)讓一個(gè)指定的人收到一封信；向每個(gè)初始者提供了目標(biāo)收信人的姓名、地址、職業(yè)等個(gè)人信息；規(guī)定：參與者只能將信件直接發(fā)給能直呼其名的熟人，并請(qǐng)他繼續(xù)轉(zhuǎn)發(fā)。因此，如果一個(gè)參與者不認(rèn)識(shí)目標(biāo)收信人，則他不能直接將信寄給他；要求參與者力爭(zhēng)讓這信件能盡早達(dá)到目的地；結(jié)果，約三分之一的信件經(jīng)過平均六次轉(zhuǎn)發(fā)到達(dá)了目標(biāo)4在網(wǎng)上，從北大如何到東北大學(xué)？北京大學(xué)

相關(guān)鏈接

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

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

遼寧

東北大學(xué)如何從東北大學(xué)到北大？東北大學(xué)

快速鏈接（CERNET東北地區(qū)中心）

CERNET中國教育和科研計(jì)算機(jī)網(wǎng)

CERNET

CERNET2成員（北京大學(xué)）

在新浪微博上，從“北京大學(xué)李曉明”幾步能走到“姚晨”？有理由相信：新浪微博也是一個(gè)“小世界”實(shí)驗(yàn)結(jié)果帶給人們兩點(diǎn)驚奇社會(huì)網(wǎng)絡(luò)中兩節(jié)點(diǎn)間包含豐富的短路徑通過“有意識(shí)的轉(zhuǎn)發(fā)”能夠“自動(dòng)地”找到這些短路徑問題為什么社會(huì)網(wǎng)絡(luò)具有這樣的性質(zhì)？它們?cè)从谏鐣?huì)網(wǎng)絡(luò)的哪些基本原理？換句話說，能否依據(jù)社會(huì)網(wǎng)絡(luò)的某些基本原理，說明這種這種性質(zhì)的必然性？8形成社會(huì)網(wǎng)絡(luò)的兩種基本力量同質(zhì)性（選擇，社會(huì)影響），三元閉包家庭成員，鄰里關(guān)系，同學(xué)，同事對(duì)應(yīng)社會(huì)網(wǎng)絡(luò)中的大量的“三角形”體現(xiàn)某種“親近”（例如地理范圍的）弱聯(lián)系偶然的原因，認(rèn)識(shí)的“遠(yuǎn)程”朋友對(duì)其所在的圈子并不一定熟悉一種什么樣的形式化網(wǎng)絡(luò)，既體現(xiàn)這兩種力量的作用，也便于我們分析其中是否有小世界現(xiàn)象？9Watts-Strogatz模型［1998］

定義一種圖（網(wǎng)絡(luò)），它體現(xiàn)這兩種力量存在許多“三角形”和少數(shù)隨機(jī)的“遠(yuǎn)程邊”想象大量節(jié)點(diǎn)排布成均勻網(wǎng)格狀連接近鄰:確定性，連接遠(yuǎn)程:隨機(jī)性每?jī)牲c(diǎn)之間有一個(gè)“網(wǎng)格距離”10Watts-Strogatz模型(r,k)

體現(xiàn)了同質(zhì)連接和弱關(guān)系連接的概念（利用r和k控制相關(guān)的強(qiáng)度），于是可以看成是現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)的一個(gè)合理近似Watts-Strogatz證明了：在這樣的網(wǎng)絡(luò)中，任意兩點(diǎn)之間存在短路徑的概率很高弱連接的隨機(jī)性使其形成閉包的概率很小但也可以證明，Watts-Strogatz模型不能很好地體現(xiàn)第二個(gè)要求搜索路徑太長(zhǎng)，盡管短路徑存在11回顧那個(gè)寄信（搜索）過程每個(gè)人被告知：如果不認(rèn)識(shí)目標(biāo)人，就不能直接寄給他，只能轉(zhuǎn)發(fā)，希望能離目標(biāo)人“近”一些雖然人們是有意識(shí)地希望信能送到，但她若不認(rèn)識(shí)目標(biāo)人（他），就只能“估計(jì)”她的哪個(gè)朋友可能“更接近于”認(rèn)識(shí)他。因此，我們沒有理由認(rèn)為信件會(huì)以很高的概率送到，更沒有理由認(rèn)為它會(huì)走一條短路徑12因此，需要一種社會(huì)網(wǎng)絡(luò)模型既反映任何節(jié)點(diǎn)對(duì)之間短路徑的存在性，也反映這種轉(zhuǎn)發(fā)方式通過短路徑達(dá)到目的的可能性可以證明，Watts-Strogatz模型不能很好地體現(xiàn)第二個(gè)要求重新構(gòu)造一個(gè)模型？擴(kuò)展Watts-Strogatz模型？JonKleinberg,Navigationinasmallworld.Nature,200013思路為什么Watts-Strogatz模型不湊效？體現(xiàn)弱關(guān)系的邊太過于隨機(jī)，不支持現(xiàn)實(shí)中人們會(huì)有意識(shí)向比較接近目標(biāo)的朋友轉(zhuǎn)發(fā)信件的行為的體現(xiàn)每經(jīng)過一步就向目標(biāo)更接近隨機(jī)邊的形成要體現(xiàn)：離得越近，機(jī)會(huì)越多14擴(kuò)展的Watts-Strogatz網(wǎng)絡(luò)模型節(jié)點(diǎn)依然在網(wǎng)格點(diǎn)上排布同質(zhì)性局部連接相同：每個(gè)節(jié)點(diǎn)與在r個(gè)網(wǎng)格步內(nèi)的節(jié)點(diǎn)都有直接的邊對(duì)隨機(jī)遠(yuǎn)程弱連接加以一定的控制：讓兩個(gè)節(jié)點(diǎn)之間存在連接的概率與它們的網(wǎng)格距離的冪次成反比關(guān)系（離得越遠(yuǎn)概率越?。┯沝(v,w)為v到w的距離（網(wǎng)格步數(shù)），則產(chǎn)生一條從v到w的隨機(jī)邊的概率與

d(v,w)-q成正比。理論上可以證明，對(duì)于適當(dāng)?shù)膓，在如此形成的網(wǎng)絡(luò)中的分散搜索有很高的效率（平均步數(shù)短）?！斑m當(dāng)?shù)膓”是多少？支持“有意識(shí)向目標(biāo)轉(zhuǎn)發(fā)”的努力15不同q值對(duì)隨機(jī)連接長(zhǎng)度的影響q值較小，隨機(jī)邊傾向于較遠(yuǎn)（對(duì)距離的“懲罰”小，遠(yuǎn)處的節(jié)點(diǎn)多帶來的優(yōu)勢(shì)明顯）q值較大，隨機(jī)邊傾向于較近Watts-Strogatz模型對(duì)應(yīng)于q=0太近也不好，遠(yuǎn)距離節(jié)點(diǎn)沒了機(jī)會(huì)16該模型的最佳工作參數(shù)理論結(jié)果：當(dāng)q=2時(shí)，分散搜索達(dá)到最佳效果仿真實(shí)驗(yàn)：由幾億個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)中，考察不同的q值在分散搜索中的效果對(duì)于這種規(guī)模的網(wǎng)絡(luò)，在指數(shù)q介于1.5和2.0之間時(shí)搜索效果最佳隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，最佳的性能指數(shù)q越來越接近2橫軸為參數(shù)q，縱軸為從一個(gè)節(jié)點(diǎn)到達(dá)另一個(gè)節(jié)點(diǎn)所需的平均時(shí)間（跳步）Nature200017d-q:為什么q=2時(shí)模型效果最佳？考慮節(jié)點(diǎn)v隨機(jī)落到距離在d到2d環(huán)內(nèi)區(qū)域的概率節(jié)點(diǎn)數(shù)與d2成正比（均勻分布，節(jié)點(diǎn)數(shù)與面積成比例）q=2意味著隨機(jī)連接到其中一個(gè)節(jié)點(diǎn)的概率與d-2成比例因此從v發(fā)出的隨機(jī)連接落到該區(qū)域的概率與d無關(guān)意味著（1）無論一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)相距多遠(yuǎn)，他都可能有一個(gè)離目標(biāo)距離近一半的朋友；（2）信件離目標(biāo)越近，與目標(biāo)有邊的可能性就越大節(jié)點(diǎn)數(shù)與d2成正比，連接到每個(gè)節(jié)點(diǎn)的概率與d-2成正比，于是到這個(gè)區(qū)域的概率與d無關(guān)這也意味著遠(yuǎn)程朋友數(shù)在人口數(shù)中的占比隨距離平方遞減18模型的驗(yàn)證與推廣大規(guī)模在線社會(huì)網(wǎng)絡(luò)是否（如何）體現(xiàn)了這個(gè)（Watts-Strogatz-Kleinberg）網(wǎng)絡(luò)的特點(diǎn)？如果沒有體現(xiàn)，則可能說明這個(gè)網(wǎng)絡(luò)作為社會(huì)網(wǎng)絡(luò)的模型還不夠好，否則就是對(duì)模型可靠性的支持什么是需要驗(yàn)證的特點(diǎn)？從地理上看，一個(gè)節(jié)點(diǎn)在任一距離范圍的朋友數(shù)量（對(duì)應(yīng)連接）在同等距離上網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)中的占比（對(duì)應(yīng)于概率）隨距離按反平方遞減如果是，則說明隨機(jī)形成的社會(huì)網(wǎng)絡(luò)可能具有某種本質(zhì)的參數(shù)！但是，在線社會(huì)網(wǎng)絡(luò)如何體現(xiàn)均勻地理位置關(guān)系？不同節(jié)點(diǎn)的同“距離”圈中的節(jié)點(diǎn)數(shù)相同19LiveJournal（LJ），1999年建立的社交網(wǎng)站20來自LiveJournal的實(shí)驗(yàn)數(shù)據(jù)50萬用戶，含郵政編碼信息（地理信息）但他們是不均勻分布的，不符合模型的假設(shè)，需要做一些“適配性”工作依據(jù)地理信息定義一個(gè)節(jié)點(diǎn)相對(duì)于另一個(gè)節(jié)點(diǎn)的排名節(jié)點(diǎn)w在節(jié)點(diǎn)v眼里的排名，rank(w)等于網(wǎng)絡(luò)中比w離v近的節(jié)點(diǎn)的個(gè)數(shù)。LiveJournal中用戶的地理位置分布同一排名含同樣多節(jié)點(diǎn)，統(tǒng)一了不同密度的區(qū)域21社會(huì)網(wǎng)絡(luò)中結(jié)合地理位置信息的節(jié)點(diǎn)排名可以看成是節(jié)點(diǎn)在地理上均勻分布時(shí)區(qū)域范圍概念的一種推廣，“排名”與“距離”有對(duì)應(yīng)關(guān)系這就使我們能一般性地處理節(jié)點(diǎn)在地理上分布不均勻的問題了22這樣要驗(yàn)證的是從地理上看，一個(gè)節(jié)點(diǎn)在任一距離上的朋友數(shù)量在同等距離節(jié)點(diǎn)總數(shù)中的占比隨距離按反平方遞減（1/d2）此時(shí)等價(jià)于看一個(gè)節(jié)點(diǎn)在任一排名上的朋友（即有連接）數(shù)量在同等排名節(jié)點(diǎn)總數(shù)中的占比隨排名成反比（1/r）近乎完美的驗(yàn)證?。≒NAS,2005）真實(shí)社會(huì)網(wǎng)絡(luò)的測(cè)量參數(shù)與模型最優(yōu)參數(shù)相當(dāng)吻合！這意味著，大量微觀社交關(guān)系的建立總體上呈現(xiàn)一種最優(yōu)化特征，或者說大量人群的隨機(jī)社會(huì)活動(dòng)相當(dāng)于一臺(tái)計(jì)算機(jī)，完成了一種優(yōu)化計(jì)算（實(shí)現(xiàn)了最優(yōu)參數(shù)）－－社會(huì)計(jì)算！一個(gè)計(jì)算思維實(shí)例！也是體現(xiàn)社會(huì)系統(tǒng)中微觀與宏觀關(guān)系的實(shí)例！23MySpace上朋友數(shù)與地理距離成反比2425Zhu&Li(2005)互聯(lián)網(wǎng)的地域性虛擬空間距離與現(xiàn)實(shí)空間距離的等價(jià)性進(jìn)一步考察網(wǎng)絡(luò)模型與社會(huì)網(wǎng)絡(luò)的關(guān)系Watts-Strogatz-Kleinbeig網(wǎng)絡(luò)模型試圖反映的社會(huì)網(wǎng)絡(luò)特征由某種“親近”（相似性）形成的近距離邊隨機(jī)的遠(yuǎn)距離弱聯(lián)系邊遠(yuǎn)程相鄰節(jié)點(diǎn)的數(shù)量在同距離節(jié)點(diǎn)數(shù)中的占比隨距離的平方減少距離，是其中一個(gè)關(guān)鍵概念地理空間位置的關(guān)系體現(xiàn)最直接的距離概念節(jié)點(diǎn)的相對(duì)排名也體現(xiàn)了一種距離概念，克服了處理節(jié)點(diǎn)在地理空間上分布不均勻情形的困難在社會(huì)網(wǎng)絡(luò)中，還有什么有意義的距離概念？跳數(shù)？意義在哪里？我們需要“社會(huì)意義”26社團(tuán)（socialfoci，社交聚點(diǎn)）與距離一個(gè)人可能參加多種社團(tuán)（組織機(jī)構(gòu)，興趣愛好群體等），社團(tuán)是兩人建立關(guān)系的一個(gè)基礎(chǔ)（社團(tuán)閉包）可以想象，兩人的親近程度（“距離”）與社團(tuán)的規(guī)模有關(guān)，越小越近定義“社會(huì)距離”：兩人同屬最小社團(tuán)的規(guī)模。V屬于5個(gè)大小分別為2，3，5，7，9的社團(tuán)27進(jìn)一步如同排名，可以建立（現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)）中的社會(huì)距離與Watts-Strogatz-Kleinbeig網(wǎng)絡(luò)空間距離之間的對(duì)應(yīng)關(guān)系從而我們可以來考察以社會(huì)距離度量人們之間親近關(guān)系的真實(shí)社會(huì)網(wǎng)絡(luò)中是否也體現(xiàn)了Watts-Strogatz-Kleinbeig網(wǎng)絡(luò)的第三條性質(zhì)Adamic和Adar以惠普實(shí)驗(yàn)室人員的email數(shù)據(jù)為對(duì)象進(jìn)行的分析表明，該性質(zhì)體現(xiàn)明顯：社會(huì)距離為r的員工之間產(chǎn)生連接的概率與r-3/4成比例節(jié)點(diǎn)：?jiǎn)T工；邊：一段時(shí)間內(nèi)交換過郵件社團(tuán)：惠普實(shí)驗(yàn)室的管理層次結(jié)構(gòu)SocialNetworks,200528Email聯(lián)系與組織機(jī)構(gòu)層次的疊加分析29領(lǐng)結(jié)模型的OUT

IN要多少步？30茶壺模型(Zhuetal.,2008)葵花模型(Donatoetal.,2005)領(lǐng)結(jié)模型(Broderetal.,2000)SCC:緊密互聯(lián)的分支IN:單向連接SCC的分支OUT:SCC單向連接的分支Tendril:與SCC無關(guān)的分支全球網(wǎng)歐亞八國中文網(wǎng)