小世界網(wǎng)絡(luò)上導(dǎo)航能力的自組織涌現(xiàn)

小世界網(wǎng)絡(luò)上導(dǎo)航能力的自組織涌現(xiàn)高雅純2012.2.22報(bào)告提綱

小世界網(wǎng)絡(luò)上的導(dǎo)航

個(gè)體間“社會距離”的度量

導(dǎo)航能力的度量

基于Watts-Strogatz小世界網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果

基于無標(biāo)度網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果

總結(jié)小世界網(wǎng)絡(luò)上的導(dǎo)航“六度分離”實(shí)驗(yàn)Travers&Milgram,Sociometry32,425,19691.選取一個(gè)人作為信件投遞目標(biāo)；2.個(gè)人投遞給最可能知道投遞目標(biāo)的朋友小世界網(wǎng)絡(luò)上的導(dǎo)航在線社會網(wǎng)絡(luò)搜索實(shí)驗(yàn)

過程：>6萬email用戶投遞到13個(gè)國家中的18個(gè)目標(biāo)用戶，通過認(rèn)識的人進(jìn)行轉(zhuǎn)發(fā)

結(jié)論：成功到達(dá)目標(biāo)的平均路徑長度為4.05。不需要“中心”節(jié)點(diǎn)的存在（也就是可以去中心化），長程連邊（也就是弱連接）起到關(guān)鍵作用P.Doddsetal.Science301,827,2003貪婪投遞與社會距離信息投遞是一個(gè)貪婪路由過程，每一次信息都傳遞給與目標(biāo)社會距離最近的朋友利用朋友的信息如地理位置、教育、職位，來定義社會距離通過社交網(wǎng)絡(luò)個(gè)體交換信息建立一個(gè)動態(tài)的網(wǎng)絡(luò)，導(dǎo)航以分布式和局域方式構(gòu)造個(gè)體間社會距離的度量隱式空間

-定義m-維歐式空間

-社會距離則是由歐式空間的距離確定，并且信息依據(jù)節(jié)點(diǎn)間社會距離進(jìn)行導(dǎo)航網(wǎng)絡(luò)的自組織嵌入

-節(jié)點(diǎn)i在隱式空間的信息交互速度和位置信息交互終止條件，確定節(jié)點(diǎn)的最終位置導(dǎo)航能力的度量成功的路由率

-成功到達(dá)預(yù)定目標(biāo)的信息量和總信息量的比例伸展系數(shù)

-信息實(shí)際路由路徑和最短路由路徑的比例

-所有信息的伸展系數(shù)平均值作為評價(jià)標(biāo)準(zhǔn)基于Watts-Strogatz小世界網(wǎng)絡(luò)WS小世界網(wǎng)絡(luò)，103個(gè)節(jié)點(diǎn)，平均度為10.隱式空間的維度5,10和20，thd=10-4初始速度vi,0從[-0.5,0.5]隨機(jī)抽取，初始位置為p0=0每一個(gè)重連概率的網(wǎng)絡(luò)都進(jìn)行20次實(shí)驗(yàn)，結(jié)果是20次實(shí)驗(yàn)的平均值實(shí)驗(yàn)結(jié)果當(dāng)網(wǎng)絡(luò)顯示小世界特性時(shí)，導(dǎo)航具有高的路由成功率和小的伸展系數(shù)。貪婪路由與隨機(jī)路由的比較

長程連邊的作用

所有信息和成功路由的信息的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間最短路徑分布在隱式空間長程連邊兩個(gè)節(jié)點(diǎn)社會距離相距很遠(yuǎn)

基于一致性網(wǎng)絡(luò)組織嵌入節(jié)點(diǎn)i在隱式空間的信息交互速度和位置節(jié)點(diǎn)i的鄰居域信息交互終止條件，確定節(jié)點(diǎn)的最終位置當(dāng)網(wǎng)絡(luò)顯示小世界特性的時(shí)候，導(dǎo)航具有高的路由成功率和小的伸展系數(shù)基于無標(biāo)度網(wǎng)絡(luò)網(wǎng)絡(luò)規(guī)模：103個(gè)節(jié)點(diǎn)，m=3，連接偏好和標(biāo)度指數(shù):隱式空間的維度為5,10和20，thd=10-4初始速度vi,0從[-0.5,0.5]之間隨機(jī)抽取，初始位置為p0=0每一個(gè)重連概率的網(wǎng)絡(luò)都進(jìn)行20次試驗(yàn)，結(jié)果是20次試驗(yàn)的平均值實(shí)驗(yàn)結(jié)果當(dāng)網(wǎng)絡(luò)顯示小世界特性的時(shí)候，導(dǎo)航具有高的路由成功率和小的伸展系數(shù)總結(jié)基于隱式空間的框架，研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對自組織導(dǎo)航能力的影響通過個(gè)體信息交互，確定個(gè)體間在隱式空間的“社會距離”，并進(jìn)行貪婪路由實(shí)現(xiàn)自組織導(dǎo)航節(jié)點(diǎn)的連接關(guān)系表現(xiàn)出小世界特性時(shí)具有很好的導(dǎo)航能力和