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

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

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

個體間“社會距離”的度量

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

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

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

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

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

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

-定義m-維歐式空間

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

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

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

-信息實際路由路徑和最短路由路徑的比例

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

長程連邊的作用

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

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