模塊化無標度網絡模型的建立與仿真分析畢業設計(論文)(編輯修改稿)

　

【文章內容簡介】 式可等價定義為 相連的三元組的數量與節點 相連的三角形的數量與節點 ii?iC （ 24） “ 與 頂 點 i 連接 的三元組 ” 是指 涵蓋頂 點 i 的三個 頂 點，并 存在 從 頂 點 i 到 其他兩個 頂 點的兩條邊。 度與度分布 經過科學家們數年的努力，我們發現度是描述節點特征的主要指標。 節點 ik 的度是 說 與節點 ik 連接的結點 個數 。對于有向網絡，節點的度 又 分為出度和入度。 節點的出度是 指 該節點指向其 它 節點的邊的數目 。 節點的入度是指從其 它 節點指向該節點的邊的數目。 通俗來講，節點的度越大就意味著這個節點在這個系統中 連接的節點越多， 扮演的角色 越重要 。 我們把一個 網絡中所有 包含的 節點的度的平均值 叫做該 網絡的平均度，用 k表示。網絡中節點的度的分布情況可用函數 )(kp 來描述 。一種說法是， )(kp 表示在 一個系統 中隨機選擇的 頂 點的度為 k 的概率 。 另 一種 說法 是 系統 中 頂 點度數為 k 的 頂 點數 與頂 點總數的 比 。 完全隨機網絡的度分布近似其 形態 在 距離最大 值 k 很遠的地方 處呈指數下降。這意味著 并不存在 ????kk 的節點，這樣的網絡叫做均勻網絡 。 經過許多科學家證明 ，許多實際網絡的度分布 事實上不 符合 泊松 分布，而是符合冪率分布。 南華大學計算機科學與技術學院畢業設計（論文） 我們把任意挑選到的頂 點 的 度數為 k 的概率 , 記為 )(kp ,k 為度數 ,可以更直觀的告訴我們該節點在該系統中所扮演的角色。 除了這三種最基本的統計 屬性 以外， 復雜網絡還具有許多與傳統網絡， ER 網絡等網絡不一樣的統計特征，這里面 最 值得關注 的莫過于小世界性，和無標度 屬性 。經過長期的研究表明，規則網絡具有比較大的劇烈系數，和較大的平均路徑長度：隨機網絡具有較小的聚類系數和小的平均路徑長度。而后，科學家 Watts 和 Strogatz開創了以后新的 理論， 以 一 個很小的概率 p ，打 斷規則網絡中原 有 的邊， 然后 隨機選擇新的節點重新連接在一起， 就形成了 一 個 新的網絡 。這個網絡與我們過去所研究的 ER 網絡和規則網絡均不相同 ，介于他們二者之間。 它具有大的聚類系數和小的平均路徑長度 。 往后，科學家把這種特性的定義為小世界性，把這種網絡定義為小世界網絡 ，如圖 所示 。 圖 小世界網絡拓撲結構圖 往后， 在漫長的實驗道路中 ，科學家們發現真實網絡都具有小世界性 。 同時，科學家們還發現真實網 絡的節點 按照 冪律分布 。 這里 的頂 點的度是指該 頂 點所 具 有的 連接 節點的 個數 。節點服從冪律分布是指， 可以用一個冪律函數近似的表示該節點與該特性的度之間的聯系。 冪律函數曲線 如圖 所示，是一條緩慢滑坡的曲線 ，這就告訴我們，在這個網絡中可以找到度很大的節點。 圖 BA 網絡度分布圖 南華大學計算機科學與技術學院畢業設計（論文） 對于傳統的規則網絡和隨機網絡 來說 ，度 值在一個很狹窄的區間內取值，所以我們基本找不到和平均度值相差較大的節點。那么我們就可以把度看做是考察一個節點的重要指標 。 我們就把這種頂點的度的分布滿足冪律分布的網絡叫做無標度網絡，把這 種特性叫做無標度特性，如圖 所示 。 圖 無標度網絡拓撲結構圖 除了 上文介紹的 小世界性和無標度性，真實網絡還存在許多統計上的特性，如，混合模式特性，度相關性，超小世界性等，有興趣的讀者可以查閱相關文獻。在此，不一一介紹。 典型無標度模型介紹 由上文我們可以知道，在小世界網絡的研究興起之后， 后期有大量的科研學者投身到復雜網絡的研究中。他們發現許多現實網絡在統計特性上存在普遍共性，其中最顯著的就是他們的節點度分布都服從冪律分布 。 這一發現逐漸演化成無標度網絡， 形成了無標度網絡模型的建立，最 具代表性的便是經典 BA 無標度網絡模型。 BA 模型 源于對科學的熱愛，對真理的探索， 1998 年， Barabasi 和 Albert 等開展了一項關于萬維網 (World Wide Web)的研究。 他們本認為其結果應該是一個符合隨機網絡的“鐘形圖”，即泊松分布，但是他們卻發現結果天壤之別。 Inter 上網頁基本由少數幾個高連通的頁面相互串接。只有不到 20%的頁面連接大于 4，其他均小于 4。這些有高連通的頁面卻只占整個網絡的極小部分，只有不到萬分之一。他們計算了 k 個南華大學計算機科學與技術學院畢業設計（論文） 連接著 Inter 的頁面，發現這些頁面 的連接也遵從冪律分布。 于是 在 1999 年， Barabasi和 Alberty提出了史上最重要的一種離婚，即構造無標度網絡的演化模型。他們也采取了與 Price 相類似的辦法。 Barabasi 和 Albert 認為隨機網絡之所以不能解釋集散節點存在的原因 ： 是因為隨機網絡 不 能 表現 現實網絡中的兩個重要 屬性 ：第一，增長特性，我們的現實網絡每天都不在不斷變化，每天都有新的節點產生并加入到我們的網絡中來，每天也都有舊的節點消失，我們的網絡也是通過不斷演化，更新而來的，而隨機網路在安置連接之前能夠得到所有的網絡節點，而節點數在網絡 中是固定的，一成不變的 。第二，優先連接機制，隨機模型都假設在添加新的連接時，概率都是均勻的，而事實上卻不是如此，許多真實網絡都是擇優連接的 。 例如 Inter， 人們 在選擇頁面連接到何處時， 本 可從多達數億的網站中選擇，但是我們大部分人 僅僅 熟悉 Inter 中的一小部分，例如 百度，酷狗這些網 頁，這一小部分分 事實上 含有連接 度 較多的網站，只要我們連接到這些節點，便可以連接到數以萬億的其他節點，這一偏好就等同于增強了他們的偏好，這種“擇優連接”的過程，也發生在其他網絡當中。比如在好萊塢，連接著關系較多的 明星往往更 便于 得到 新銳們 的 關注。又比如 在我們 每天所使用 的互聯網上， 一些 端口 很多的路由器 由于擔負著繁重的工作，一般情況下會 被分配到更多的帶寬， 以便更好的工作，服務于社會。因此 我們便更喜歡 把自己的電腦 連接到這些路由器上 ，從而得到更快，更高效的網絡服務 。 我們可以通過 圖 來更好的理解 。 圖 真實網絡示意圖 在過去，我們常常說在我們的網絡節點集散中，出現了“富者更富”的現象。這又是為什么呢？無標度網絡模型給出了解釋。介于增長特性和優先連接機制的出現，當網絡中有新的節點產生時，他在選擇自己的連接對象時比較喜歡和已經 有較南華大學計算機科學與技術學院畢業設計（論文） 多連接的節點相連接。正如我們在生活中，如果讓我們選擇交朋友的對象，恐怕許多人都會選擇已經有很多朋友的人來建立關系。隨著時間的推移，這種趨勢愈發明顯，從而造成了集散現象的產生。顯然，我們可以推論“富者更富”現象在以往的隨機網絡中是不可能出現的。 隨著 BA 模型的發明與廣泛推廣，復雜網絡的歷史又翻開了一頁新的篇章。人們在網絡研究的歷史長河中鑄就了新的里程碑。此后，有更多的學者開始了對復雜網絡的研究與探索，他們提出了諸如加速增長，局域時間，網絡老化，網絡適應性以及非線性優先連接機制等。但是我們必須承認一點 ，我們只能說絕大多數網絡是無標度網絡，而不能一概而論的說所有的現實網絡都是無標度網絡，還有小部分網絡服從指數分布，截斷形式等，這也是我們研究的科學性所在。如圖 就是一個冪律分布的網絡。 圖 典型的具有冪律分布的網絡 蛋白質網絡 模塊化無標度網絡模型 我們在漫長的學習與探索過程中，明白一個道理。即使是大家普遍認同的，我們也不能一概而論的，更不能斷章取義。我們在上文中說，許多現實的系統網絡都有小世界性和無標度性，換言之他們具有許多共同的全局結構特征。但是，他們還是有區別的，要 不然我們怎么能說他們終究是不同的網絡，在局部方面看，各個網絡還是各有異同的。于此，我們就必須再了解這些網絡的局部所存在不一樣的地方，探討這些不同產生的機理，過程，后期的發展狀況。舉個例子，我們生物界的細胞網絡，細胞是靠各種功能聯系在一起的，功能類似的細胞高度集中，形成了一個團南華大學計算機科學與技術學院畢業設計（論文） 體，我們把這個團體叫做模塊。那么到底什么是模塊呢？一般的定義是，一組物理性質或者功能性質而聚集在一起，共同工作，從而完成一個特例的功能的節點。在我們生活中許多地方，都具備了模塊。比如說，我們現在所熟知的 FACEBOOK，博客，微博，都是 由許多有共同興趣的人聚集在一起的：再比如說，在一個汽車的制造過程中，不管是發動機，還是輪胎，都是由一個特定的群體專業生產制造的，所以說高度模塊化在我們的生活中隨處可見，而模塊化的工作，生活，是現代社會的必要的產物。 例如 在生物系統中 ，相對固定的 核糖核酸 和 脫氧核糖核酸 ，就是我們生命活動的基礎 。事實上，一個系統中的絕大多數分子或者是具有模塊化活動的一個細胞內的聯合體的一部分（如核糖體），或者是參與到一個功能上的更廣的模塊以作為一個相對獨立過程的調控單元（如信道中的信號放大）。 那么網絡中的模塊是如何構成的呢？近期 的研究表明，模體可能是復雜網絡的基本模塊 ，也就是我們所說的基本組成部分 。 假設兩個網絡具有相同的規模，那么無標度網絡要比隨機網絡具有較高的聚類系數，即我們所說的高聚類行。所謂的高聚類行就是指這個網絡的某一部分，由各種高度鏈接的頂點組成，成型一個團體也就是模塊，而這也正是出現某一個功能模塊的前提。在一個網絡內部的某個模塊顯示了這個網絡在一定層次上的鏈接模式。盡管如此，但是這么多模塊也不是所有的模塊都是重要模塊的。在一個復雜網絡中，可以包括各種各樣的模塊，如三角形模塊，正方形模塊，菱形模塊等。其中的一些模塊所占的 比例很高，而另一些模塊卻占有較低的比例。這些比例高的模塊就叫做模體。我們知道，一個復雜網絡都是由他內部特定的模塊所表示的，那么如果我們可以清晰準確的辨識出這些模塊，就有利于我們了解這個網絡的局部特征，進而了解整個網絡。 南華大學計算機科學與技術學院畢業設計（論文） 第三章 BA 模型與模塊化模型算法比較 BA 模型 通過上文的介紹，我們知道隨機網絡和“小世界”網絡的度分布遵從泊松分布。該分布的特點主要表現在在其均值處有一個峰值，而兩側則呈現出逐漸遞減，導致這樣的網絡在后來也被稱為指數網絡（ exponential works）。隨著科技的發展 ，技術的進步，后來人們提出了復雜網絡的概念，例如我們熟悉的萬維網，互聯網，英特網等，以及生物界的神經系統網，生物體的新陳代謝網等的節點的度分布都遵從冪律分布。由于這種網絡的頂點關聯方式并沒有顯著的特別屬性，我們就把他們稱為無標度網絡。 為了進一步給大家解釋這種網絡中節點的度分布服從冪律分布的現象，Barabasi和 Albert 創造了一個無標度網絡模型，就是我們現在所廣泛研究的 BA 無標度網絡模型。 BA 模型的特性 在現實意義中，我們知道一個網絡具有冪律度分布固然是有意義的，但是更為重要的是我們要理 解冪律分布的產生機理。由 Barabasi 和 Albert 創建的 BA 無標度網絡模型實際上闡述了真實網絡的兩個重要特性 : (1) 增長特性： 我們的網絡每天都在變化，用戶每天都在增加與退出，網上的網站也在每天更新，每天都有新的頁面產生，有舊的頁面撤除。再例如，每天都有新的車輛上戶，也有舊的車輛報廢 ； 每天都有新的想法產生等等。所以說，我們的網絡規模在不斷增長。 而 ER 隨即圖和 WS 小世界模型中網絡節點數是固定的，這不符合實際網絡的發展規律。 （ 2）優先連接特性： 每當有新的節點加入到已知網絡中時，他們在選擇鄰居的時候都愿意選擇 那些已經有很多節點連接的節點作為自己的鄰居，也就是我們所說的“馬太效應”或者說“富者更富”現象。舉個例子，我們在做畢業設計時，我們喜南華大學計算機科學與技術學院畢業設計（論文） 歡參考借鑒那些名人學者的學術研究報告。在我們的朋友圈中，可能很多人都認識某幾個特別受歡迎的人，但是這些人互相卻并不認識。 而在 ER 隨即圖中，兩個節點之間是否有邊相連是完全隨機確定的，在 WS 和小世界模型中，長程邊的端點也是完全隨機確定的。 BA 模型的算法 1）增長性：開始 時創建 少量節點 0m ，在每個時間間隔添加一個具有 ? ?0mm?條邊的新節點（連接到已存在于系統中的 m 個節點上）。 2）擇優連接： 當選擇與新節點連接時，假設新節點連接到節點 i的概率 ? 取決于該節點的連通度 ik ，即 ? ? .??i iii kkk? （ 31） 經過這樣的計算后，我們在經過 t時刻以后，就可以得到一個 tmN ?? 0 ， mt條邊的 BA無標度網絡模型。我們可以看到網絡整體上呈現冪律分布 ??kP ： ??k ，冪指 數 3?? 。這個結果在后來的多種理論方法和實驗結構都得到了證明，實驗結果如圖 。 圖 BA網絡度分布圖 南華大學計算機科學與技術學院畢業設計（論文） 模塊化無標度網絡模型 隨著 近 年來對許多實際網絡的研究及探索，人們發現，他們