復雜網絡的基本概念、模型及應用

復雜網絡的基本概念、模型及應用

一、復雜網絡的基本概念前面我們在《多主體建模和智能優(yōu)化算法》一文中,介紹過實際網絡,有了這些實際網絡，我們就要對它進行研究。在研究之前，我們必須把它抽象成可以用數學進行描述的問題，即復雜網絡。1.復雜網絡的數學描述網絡G=（V,E），由點集V（G）和邊集E（G）組成的一個圖，可分為無向、有向和加權網絡。令ei∈E（G），每條邊ei有V（G）中的一對點(u,v)與之對應；如果任意(u,v)與(v,u)對應同一條邊，則稱為無向網絡，否則為有向網絡；如果任意∣ei∣=1，則稱為無權網絡，否則為加權網絡。2.無向網絡無向網絡是最簡單的網絡類型，它節(jié)點跟節(jié)點之間的連邊只表示連接關系，無方向的概念，如圖1所示。

圖1無向網絡的鄰接矩陣無向網絡由節(jié)點和連邊構成，我們把節(jié)點和連邊用矩陣進行刻畫。圖1展示了一個非常小的網絡，把它寫成矩陣的形式，實際上是一個4×4的矩陣，由于節(jié)點1和節(jié)點4之間有連邊，我們把矩陣中（1,4）這個地方記為1；節(jié)點2和節(jié)點4有連接，那么第二行第四列我們記為1；節(jié)點3和節(jié)點4是有連接，那么第三行第四列記為1；節(jié)點4和節(jié)點1、2、3都有連接，所以第四行的第1、2、3列都記為1，其他地方是0。這個矩陣就把一個網絡的信息全部記錄下來了，通過數學語言對網絡進行了抽象。對于無向網絡，實際上我們可以對應的把它做一些調整，就可以模擬很多現(xiàn)實中的網絡。3.有向網絡有向網絡是另外一類復雜網絡。例如微博，在微博網絡中，每一個節(jié)點是一個微博用戶，節(jié)點跟節(jié)點之間的連邊表示“關注”關系，由于我粉你，但你不一定粉我，所以連接關系是有向的。同樣的，還有引文網絡，在引文網絡里每一個點是一篇文章，文章跟文章之間的引用關系是有向的，我引用你，你不一定引用我，所以這是有向網絡。對于有向網絡，我們把它抽象成矩陣的形式進行描述。但是，有向網絡與無向網絡在矩陣層面上的最大區(qū)別在于無向網絡的矩陣一定是對稱的，有向網絡的矩陣不一定是對稱的。4.加權網絡加權網絡是更復雜的網絡。我們在實際網絡（社交網絡）中提到科學家跟科學家之間的合作可以抽象成復雜網絡，但其中的連邊可以表示科學家跟科學家的合作次數。在矩陣中，每一行每一列的元素表示合作次數，即數值不一定僅記為1和0，數值大小代表權重。因此，不同類型的復雜網絡都可以通過數學語言抽象的矩陣來進行刻畫。5.二分網絡后面我們在介紹關于信息挖掘部分會涉及到一個與之前介紹過的不同的網絡，二分網絡。如圖2所示，二分網絡是由兩類的節(jié)點來構成的，它可以刻畫很多在線系統(tǒng)。在線系統(tǒng)里面，一類節(jié)點表示“用戶”，另外一類節(jié)點表示“商品”，或者是電影、視頻等等。在二分網絡中，連邊存在于兩類的節(jié)點之間，同類節(jié)點之間沒有連邊。它可以幫助刻畫在線用戶的行為，例如購物，你在淘寶上買了一個東西，那么你就作為一個“用戶”節(jié)點，你購買的東西是“商品”節(jié)點，然后把這兩個節(jié)點之間連一條邊。二分網絡能抽象用戶的在線行為，對應的鄰接矩陣與前文介紹的網絡的鄰接矩陣有所不同，它不再是一個方陣。前文介紹的網絡的鄰接矩陣一定是方陣，因為橫軸縱軸對應同一類節(jié)點，而二分網絡對應的鄰接矩陣，它是n×m，n是“用戶”節(jié)點，m是“產品”節(jié)點。如果n和m不相等，這就不是一個方陣。如果1號用戶購買了5號產品，就在（1，5）處記為1；如果沒有購買這個產品，就在相應處記為0。

圖2二分網絡

6.多層網絡還有一類最近研究比較多的網絡，多層網絡。多層網絡是更復雜的系統(tǒng)。例如航空系統(tǒng)就可以抽象成多層網絡。我們知道很多國家都有自己的航空公司，每家航空公司都有自己的航線。一家航空公司就可以形成一個自己公司內部的航空網絡。我們把若干家航空公司的內部網絡重疊（不一定是疊加），就可以用多層網絡來構建一個航空系統(tǒng)。理論上，多層網絡有多種刻畫方式，例如用大矩陣刻畫，把節(jié)點抽象成大矩陣里面的行列，也可以抽象成很多小矩陣，例如圖3中有5個小矩陣，但因為有時層與層之間會有連接，所以需要更多的矩陣去刻畫一個多層網絡。

圖3多層網絡7.度與度分布復雜網絡中有一個經典的概念——度，用于衡量節(jié)點的連邊數，即一個節(jié)點有多少條連邊，我們就定義它的度是多少。例如一個節(jié)點有3條連邊，它的度就是3。網絡中，節(jié)點在不同度值上的分布稱為度分布。我們通常用度分布的頻數統(tǒng)計圖展現(xiàn)網絡中節(jié)點的連邊數的分布情況。二、復雜網絡基本模型我們從最原始的研究開始介紹復雜網絡的基本模型。復雜網絡起源于1998年和1999年在《Nature》和《Science》雜志中的兩篇文章，分別提出了小世界網絡模型和無標度網絡模型，推動了復雜網絡領域近20年的發(fā)展。1.規(guī)則網絡與隨機網絡最早在物理學領域的研究中應用較多的網絡模型是規(guī)則網絡，例如晶格網絡。與規(guī)則網絡相對的是隨機網絡，在圖論中關于隨機網絡的研究比較多，任意兩個節(jié)點之間以一定概率隨機連接，就會形成隨機網絡。這兩類網絡在很多傳統(tǒng)科學研究中較為常見，但是當現(xiàn)實的數據收集越來越多時，人們發(fā)現(xiàn)這兩類傳統(tǒng)的網絡模型對現(xiàn)實中網絡的刻畫能力越來越差，直到上世紀90年代末小世界網絡和無標度網絡模型的提出。2.小世界網絡及六度分離小世界網絡模型描述的對象是社交網絡。社交網絡有兩個特點是傳統(tǒng)模型無法刻畫的，一是有比較大的集聚系數，二是最短路徑非常小。集聚系數指一個節(jié)點直接相連的其他節(jié)點（下文稱為“鄰居”）之間的連邊數。如果“鄰居”之間連接非常緊密，那么這個節(jié)點的集聚系數就比較大。在社交網絡中這一現(xiàn)象非常普遍，例如一個人的朋友之間相互認識的可能性是很大的，他們之間很可能也是朋友。另外，在復雜性科學中有一個概念叫六度分離理論。六度分離理論指在這個世界上，看似沒有關系的任意兩個人都可以通過六步左右的路徑連接在一起。例如一個股票專家做過一個實驗，將一封有關股票信息的電子郵件發(fā)送給一個陌生人，并要求他把電子郵件轉發(fā)給一個愛炒股的人,當這封電子郵件第六次轉發(fā)時，竟然又轉發(fā)到股票專家手中。經過無數次實驗結果相同,所以得出初步結論：任何兩個陌生人之間，可以通過六個人來建立聯(lián)系。我們可以通過有限的步驟把由70多億人組成的社交網絡中任意兩個點通過非常短的步驟連接在一起，這就是非常小的最短路徑特點。但是這兩個特點在規(guī)則網絡和隨機網絡里都不能被體現(xiàn)。例如，規(guī)則網絡的集聚性特別高，但是最短路徑可能很大；而隨機網絡因為連邊隨機，所以隨機選取兩個點，它們能以非常短的距離連接，但它的集聚性不高，我們任意選取一個點會發(fā)現(xiàn)它的鄰居之間往往連邊很少。所以，規(guī)則網絡和隨機網絡僅僅分別刻畫了社交網絡兩個特點之一。1998年發(fā)表在《Nature》期刊的一篇文章通過非常簡單的模型把社交網絡的兩個特點呈現(xiàn)出來了，即這一模型既有規(guī)則網絡的高集聚性，又有隨機網絡小的最短路徑特點。在規(guī)則網絡的基礎上，引入一個非常小的概率

，對原有的一條連邊以概率

剪斷，然后隨機在網絡里選取兩個節(jié)點連接在一起。當

時，任意一條連邊都不會重新連接，即規(guī)則網絡；如果

，每一條連邊都會以100%的概率被剪斷，然后重新連接到網絡里的任意兩個點，這樣的一個極端情況就是隨機網絡；當

時，網絡不但能保證原網絡比較高的集聚性，而且因為剪斷了少量的連邊使之重連，所以能出現(xiàn)一些長連邊，從而有效地縮短了整個網絡的最短路徑。由此看出，小世界網絡提出了一種能夠更好重現(xiàn)社交網絡的模型。

圖4規(guī)則網絡、小世界網絡、隨機網絡3.無標度網絡及網絡增長1999年《Science》期刊上發(fā)表的另外一篇文章認為，雖然小世界網絡模型能夠很好地重現(xiàn)社交網絡，但是社交網絡另一個非常重要的特點被小世界網絡忽略了。眾所周知，實際網絡是隨時間不斷增長的，例如引文網絡和微博網絡，因為有新的文章被發(fā)表，有新的用戶使用微博；社交網絡也是隨時間不斷增長的，但是小世界網絡它的節(jié)點數是固定的。為了重現(xiàn)這一特點，文章提出了一個增長網絡的模型，首先有若干個初始節(jié)點，然后每一步都會有新的節(jié)點加入，而這個新的節(jié)點會與一些老的節(jié)點相連，演化結束以后，會得到一個網絡，我們稱之為無標度網絡。這個網絡有一個性質是小世界網絡無法重現(xiàn)的，即實際網絡中廣泛地觀測到的度不均勻的現(xiàn)象。例如在微博網絡里，少數的大V有很多的粉絲，而大多數普通用戶就可能只有二三十個粉絲，這種不均勻性是小世界網絡無法刻畫的。再例如引文網絡中，一些文章的被引用次數是非常多的，成千上萬，但是絕大多數文章的被引用次數都非常少，而這樣一個增長網絡刻畫的就是這一現(xiàn)象。因為每一個節(jié)點進入的時候只能連比它更老的節(jié)點，這使得老的節(jié)點會有更長的時間去積累連邊，所以在這個網絡里，大量新的節(jié)點的連邊數都比較少，若干個老的節(jié)點的連邊數會非常多。這個網絡模型解釋了實際網絡里的“二八”效應，20%的點占了80%的連邊數。這兩篇文章讓人們發(fā)現(xiàn)，實際網絡有很多特點是傳統(tǒng)的網絡模型無法刻畫的。除小世界網絡和無標度網絡模型之外，還有哪些實際網絡的特性未被發(fā)現(xiàn)，所以近年來涌現(xiàn)了一大批的對于實際網絡進行建模的文章，提出的模型也是千差萬別。小世界網絡和無標度網絡度分布如圖5和圖6所示（p是連接概率）。我們發(fā)現(xiàn)，小世界網絡的度分布接近于正態(tài)分布，而且橫軸基本上是同一數量級的（10的1次方）。小世界網絡節(jié)點的度值差別不大。而無標度網絡的度分布頻數統(tǒng)計圖中（橫軸是節(jié)點的度，縱軸是該度值的節(jié)點數在網絡里面所有節(jié)點所占的比例），有很大比例的點的度非常小（10的1次方，10的0次方），有少量的點的連邊數極其多，數量能達到10的2次方，10的3次方，所以無標度網絡展現(xiàn)了節(jié)點度分布極度不均勻的特點，其中大量的點是小度節(jié)點，有少量的節(jié)點的連邊數特別多，而這種分布被稱為冪律分布（在頻數統(tǒng)計圖上坐標軸取雙對數，圖像是一條直線）。

圖5小世界網絡的度分布

圖6無標度網絡的度分布三、復雜網絡在解決實際問題中的應用1.網絡的魯棒性當出現(xiàn)擾動時，我們需要評價網絡的受損程度，如果網絡的受損程度小，系統(tǒng)還能正常運行，我們就稱這個網絡具有魯棒性。網絡的魯棒性涉及到滲流理論，關注的是網絡中的最大連通集團。很多實際網絡并不是全連通的，但會有一個最大的連通集團，其他節(jié)點散布在最大連通集團周圍。最大連通集團非常重要，肩負著網絡里面的很多功能，例如在航空網絡里，如果一個點不在最大連通集團之內，這個點的航班無法到達很多其他的空港；在神經網絡里，連通的神經元之間才能傳遞信息；在電力網絡里，網絡須有較好的連通性才能給一個點供電。因此，為確保網絡的魯棒性，應該保護網絡中的最大連通集團。實際網絡的特點是有大量的節(jié)點連邊數特別少，但是有少量的節(jié)點連邊數特別多。我們以航空網絡為例，航空網絡受到外界的干擾，如果是自然災害影響，因為自然災害一般沒有目的性，大多是天氣導致的，它可能會影響到某一些空港，使得空港的飛機無法起飛。在這種隨機影響下，整個網絡的功能性到底能有多大的保持？那么發(fā)現(xiàn)在這樣的網絡里面，我們將受到災害影響的節(jié)點從航空網絡里去掉，因為絕大多數的節(jié)點度值都很小而整個網絡的最大連通集團還比較大，所以航空網絡對于這種隨機干擾，它的魯棒性很高，對災害的敏感性不那么強；但是如果是外界蓄意攻擊，例如一個恐怖組織計劃破壞航空系統(tǒng)，必然不是隨機選取一個空港進行攻擊，而是攻擊網絡的中樞——最繁忙的機場。我們把這個機場從網絡中刪掉，最后發(fā)現(xiàn)網絡的最大連通集團變得特別小，使很多空港的飛機都無法與其他空港連接。大量的實際網絡都是由這樣的結構所刻畫的，而這樣的結構的魯棒性和脆弱性是共存的。因為網絡中有大量的點都是小度值的，所以隨機擾動并不能影響這個系統(tǒng)的運轉，但是對于蓄意攻擊，網絡是非常敏感的。2.網絡擁堵交通擁堵是大城市病之一。我們對交通進行建模，評價交通的運行狀況，評價交通網絡的設計是否合理，會不會造成大范圍的擁堵。例如將北京的道路抽象成網絡的形式，每一個節(jié)點表示一個路口，每一條邊表示路口與路口之間的道路。復雜網絡中有一個衡量節(jié)點重要性的指標叫做介數，表示通過一個點連接網絡中任意兩點最短路徑的數量，如果通過的最短路徑數量很多，那么這個點的介數就大。我們把道路系統(tǒng)抽象成網絡后，就可以計算網絡中每一個點的介數。那么我們可以列出介數很大的若干個點，它們擔負著若干個集團之間相互溝通的任務。如果一個網絡中的節(jié)點介數分布非常均勻，那么整個系統(tǒng)的交通流就被平均分擔到了各個路口，一般不會出現(xiàn)大量的擁堵。但是如果有若干個點的介數特別高，就說明這個路網的設計不太穩(wěn)健，一般會造成這個點上的擁堵。如果需要評價一個網絡可能出現(xiàn)的擁堵情況，我們就可以觀察節(jié)點中最大的介數，如果最大的介數都比較小，網絡的交通流分布就不會特別集中在若干個節(jié)點上，發(fā)生擁堵的可能性就小。我們以一個實例來說明上述的方法。如圖7所示，我們把北京西站附近的路網抽象為復雜網絡，每一個路口抽象為一個點，路口與路口之間的道路抽象為一條連邊。攝像頭可以記錄道路上的交通情況。圖中道路的顏色不是表示車的數量，而是表示車流的速度。電子地圖中的實時路況信息，顏色為紅色并不表示車多，而是表示道路上車速比較慢。在網絡建模并獲得了實際數據之后，我們就觀察每條道路的車流速度，車流速度慢就標為紅色，車流速度快就標為綠色。當然在不同的時間情況會不同，9點的時候紅色的道路就特別多，12點的時候紅色的道路就特別少。我們把網絡里紅的連邊刪掉，然后觀察網絡的連通集團到底會發(fā)生什么變化。當然，刪去的連邊越多，網絡的連通性就越差。

圖7北京西站附近的交通圖

圖8最大連通集團的變化為什么我們要關注網絡的連通性？因為在交通網絡里，如果刪去若干條連邊后，一個點和別的點無法連在一起，在現(xiàn)實中你就永遠到不了上班的地方。把這些特別擁堵的連邊從網絡里刪掉，因為這些道路擁堵了，你無法通過，就堵在路上了。如圖8，我們發(fā)現(xiàn)網絡中的最大連通集團含有節(jié)點數隨逐漸刪去連邊而下降，但不是平緩下降，而是在某一點陡降。這說明在網絡里，擁堵的連邊往往溝通了兩個區(qū)域，它并不是在網絡里隨機分布的，而是往往出現(xiàn)在網絡里介數比較大的點上。所以當刪到某一條邊后，你兩個區(qū)域不再連通，那么網絡中的最大連通集團就陡降了。交通網絡里會存在若干這種瓶頸路，一旦把它們刪掉，網絡的溝通情況就會變得特別差，從而分成兩個集團，而如果要疏導交通或提高交通的運行體驗，不需要全面地提升整個網絡，例如不需要把北京市所有的道路拓寬兩個車道，只需要把若干瓶頸路拓寬，就會很大程度上緩解交通擁堵。3.網絡傳播網絡傳播問題的研究對象是社交網絡。2013年發(fā)表在《Science》上的一篇文章研究了網絡上的傳播過程所具有的特點。它收集了2003年和2009年的兩組全球的數據，2003年是非典疫情爆發(fā)的一年，2009年是H1N1流感爆發(fā)的那年。數據中每個國家具有兩個數據，第一個數據是國家離病毒源頭的距離，我們知道SARS疫情是在中國爆發(fā)的，H1N1是在墨西哥爆發(fā)的，第二個數據是這個國家在中國爆發(fā)疫情后多長時間被感染。收集完數據以后，作者就做了散點圖，每個點代表一個國家，橫軸是它離中國的距離，縱軸是它感染病毒的時間。結果發(fā)現(xiàn)一個國家在什么時候被感染病毒與它距離源頭有多遠沒有明顯的關系。你離中國特別近，也不一定你明天就感染病毒，你離中國特別遠，也并不意味著你很安全，距離的遠近，實際上對病毒的傳染并沒有作出一個很好的解釋。

圖9疾病傳播時間與和疾病起源地有效距離的關系作者還關注到了全球航空網絡，搜集了兩個空港之間每天的航班數量及人流量，從而定義了一個有效距離

其中m和n分別代表一個國家，

表示這兩國之間的日常人流量，

越大，

越小，即如果兩個國家之間人流量特別多，這兩個國家的有效距離就越小。在重新定義距離后，作者作出了新的散點圖，縱軸依然是這個國家感染病毒的時間，橫軸表示有效距離，結果發(fā)現(xiàn)散點大多落在了一條直線上。這說明你離一個國家的有效距離比較近，你就會在比較早的時間感染這個病毒；如果一個國家離另外一個國家有效距離比較遠的話，那么你感染這個病毒的時間也會比較靠后，病毒要經過比較長的時間才能傳播到這個地方。所以決定一個國家感染病毒的快慢，實際上是網絡的有效距離，而不是地理距離。我們在日常生活中也有同樣的感覺。例