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

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

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

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

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

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

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

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