Ch3 復雜網絡的基本統計特征

第三章復雜網絡的基本統計特性1網絡的“度”刻畫了一個節點的一階鄰居數量23.1網絡的度和度分布3度分布P(k)：網絡中各個度值的節點所占的比例。4累積度分布Pk：網絡中隨機選取一個節點，其度大于或等于k的概率。5不同網絡上的累計度分布曲線局部集聚系數是用來度量網絡中單個節點的鄰居節點相互之間連接的程度。對于網絡中的一個節點，它的局部集聚系數指的是其鄰居節點之間實際存在的邊數與可能存在的最大邊數之間的比例。局部集聚系數是一個重要的度量指標，它可以幫助理解網絡中微觀層面上的連通性。例如，在社交網絡中，一個高局部集聚系數可能意味著個人的朋友彼此之間也是朋友。63.2網絡的集聚系數局部集聚系數計算方式：局部集聚系數ci的值范圍為0-1，值越接近1，表示鄰居之間的連接越緊密，形成一個緊湊的團簇；值越接近0，表示鄰居之間幾乎沒有直接的連接。7全局集聚系數是對整個網絡集聚傾向的度量，它描述了網絡中形成完整三角形（即閉合三元組）的傾向。與局部集聚系數不同，它不是針對單個節點而是針對網絡整體。在得到網絡中所有節點的集聚系數之后，一個網絡的全局集聚系數C可定義為網絡中所有節點的集聚系數值的平均：8集聚系數計算示例9路徑是網絡中從一個節點到另一個節點的連接序列，其中每一對連續的節點都通過網絡中的邊相連。以無向網絡為例，路徑是指沿著網絡中的連邊行走所經過的節點，它是一個節點序列，可表示為：網絡中兩個節點vi和vj之間的距離dij通常指的是網絡中兩個節點之間的最短路徑長度，它是衡量網絡中信息傳遞速度和效率的基本指標。測定最短路徑的算法主要有Dijkstra算法和Floyd算法。103.3網絡的距離與介數網絡的平均路徑長度是一個描述網絡中所有節點對之間路徑長度平均值的度量，是衡量網絡全局連通性的一個重要指標。對于一個給定的網絡，網絡的平均路徑長度L定義為任意兩個節點之間的平均距離，即：在小世界網絡中，即使是在大規模網絡中，任意兩個節點之間的平均距離也相對較小；在規則網絡（每個節點以相同的方式連接到其他節點）中，平均路徑長度可能會更長；在隨機網絡中，平均路徑長度通常介于規則網絡和小世界網絡之間。11網絡的直徑D是網絡中所有節點對之間最短路徑的最大值。在實際網絡中，網絡直徑指的是任意兩個存在有限距離的節點之間的最大距離，即：小世界網絡中網絡的直徑可能較小，而在規則網絡中，直徑可能會比較大。1213介數用于衡量某個節點在網絡中的重要性或中心性。介數定義為任意一對節點間的最短路徑經過某節點或連邊的次數，可以分為點介數和邊介數。14點介數：邊介數：網絡的稀疏程度即網絡的密度，定義為網絡中實際存在的邊數M與最大可能的邊數之比。網絡的稀疏程度可定義為（在有向圖網絡中，去掉下式分母中的）：平均度與網絡密度之間的關系：153.4網絡的稀疏性與連通性一個圖中任意兩點間至少有一條路徑相連，則稱該圖為連通圖。任何一個非連通圖都可分為若干個連通子圖，每個子圖稱為原圖的一個分圖。含有節點數最多的連通子圖稱為最大連通集團。一個連通圖G的連通程度也稱作連通度。16度度相關性：度與度之間的相關性173.5度度相關性與富人俱樂部度度相關性的計算方法可視化描述：ejk表示在網絡中隨機選擇一條連邊，它的兩端點的度值分別為j和k的概率，通過可視化描述ejk的概率分布來定性判斷網絡的度度相關性。18同配性異配性度度相關性的計算方法度相關函數所有度值為k的節點的最近鄰平均度值的平均值定義為：如果knn(k)是隨著k值上升的增函數，即μ>0，稱該網絡為同配網絡；若μ<0，稱該網絡為異配網絡；若μ=0，則稱該網絡為中性網絡。19度度相關性的計算方法相關系數皮爾遜（Pearson）相關系數20富人俱樂部現象實際網絡中存在少量的節點卻擁有大量的連邊，這些節點被稱為“富節點”；它們傾向于彼此之間相互連接，出現了“富人俱樂部”現象。富人俱樂部系數表示網絡中前r個度值最大的節點之間實際存在的連邊數L與這r個節點之間總的最大可能邊數的比值，即：如果φ(r/N)=0，則不存在富人俱樂部現象；如果φ(r/N)=1，則前r個度最大的節點組成的富人俱樂部為一個完全連通子圖。21模體——在網絡中密度明顯較高的子圖（基本結構單元）223.6模體判斷實際網絡的子圖j是否為模體（1）該子圖在與實際網絡對應的隨機化網絡中出現的次數大于它在實際網絡中出現次數的概率很小，通常要求這個概率小于某個閾值P。（2）該子圖在實際網絡中出現的次數Nreali不小于某個下限U。（3）該子圖在