社會(huì)網(wǎng)絡(luò)動(dòng)態(tài)性及網(wǎng)絡(luò)環(huán)境中的分布式搜索策略研究.pdf

1、社會(huì)網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)的一支，它以社會(huì)生活中人類或組織的行為活動(dòng)為研究對(duì)象，將其抽象為相互作用的個(gè)體組成的網(wǎng)絡(luò)。這樣的網(wǎng)絡(luò)無(wú)處不在，并且與我們的生活密切相關(guān)，如演員合作網(wǎng)絡(luò)、科學(xué)家合作網(wǎng)絡(luò)、恐怖分子網(wǎng)絡(luò)、疾病傳染網(wǎng)絡(luò)以及虛擬社會(huì)網(wǎng)絡(luò)等等。通過(guò)研究社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)和性質(zhì)，可以幫助我們更深刻的理解社會(huì)現(xiàn)象，對(duì)現(xiàn)實(shí)中的決策、管理、優(yōu)化問(wèn)題都有極其重要的意義。
　　 傳統(tǒng)的社會(huì)網(wǎng)絡(luò)研究是以靜態(tài)的觀點(diǎn)分析網(wǎng)絡(luò)結(jié)構(gòu)，例如網(wǎng)絡(luò)的度分布、平均最短距離

2、、聚類系數(shù)等。但是真實(shí)的社會(huì)網(wǎng)絡(luò)是一個(gè)不斷進(jìn)化的系統(tǒng)，內(nèi)部個(gè)體不斷相互作用，個(gè)體之間的關(guān)系以及屬性也是動(dòng)態(tài)變化的，與之相應(yīng)，網(wǎng)絡(luò)的整體拓?fù)浣Y(jié)構(gòu)、網(wǎng)絡(luò)性能、以及基于網(wǎng)絡(luò)的各種行為都是動(dòng)態(tài)變化的。社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)特性在近些年才開始被重視起來(lái)，Carley專門提出了動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)(Dynamical Social Network)的概念，指出社會(huì)網(wǎng)絡(luò)的最重要特性即動(dòng)態(tài)性，并試圖建立一個(gè)組織模型來(lái)研究社會(huì)網(wǎng)絡(luò)內(nèi)信息以及決策流的特征。與社會(huì)網(wǎng)絡(luò)動(dòng)態(tài)性

3、的外在表現(xiàn)相比，人們更好奇的是網(wǎng)絡(luò)動(dòng)態(tài)性的來(lái)源，即網(wǎng)絡(luò)演化動(dòng)力學(xué)。社會(huì)網(wǎng)絡(luò)研究的一個(gè)目標(biāo)是理解網(wǎng)絡(luò)上各種動(dòng)力學(xué)與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的關(guān)系，而網(wǎng)絡(luò)的形成方式和演化機(jī)制決定網(wǎng)絡(luò)的結(jié)構(gòu)，因此研究網(wǎng)絡(luò)演化機(jī)制模型成為社會(huì)網(wǎng)絡(luò)的研究前提和熱點(diǎn)。這也是本文的任務(wù)之一。
　　 與傳統(tǒng)方法不同，我們通過(guò)分析社會(huì)網(wǎng)絡(luò)中個(gè)體的動(dòng)態(tài)性，認(rèn)為個(gè)體屬性呈一種隨時(shí)間衰減的動(dòng)態(tài)變化規(guī)律，并可以通過(guò)外部刺激增強(qiáng)，我們稱之為社會(huì)網(wǎng)絡(luò)中的記憶效應(yīng)。記憶效應(yīng)的存在是導(dǎo)致網(wǎng)

4、絡(luò)拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)性的內(nèi)在原因和網(wǎng)絡(luò)演化的重要?jiǎng)恿??；趥€(gè)體動(dòng)態(tài)性的分析，我們提出社會(huì)記憶網(wǎng)絡(luò)動(dòng)態(tài)模型，其中個(gè)體的吸引度隨時(shí)間以指數(shù)衰減，吸引度可以通過(guò)增加新連接的方式增強(qiáng)，而個(gè)體每次增加新連接的概率正比于其動(dòng)態(tài)變化的吸引度。由此而生成的社會(huì)記憶網(wǎng)絡(luò)不僅具備了小世界和無(wú)標(biāo)度特性，同時(shí)也具有動(dòng)態(tài)演化的新舊交替式的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，反應(yīng)了真實(shí)網(wǎng)絡(luò)的動(dòng)態(tài)過(guò)程。我們采用真實(shí)數(shù)據(jù)對(duì)模型進(jìn)行了驗(yàn)證并分析了網(wǎng)絡(luò)中的記憶特性對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和性能產(chǎn)生的影響。同時(shí)當(dāng)

5、記憶特性消失(衰減指數(shù)為0)時(shí)網(wǎng)絡(luò)退化為經(jīng)典的BA模型[35]，因此可以說(shuō)，社會(huì)記憶網(wǎng)絡(luò)模型更具一般性。
　　 由于社會(huì)記憶網(wǎng)絡(luò)中記憶特性的存在，網(wǎng)絡(luò)中出現(xiàn)一批屬性如熱度(泛指社會(huì)網(wǎng)絡(luò)中的吸引度、影響力等屬性)只在某一時(shí)間段出現(xiàn)峰值的節(jié)點(diǎn)，而對(duì)于較長(zhǎng)的時(shí)間段而言，這些熱度最高的節(jié)點(diǎn)又是隨時(shí)間動(dòng)態(tài)變化的。這種節(jié)點(diǎn)在特定階段具有很強(qiáng)的影響力，對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的演化、網(wǎng)絡(luò)中信息流通性能都具有重要的意義。在應(yīng)用和分析中，我們常需要知曉它們

6、在網(wǎng)絡(luò)中的位置，而社會(huì)網(wǎng)絡(luò)通常是很龐大的網(wǎng)絡(luò)，如何在這樣復(fù)雜的動(dòng)態(tài)大型網(wǎng)絡(luò)中發(fā)現(xiàn)并追蹤熱度最高的節(jié)點(diǎn)也成為一個(gè)挑戰(zhàn)性的課題。
　　 針對(duì)這一問(wèn)題，我們提出基于面向自治計(jì)算(AOC)的分布式搜索方法來(lái)尋找追蹤網(wǎng)絡(luò)中的這些重要節(jié)點(diǎn)。每個(gè)智能體作為一個(gè)獨(dú)立的計(jì)算單元，僅僅在其局部環(huán)境中搜索，但是通過(guò)與環(huán)境和智能體相互之間的作用，在自身行為規(guī)則的引導(dǎo)下可以實(shí)現(xiàn)從局部環(huán)境自治的向全局目標(biāo)逼近，并最終找到網(wǎng)絡(luò)中的重要節(jié)點(diǎn)。在基于AOC方法的

7、基礎(chǔ)上，我們?cè)O(shè)計(jì)了多種具體的搜索策略，包括三種局部移動(dòng)搜索策略、Levy Flight搜索策略以及可變概率搜索策略，并分析了各種策略的內(nèi)在機(jī)理和搜索性能，包括搜索效率、魯棒性、尺度可變性和時(shí)間復(fù)雜度。我們采用BBS網(wǎng)絡(luò)的真實(shí)數(shù)據(jù)對(duì)算法進(jìn)行測(cè)試驗(yàn)證，分析結(jié)果表明，基于AOC的搜索策略可以在大型的、動(dòng)態(tài)的、離散式的網(wǎng)絡(luò)環(huán)境中表現(xiàn)出優(yōu)秀的搜索性能。除此之外，我們還建立了三種不同的人工網(wǎng)絡(luò)環(huán)境測(cè)試，相應(yīng)的搜索策略亦達(dá)到良好的搜索效果。因此，我們