複雜網絡

從 集智百科
跳到: 導覽搜尋

複雜網絡是一種理解現實世界複雜系統的抽象模型。它將複雜系統中的實體抽象成點,而將實體之間的關係抽象成連線。雖然數學中的圖論也在研究網絡,但是,現實中的複雜網絡會更多地展現出隨機特性。因此,複雜網絡一般更加關注網絡的統計特徵

目錄

複雜網絡研究簡史

歐拉與格尼斯堡七橋問題

格尼斯堡的七橋是一個歷史上著名的數學問題。1736年歐拉·萊昂哈德[1]的負分辨率奠定了圖論[2]的基礎,預示了拓撲學[3]的概念。 普魯士[4]的格尼斯堡[5](現在是俄羅斯[6]的加里寧格勒[7])坐落在普瑞格爾河[8]的兩側,包括兩個大島——克內夫[9]和洛姆斯[10],它們通過7座橋互相連接在一起,且與城市的兩個大陸部分相連。問題是設計出一種穿越城市的方式,每座橋都要經過有且只有一次。 通過明確制定邏輯人物的方式,解決方案包括其中任何一個: 1.通過橋樑或其他途徑到達島嶼或大陸彼岸 2.不經過另一端而經過橋(但,這是絕對不可能的) 歐拉證明了這個問題沒有解決方案。他所面臨的困難是開發出一種合適的分析技術,以及後面的測試,這些測試需要用精確的數學方法證明這一論斷。

ER隨機網

在數學領域的圖論[11]中,ER模型與兩種用來生成隨機圖像[12]的模型密切相關。它們是以兩個於1959年首次介紹其中一個模型的數學家艾迪胥·保羅[13]和瑞尼·阿爾弗萊德[14]命名的,而吉爾伯特·埃德加[15]介紹了另一個,同時也獨立[16]介紹了艾迪胥和瑞尼介紹的模型。在艾迪胥和瑞尼模型中,所有圖形在一個固定的頂點及固定數量的邊緣上是等可能的;在吉爾伯特介紹的模型中,每條邊都有固定的出現或不出現的概率,與其他邊無關。這些模型可用於概率方法[17],以證明滿足各種性質的圖像的存在,或提供一個它對幾乎所有[18]圖形的屬性的意義的嚴格的定義。

小世界網絡

通過類比小世界現象[19](通常稱作六度分離[20]),網絡可以稱為小世界網路。由匈牙利作家卡林西·弗里傑什[21]於1929首次提出,米爾格拉姆·斯坦利[22]於1967年通過實驗檢驗小世界的假設,闡述為任意兩個人之間所間隔得人不會超過六個,即相應的社會關係圖的直徑不大於6。瓦特·詹姆斯·鄧肯[23]和斯托加茨·斯蒂芬[24]於1988年發表了第一個小世界網絡通過單個參數在隨機圖像和格子之間的平滑插值體現的模型。該模型證明了只有一小部分遠程鏈接,正則圖,在網絡的直徑大小成正比。該結論可以轉換成一個「小世界」中任意兩個頂點之間的邊的平均數量是非常小的(精確地說,網絡的尺寸呈對數增長),而聚類係數大。眾所周知,各種各樣的抽象圖像都具有小世界的特性,例如:隨機圖像和無標度網絡。此外,真實世界的網絡,如萬維網[25]和代謝網絡也顯示出這種特性。 在有關網絡的科學文獻中,「小世界」一詞有一些含糊不清的地方。除了表示網絡直徑的大小,還可以表示小直徑和高聚類係數[26]的同時出現。聚類係數時表示網絡中三角形密度的指標。例如,係數隨機圖的聚類係數可以忽略不計,而現實網絡的聚類係數往往要大得多。科學家指出,這種差異表明,在現實世界的網絡中,邊緣是相關的。

無標度網絡

無標度網絡是一個符合冪律[27]的度分佈[28]網絡[29],至少是漸近的。也就是說,網絡中有k個節點的節點分式P(k)對於k為較大的值,如[[30]],同時,γ參數的值通常是在2到3之間,雖然有時也可能在這些範圍之外。 一些報告表明,許多網絡是無標度的,儘管統計分析駁斥了其中許多的說法,並對其他說法提出了嚴重質疑。他們提出了優先依附[31]和適應度模型[32]作為解釋真實網絡中推測的冪律分佈的機制。

網絡科學

網絡科學是研究電信網絡[33]、計算機網絡[34]、生物網絡[35]、認知語義網絡[36]、社交網絡[37]等複雜網絡[38]的學術領域。該領域考慮節點(或頂點)所代表的不同元素或參與者,以及元素或參與者之間為鏈接(或邊)的連接。該領域採用的理論和方法包括數學的圖論[39]、物理的統計力學[40]、計算機科學的數據挖掘[41]和信息可視化[42]、統計學的推理建模[43]和社會學的社會結構[44]。美國國家研究委員https://en.wikipedia.org/wiki/National_Academies_of_Sciences,_Engineering,_and_Medicine美國國家研究委員會] 會將網絡科學定義為「研究物理、生物和社會現象的網絡表徵,從而得出這些現象的預測模型」。

表示與分類

鄰接矩陣

在圖論[45]和計算機科學[46]中,鄰接矩陣是用於表示有限圖[47]的方陣[48]。矩陣的元素表明圖中頂點對是否相鄰。在有限簡圖[49]的特殊情況下,鄰接矩陣是一個(0,1)對角線[50]上為0的矩陣。如果圖是無向的,則鄰接矩陣實對稱的[51]。譜圖理論[52]研究了圖與其鄰接矩陣的特徵值[53]和特徵向量[54]之間的關係。鄰接矩陣應與圖的關聯矩陣[55]分開,鄰接矩陣是一種不同的矩陣表示,其元素表示頂點——對邊是否有關聯,度矩陣[56]包含了每個頂點[57]的度[58]的信息。

鏈表表示

網絡分類

有向網

加權網

加權網是直接點之間的連結具有分配給它們權值的網絡[59]。網絡是一個元素以某種方式連接在一起的系統(沃瑟曼和浮士德,於1994年)。系統的元素表示為節點(也稱為參與者或頂點),交互元素之間的連接被稱為連結、邊、弧或鏈接。節點可以是神經元、個人、團體、組織、航站樓,甚至是國家,而連結可以是友誼、交流、合作、聯盟、流動或貿易等形式。 在許多現實世界的網絡中,並非網絡中的所有連結都具有相同的容量。事實上,連結往往與權數有關,以他們的力度、強度、能力 (巴拉特.et al.,於2004年;霍瓦特,於2011年)區分。一方面,格蘭諾維·馬克[60](於1973年)認為,社交網絡[61]中社交關係的強度是其持續時間、情感強度、親密度和服務交換的函數。另一方面,非社會網絡,權重通常指的是執行的函數關係,例如,在食物網[62]中,物種之間的碳流量(毫克/m²/天)(拉士克維施.et al.,於2003年),神經結的數量和縫隙連接神經網絡(沃茨和斯特里伽茨,於1998年),或在交通網絡中的流動的流量(奧普薩爾 et al.,於2008年)。 通過記錄連結強度,可以創建一個加權網絡(也稱價值網絡)。下面是這樣一個網絡的例子(權重也可以通過賦予變換不同的寬度來可視化): [[63]] 加權網絡也廣泛應用於基因組和系統生物學[64]應用。(霍瓦特,於2011年)。例如,加權基因共表達網絡分析(WGCNA)常用於構建基於基因表達(如微陣列[65])數據的基因(或基因產物)之間的加權網絡(張某和霍瓦特,於2005年)。一般而言,加權相關網絡[66]可以用軟閾值法定義變量之間的兩兩相關關係(如基因檢測)。

流網絡

在圖論[67]中,流網絡(也稱運輸網絡)是一個有向圖[68],其中每條邊都有一個容量,每條邊接受一個流量。邊緣上的流量不能超過邊緣的流量。通常來說,在運籌學[69]中,有向圖成為網絡,那些頂點被稱為節點,這些邊稱為弧。流量必須滿足流入節點的流量等於流出節點的流量的限制,除非它是一個只有流出流或匯聚即只有流入流的源。一個網絡可以用來模擬道路系統中的交通,需求環流,管道中的流體,電路中的電流,或任何類似的東西通過一個節點網絡時的情況。

空間網

空間網絡(有時也稱為幾何圖形[70])是指頂點[71]或邊[72]是與幾何[73]對象相關聯的空間元素的圖像[74],即節點位於具有一定度量[75]的空間中。最簡單的數學實現是格子[76]或隨機幾何圖形[77],它們的節點在二維平面上均勻分佈;如果歐幾里德距離[78]小於給定的鄰域半徑,則連接一對節點。交通和移動網絡[79]、互聯網[80]、流動電話網絡[81]、電網[82]、社交和聯繫網絡[83]以及神經網絡[84]都是底層空間相關的例子,而圖的拓撲[85]本身並不包含所有信息。描述和理解空間網絡的結構、彈性和演化對從城市主義到流行病學的許多不同領域都至關重要。

二分網

二分網是一類特殊的複雜網絡[86],其節點被劃分為兩個集合X和Y,只允許不同集合中兩個節點之間的連接。為了方便直接顯示特定一組節點之間的關係結構,通常採用單模投影的方式壓縮二分網。這意味着接下來的網絡只包含兩個集合中的任意一個節點,並且只有當兩個X(或者Y)節點至少有一個公共相鄰的Y(或者X)節點時,它們才會連接。 最簡單的方法涉及到雙方的網絡投射到一個未加權的網絡,但不考慮網絡的拓撲結構或共享一個連接的頻率對立的元素集。由於在這種情況下,雙方的網絡很大程度上與不同的結構可以有完全相同的一種模式表示,一個清晰的插圖的原始網絡拓撲通常需要使用一些加權法。[[87]]

統計指標

在統計和研究設計[88]中,指標是一種複合統計[89]——衡量一組具有代表性的單個數據點的變化,或者換句話說,綜合多個指標[90]的複合度量。指標總結和排列特定的觀察。 社會科學領域的許多數據都用各種指數表示,如性別差距指數[91]、人類發展指數[92]或道瓊斯工業平均指數[93]。 各項指標通常權重相等,除非有一些理由違反(例如,如果兩個項本質上反映了變量的相同方面,那麼它們的權重可能為0.5)。 構建項目涉及四個步驟。首先,項目的選擇應該基於它們的面部效度[94]、單維性、測量維度[95]的特異性程度以及它們的方差[96]。項目之間應該有經驗上的聯繫,這引向了檢驗它們的多元關係的第二步。第三,設計索引得分,這涉及到確定它們的得分範圍和項目的權重。最後,需要對指標進行驗證,這涉及到是否能夠預測與構建中未使用的測量變量相關的指標。

在圖論[97]中,圖[98]的頂點[99]的度(或值)是指與該頂點關聯的[100]、循環數[101]為2次的邊[102]的數量。一個頂點v是表示程度的度(v)或度訴一個圖G的最大程度,用Δ(G)和最低程度的一個圖表,用δ(G),最大和最小程度的頂點。在右邊的圖中,最大值是5,最小值是0。在一個普通的圖[103]中,所有的度都是一樣的,所以我們可以說這個是圖的度。[[104]]

平均路徑長度

平均路徑長度是拓撲網絡[105]中的一個概念,定義為所有可能的網絡節點[106]對的最短路徑上的平均步數。它是網絡上信息或大眾運輸效率的一種度量。

直徑

在幾何學[107]中,圓[108]的直徑是任何穿過圓中心、端點在圓上的直線段[109]。它也可以定義為圓的最長弦[110]。這兩個定義對於球體[111]的直徑也是有效的。 在現代化的用法中,直徑的長度也被稱為直徑。從這個意義上說,我們談論的是直徑(指距離)而不是直徑(指的是直線本身),因為一個圓或球體的所有直徑都有相同的長度,這是半徑[112]r的兩倍。 d = 2r⇒r = d / 2。 對於平面上的凸形[113],其直徑定義為兩條相切於其邊界的平行線[114]之間可以形成的最大距離,而寬度通常定義為這種距離的最小值。這兩個量都可以用旋轉卡尺[115]有效地計算出來。對於一個等寬的曲線[116],例如魯洛三角形[117],其寬度和直徑是相同的,因為所有的平行切線的長度相同。 而對於橢圓[118],標準術語是不同的。橢圓的直徑是任何穿過橢圓中心的弦。例如,共軛直徑[119]具有這樣的性質:其中一個端點與橢圓的切線平行於另一個端點。最長的直徑稱為長軸[120]。 「直徑」一詞來源於希臘[121]διάμετρος(diametros)、「一圈直徑」,從διά(dia)」,通過「和μέτρον(密特隆),「衡量」。[3]通常縮寫DIA,dia,d,或⌀。

集聚係數

在圖論[122]中,聚類係數是圖中節點聚類的程度的度量。有證據表明,在大多數真實世界的網絡中,特別是在社交網絡[123]中,節點往往以相對高密度的聯繫為特徵,形成緊密的群體;這種可能性往往大於兩個節點之間隨機建立平局的平均概率(霍蘭德和萊因哈特,於1971年; 瓦茨和斯托蓋茨,於1998年)。 這種方法有兩種版本:全局和局部。全局版本的設計是為了給出網絡中集群的總體指示,而局部版本則表示單個節點的嵌入性。

相關性

關聯性是指一個主題與另一個主題之間的聯繫[124],在考慮第一個主題時考慮第二個主題是有作用的。關聯的概念被研究在許多不同的領域,包括認知科學,邏輯,圖書館信息科學[125]。然而,最根本的是,它屬於認識學[126](也稱認識論)的研究範圍。不同的知識理論對被認為相關的東西有不同的含義,這些基本觀點對所有其他領域也都有影響。

模塊性

從廣義上講,模塊化是指系統的組件可以分離和重組的程度,通常具有靈活性和多樣化的使用優勢。模塊化的概念主要用於通過將系統分解為不同程度的相互依賴和獨立性來降低複雜性,並「將每個部分的複雜性隱藏在抽象和接口之後」。然而,模塊化的概念可以擴展到多個學科,每個學科都有自己的概念上的細微差別。儘管有這些細微的差別,關於模塊化系統的一致主題還是出現了。

節點中心性

在圖論[127]和網絡分析[128]中,中心性指標確定圖中最重要的頂點[129]。應用程序包括識別社交網絡[130]中最有影響力的人、互聯網[131]或城市網絡[132]中的關鍵基礎設施節點和疾病的超級傳播者[133]。中心性概念最早出現在社會網絡分析[134]中,許多衡量中心性的術語反映了它們的社會學[135]淵源。它們不應該與節點影響度量[136]相混淆,節點影響度量試圖量化網絡中每個節點的影響。[[137]]

實證數據

實證數據,也被稱為感覺經驗,是通過感覺[138]獲得的信息[139],特別是通過觀察[140]和記錄通過實驗[141]的模式和行為。該詞來自希臘[142]語的經驗,ἐμπειρία(empeiria)。 在康德·伊曼努爾[143]之後,哲學中通常把獲得的知識稱為後驗知識[144](與先驗[145]知識相反)。

統計特徵

可觀測性

統計量是一種可觀察的隨機變量[146],它不同於描述統計總體[147]特性的一般不可觀察量的參數[148],也不同於不可觀察的隨機變量,例如觀察到的測量值和總體平均值之間的差值。如果整個總體可以觀察到沒有誤差,一個參數只能精確地計算;例如,在一個完美的人口普查或標準化考試[149]的考生群體中。 統計學家經常考慮一個參數化的概率分佈族[150][151],其中的任何成員都可能是人口中每個成員的某種可測量方面的分佈,從中隨機抽取一個樣本。例如,這個參數可能是北美25歲男性的平均身高。測量了100個這樣的人的樣本的身高;這100個數字的平均值是一個統計數據。人口中所有成員的平均身高不是一個統計數據,除非這個數據也以某種方式被確定(例如通過測量人口中的每一個成員)。所有25歲北美男性的平均身高是一個參數,而不是一個統計數據。

統計特性

統計的重要潛在特性包括完整性、一致性、充分性、無偏性、最小均方誤差、低方差、穩健性和計算便利性。

信息的統計

模型參數的統計信息可以用幾種方法定義。最常見的是費雪信息,它是在由統計量引起的統計模型上定義的。也可以使用庫爾貝克信息度量。

無標度

一個網絡的度分佈被稱為無標度,即一個均勻隨機選擇的節點有一定數量鏈路度的概率,遵循一個被稱為冪律[152]的特殊數學函數。冪律表明,這些網絡的度分佈沒有特徵尺寸。相比之下,具有單一的、規模定義明確的網絡在某種程度上類似於網格,因為每個節點(大致)都在同一個程度。單一的規模網絡的例子,包括Erdős-Renyi(ER)[153]隨機圖像和超立方體[154]。產生尺度不變的度分佈的網絡模型有巴拉巴西-艾伯特模型[155]和適應度模型[156]。在一個具有無標度度分佈的網絡里,一些頂點有大於平均梯度的階的等級——這些頂點通常被稱為樞紐,儘管這有點誤導因為它沒有固定的閾值,一個節點可以被視為一個樞紐。如果有這樣的閾值,網絡就不會是無標度。 人們對無標度網絡的興趣起始於1990年代末的關於冪律度分佈在真實世界的網絡如萬維網[157]、自製系統[158]網絡(ASs),一些互聯網路由器網絡、蛋白質相互作用網絡、電子郵件網絡等的發現報告。大部分在報告冪律時,在挑戰嚴格的統計測試時,都失敗了,但是,對於重尾度分佈的較普遍看法——許多這樣的網絡確實表現出這種分佈(在有限尺寸影響發生之前)——與人們所預期的邊緣獨立存在且隨機存在(即假設它們遵循泊松分佈[159])。建立一個冪律度分佈的網絡有很多種不同的方法。尤爾過程[160]是冪律的典型生成過程,自1925年以來就為人所知。然而,由於其頻繁的再創造,它的許多其他名字被人們所熟知,例如,西蒙·亞歷山大·赫伯特[161]的直布陀羅原則、馬太效應[162]、累積優勢,以及巴拉巴西[163]和艾伯特的冪律度分佈的優先鏈接[164]。近期,雙曲幾何圖形[165]被認為是另一種構建無標度網絡的方法。 一些具有冪律度分佈的網絡(以及特定的其他類型的結構)可以高度抵抗垂直的隨機刪除——即絕大多數頂點仍然與一個巨大的指數連接在一起。這樣的網絡對旨在快速破壞網絡的攻擊也異常敏感。當圖像是除度分佈外均勻隨機的時候,這些關鍵的頂點是最高階的,因此在社會和通信網絡涉及疾病和病毒的傳播(自然和人工),以及時尚的傳播(這兩種都是由滲流[166]或分支流程[167]建模的)。而隨即圖像(ER)節點間的平均距離為o(log N),其中N為節點數,無標度圖像的距離為log log N。這種圖像被稱為超小世界網絡。

小世界

這個小世界實驗由米爾格拉姆·斯坦利[168]和其他研究人員進行的幾個實驗組成,他們研究了美國人社交網絡[169]的平均路徑長度[170]。該研究具有開創性,它表明人類社會是一個以短路徑長度為特徵的小世界型網絡[171]。這些實驗經常與「六度分離」[172]聯繫在一起,儘管米爾格拉姆本人並沒有使用這個術語。

Rich Club係數

Rich-club係數是圖形[173]和網絡[174]的度量標準,旨在衡量連接良好的節點之間相互連接的程度。具有較高Rich-club係數的網絡具有較強的Rich-club效應,且節點間的連接程度較高。這種效應已經在科學協作網絡和航空運輸網絡中得到了測量和注意。蛋白質相互作用網絡[175]明顯缺乏Rich-club係數。

社區劃分

基本模型

SW模型

BA模型

艾伯特-巴拉巴西(BA)模型是一種使用優先連接[176]機制生成隨機無標度網絡[177]的算法。一些自然的和人為的系統,包括互聯網[178]、萬維網[179]、引文網絡[180]和一些社交網絡[181],被認為是近似無尺度的,並且肯定包含很少的節點(稱為集線器),與網絡的其他節點相比具有異常高的程度。BA模型試圖解釋真實網絡中存在這樣的節點。該算法以發明者艾伯特·拉斯洛·巴拉巴西[182]和艾伯特·瑞卡[183]的名字命名,它是一種更通用的模型的特例,稱為普利斯模型[184]

雙曲幾何模型

有很多不同的偽球面在很大範圍內都有一個恆定的負高斯曲率,其中偽球面[185]是最著名的。 但是在其他模型上做雙曲幾何比較容易。 [[186]] [[187]] 雙曲幾何常用的模型[188]有四種:克萊恩模型[189]、龐加萊圓盤模型[190]、龐加萊半平面模型[191]和洛倫茨或雙曲面模型[192]。這些模型定義了滿足雙曲幾何公理的雙曲平面。儘管它們的名字,上面提到的前三個模型是由貝爾特拉米[193]作為雙曲空間模型引入的,而不是由龐加萊[194]或克萊恩[195]提出的。所有這些模型都可以擴展到更多的維度。

網絡上的動力學

網絡的動力學

個人工具
名字空間
動作
導覽
工具箱