復(fù)雜網(wǎng)絡(luò)形成機制及建模研究

復(fù)雜網(wǎng)絡(luò)形成機制及建模探討報告人:曹繼偉導(dǎo)師:劉玉華教授華中師范大學(xué)計算機科學(xué)系2005年3月1復(fù)雜網(wǎng)絡(luò)現(xiàn)象復(fù)雜網(wǎng)絡(luò)出現(xiàn)在自然系統(tǒng)或人造系統(tǒng)的各個領(lǐng)域2復(fù)雜網(wǎng)絡(luò)現(xiàn)象(續(xù))Internet(路由器，線路)WWW(web頁面，超連接)文章合作網(wǎng)絡(luò)(作者，合作關(guān)系)食物鏈(動物，捕食關(guān)系)化學(xué)反應(yīng)(分子，發(fā)生化學(xué)反應(yīng))……3復(fù)雜網(wǎng)絡(luò)的形成機制自組織 孤立個體 優(yōu)先粘貼 生長涌現(xiàn)高層次個體高層次增長

4網(wǎng)絡(luò)增長的層次性網(wǎng)絡(luò)生長具有兩個方向：自上而下、自下而上高層主體－高層主體低層主體－低層主體高層主體－底層主體5復(fù)雜網(wǎng)絡(luò)形成的約束機制老節(jié)點的年齡建立連接的成本和節(jié)點的連接容量節(jié)點類型因素

6復(fù)雜網(wǎng)絡(luò)建模規(guī)則DavidJ.Aldous提出建立復(fù)雜網(wǎng)絡(luò)模型應(yīng)當(dāng)遵循三條原則：形式化即對任何一個系統(tǒng)都要找到一個合理的數(shù)學(xué)公式來描述適應(yīng)性即通過適當(dāng)?shù)卣{(diào)整模型的參數(shù)能夠得到模型統(tǒng)計參數(shù)的變化自然性即網(wǎng)絡(luò)模型的統(tǒng)計屬性應(yīng)該自然演化自一些簡單的數(shù)學(xué)結(jié)構(gòu)，而不是在模型中定義的7幾個重要的復(fù)雜網(wǎng)絡(luò)模型隨機網(wǎng)絡(luò)模型小世界網(wǎng)絡(luò)模型無標(biāo)度網(wǎng)絡(luò)模型8隨機網(wǎng)絡(luò)模型Input:(n,p)n是節(jié)點個數(shù)，p是邊出現(xiàn)的概率。算法

從n個孤立點開始對任意一對頂點，以概率p連接。9隨機網(wǎng)絡(luò)的特征(1)聚集系數(shù)較小；(2)網(wǎng)絡(luò)平均距離??；(3)節(jié)點度服從Poisson分布。隨著概率p從0到1逐漸增加，網(wǎng)絡(luò)的某些性質(zhì)會突然出現(xiàn)。10Watts-Strogatz小世界模型Input:(n,k,p)n是網(wǎng)絡(luò)節(jié)點數(shù)。每個節(jié)點與自己的第k個鄰居建立無向連接。p是每條邊被重置的概率。算法(1)初始化時，n個初始節(jié)點均勻分布在圓周上，每個節(jié)點與自己的第k個鄰居建立連接(2)對每條初始化后的邊，以概率p用一條隨機邊取代。11Watts-Strogatz小世界模型（續(xù)）規(guī)則小世界隨機P＝0P＝1隨機性增強12無標(biāo)度網(wǎng)絡(luò)模型Input:(n0,m,t)n0是網(wǎng)絡(luò)的初始節(jié)點數(shù)。m(m≤n0)是每當(dāng)一個新節(jié)點接入到網(wǎng)絡(luò)中，該新節(jié)點所帶的連接數(shù)。t表示接入的新節(jié)點的個數(shù)。算法:(1)初始化，引入n0個孤立節(jié)點(2)對下面步驟執(zhí)行t次：加入一個新節(jié)點v，v帶有m條邊連向已存在于網(wǎng)絡(luò)中的m個節(jié)點。對任意一個已存在節(jié)點i，它與v建立連接的概率是：

p(ki)(p(ki)=ki/∑kj)。

13用模擬的方式動態(tài)建模網(wǎng)絡(luò)在t時刻的狀態(tài)無法用精確的解析表達式來預(yù)測。無法通過構(gòu)建系統(tǒng)的目標(biāo)解析函數(shù)來優(yōu)化系統(tǒng)性能。14復(fù)雜網(wǎng)絡(luò)動態(tài)建模過程如何計算已有節(jié)點被新節(jié)點選擇的概率（考慮度、距離、成本等）適當(dāng)引入隨機因素新加入節(jié)點帶來的某些邊隨機連向已有節(jié)點。15