社會網絡動態性及網絡環境中的分布式搜索策略研究.pdf

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

2、、聚類系數等。但是真實的社會網絡是一個不斷進化的系統，內部個體不斷相互作用，個體之間的關系以及屬性也是動態變化的，與之相應，網絡的整體拓撲結構、網絡性能、以及基于網絡的各種行為都是動態變化的。社會網絡的動態特性在近些年才開始被重視起來，Carley專門提出了動態社會網絡(Dynamical Social Network)的概念，指出社會網絡的最重要特性即動態性，并試圖建立一個組織模型來研究社會網絡內信息以及決策流的特征。與社會網絡動態性

3、的外在表現相比，人們更好奇的是網絡動態性的來源，即網絡演化動力學。社會網絡研究的一個目標是理解網絡上各種動力學與網絡拓撲結構的關系，而網絡的形成方式和演化機制決定網絡的結構，因此研究網絡演化機制模型成為社會網絡的研究前提和熱點。這也是本文的任務之一。
　　 與傳統方法不同，我們通過分析社會網絡中個體的動態性，認為個體屬性呈一種隨時間衰減的動態變化規律，并可以通過外部刺激增強，我們稱之為社會網絡中的記憶效應。記憶效應的存在是導致網

4、絡拓撲結構的動態性的內在原因和網絡演化的重要動力?；趥€體動態性的分析，我們提出社會記憶網絡動態模型，其中個體的吸引度隨時間以指數衰減，吸引度可以通過增加新連接的方式增強，而個體每次增加新連接的概率正比于其動態變化的吸引度。由此而生成的社會記憶網絡不僅具備了小世界和無標度特性，同時也具有動態演化的新舊交替式的網絡拓撲結構，反應了真實網絡的動態過程。我們采用真實數據對模型進行了驗證并分析了網絡中的記憶特性對網絡結構和性能產生的影響。同時當

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

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

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