復雜網絡Ch6 加權網絡

第6章加權網絡6.1加權網絡模型及統計性質6.2權重對網絡結構性質的影響6.3加權網絡的演化6.4空間網絡16.1加權網絡模型及統計性質26.1.1邊權的定義3權重（點、邊）加權網絡中邊權的賦予網絡中以已有的物理量eg：電阻網絡——電阻；航空網——座位數、航班數、里程；新陳代謝網——反應速率；因特網——帶寬相互作用的抽象eg：科學家合作網——合著文章數；演員合作網——合演次數；中藥網、菜肴網等4無權無向網絡

加權無向網絡31423214protein-proteininteractions,wwwCallGraph,metabolicnetworks6.1.1邊權的定義5權重的不同定義相似權：

概念與距離相反，邊權越大，頂點之間越親近（0為無連接）如合作次數、化學反應速率相異權：

概念與距離相同，邊權越大，頂點之間距離越遠（∞為無連接）如航空線的里程

YINGFAN,MENGHUILI,JIAWEICHEN,LIANGGAOandZENGRUDI，InternationalJournalofModernPhysicsBVol.18,Nos.17-19(2004)2505-25116.1.1邊權的定義6.1.2加權網絡上的統計量6點強度，強度分布，單位權和差異性點權：單位權：權重分布的差異性：7相關性相關匹配性質：節點的加權平均近鄰度：

具有較大權重的邊傾向于連接具有較大度值的節點

具有較大權重的邊傾向于連接具有較小度值的節點6.1.2加權網絡上的統計量8最短路徑：兩個由權重分別為w12和w23的邊連接的頂點之間的距離:相異權d13=w12+w23相似權d13=1/w=1/w12+1/w236.1.2加權網絡上的統計量123w12w239加權集聚系數：加權網集聚系數:

加權網集聚系數:

(三角形三條邊上權重的幾何平均值)

6.1.2加權網絡上的統計量10

6.1.2加權網絡上的統計量11生物網絡：阿爾莫斯（Almaas）等把大腸桿菌的新陳代謝反應看作加權網絡進行研究。蒂耶里等研究了人類免疫系統中細胞間的通信過程。社會網絡：科學家合作網、電影演員合作網、E-mail網絡以及人際關系網等都是典型的社會網絡，其中許多網絡的拓撲性質，都得到了深入研究。技術網絡:基礎設施網絡中如Internet、鐵路網、地鐵網和航空網中，輸運過程中的流量可以自然的轉化為權重。6.1.3一些加權網絡的實證結果12收集了1992-2004年發表的經濟物理學方面的文章，包括808篇文章和819位作者。從數據庫中可以得到任意兩位作者之間的合作、引用和致謝3種關系的次數3個網絡：合著網絡、引用網絡和致謝網絡，把不同層次的交流和相應次數轉化為邊上的權重。把每條邊上的合作、引用和致謝的權重綜合成為一個權重：3種關系所對應的權重定義為：引用和致謝是有方向性的，因此經濟物理科學家合作網絡是一個加權有向網。在以上數據庫和邊權賦予的情況下，得到了該網絡的基本統計結果。6.1.4經濟物理學科學家合作網絡的建立和統計分析13經濟物理學家合作網絡的Zipf排序6.1.4經濟物理學科學家合作網絡的建立和統計分析14經濟物理學家合作網絡的點介數的Zipf排序6.1.4經濟物理學科學家合作網絡的建立和統計分析15單位權頻數統計分布6.1.4經濟物理學科學家合作網絡的建立和統計分析16社團結構的模塊化Q函數：6.1.5加權網絡的社團結構表示節點i的點權網絡中所有連邊的權重之和

17GN算法在加權網上的推廣:將加權網轉化為無權多圖，在無權多圖中每條邊的權重都是相同的，點與點之間的緊密程度是由邊的個數表示的。加權網與無權多圖：6.1.5加權網絡的社團結構18

6.1.5加權網絡的社團結構6.2權重對網絡結構性質的影響1920調整權重與邊的匹配關系:6.2.1權重調整對網絡基本結構性質的影響原始加權網絡（Weighted）相應的無權網（Nonweighted）反權網（Inverse）21原始網絡、反權網絡和隨機賦權網絡的比較6.2.1權重調整對網絡基本結構性質的影響22加權網絡和無權網絡中最大連通集團介數分布的比較:6.2.1權重調整對網絡基本結構性質的影響23最大連通集團的統計結果：6.2.1權重調整對網絡基本結構性質的影響經濟物理科學家合作網絡原始網絡集聚系數值比反權網絡和隨機網絡的數值大。這表明權重和網絡中的邊有特定的匹配關系，權重并不是隨機賦予的，而是與網絡的結構與功能耦合在一起的。24調整權重的分布:6.2.1權重調整對網絡基本結構性質的影響產生新權重分布的方法和理論分析（權重隨機化方法）在規則網上，把每條邊的權重w分成份(每為)，每一份都以

p的概率抽取；把抽取后的份

等概率的撒在每條邊上。權重分布的理論分析：設隨機化后邊權為，那么每條邊包含

的份數與同分布25平均最短路徑和集聚系數與概率p的關系6.2.1權重調整對網絡基本結構性質的影響26網絡規模與平均最短路徑的關系:6.2.1權重調整對網絡基本結構性質的影響27網絡引入權重之后，節點間的相互作用會發生改變，進而影響聚類過程中社團的劃分。紐曼針對已知社團結構的網絡，給出了判別不同聚類結果正確率的方法

不能準確的描述不同社團結構間的差別

達農等提出了一個比較不同聚類結果準確率的函數I(A,B)

沒有注重社團結構中類的差別判斷聚類結果差異性的函數D6.2.2權重調整對社團結構的影響28加權網絡和無權網絡聚類結果對比:6.2.2權重調整對社團結構的影響6.3加權網絡的演化2930基本特征：按照一定的偏好機制形成網絡拓撲結構的演化，在此過程中為每一條新加入的邊賦權。而邊權是固定的，并不隨網絡結構的演化而變化。模型：Yook-Jeong-Barabási-Tu(YJBT)、Zheng-Trimper-Zheng-Hui(ZTZH)、Antal-Krapivsky(AK)6.3.1邊權固定模型31Yook-Jeong-Barabási-Tu(YJBT)考慮權重的無標度網絡演化模型。在演化過程中，網絡拓撲結構的演化規則與無權網絡演化的BA模型完全相同。節點j所帶有的邊按偏好連接規則連接到老節點，連接到節點i的概為：

m條邊連接完成后，節點j的每條邊賦予權重：6.3.1邊權固定模型32

6.3.1邊權固定模型33Antal-Krapivsky(AK)加權網絡的演化模型，改進之處是在演化過程中考慮了邊權對網絡結構演化的影響。模型的演化規則如下：每個時間間隔有一個新節點j加入網絡中，并選擇一個老節點i建立一條連接，其連接概率正比于節點的強度：6.3.1邊權固定模型34上述模型都忽略了當新節點或邊進入系統時邊權演化的可能性。事實上，相互作用關系的演化和加強是現實系統共同的特征。例如，在飛機航線網絡中，兩機場間新航線的建立通常會影響到兩個機場的客流量以及與其相關的航線的客流量。6.3.2邊權演化模型35Barrat-Barthélemy-Vespignani(BBV)基于點強度驅動和邊權逐漸加強機制建立的網絡演化模型，可以模仿現實系統中相互作用強度的變化。權重分配示意圖：6.3.2邊權演化模型36Dorogovtsev-Mendes(DM)是一個邊權演化模型，權重大的邊增加權重，然后吸引新的連接。DM模型的演化規則示意圖：6.3.2邊權演化模型37流驅動的加權網絡模型不僅考慮了新節點加入的影響，同時還考慮了邊權隨時間的演化以及老節點之間新邊的生成。權重變化規則：帶有m條邊的新節點n按下面的規則與老節點隨機連接：6.3.2邊權演化模型38加權網絡演化模型應該符合3個基本要求：邊權演化、一般性、不需要額外的非網絡信息。科學家合作網絡的實證研究為構造加權網絡演化模型的啟示：新老節點每一時刻都可以建立新的連接，并允許節點間的重復連接，通過簡單的函數關系把連接次數轉化為權重，就可以研究在各種驅動機制下的加權網絡演化模型。連接次數依照權重或度進行演化，然后，新的連接次數又轉化為邊權，再次驅動系統的演化6.3.3基于科學家合作機制的加權網絡演化模型39基于科學家合作網的加權網絡演化模型6.3.3基于科學家合作機制的加權網絡演化模型6.4空間網絡4041社會網Internet網絡航空網絡其他網絡6.4.1空間網絡的實證研究42社會網社會網絡的空間距離分布呈冪律特征，即朋友之間距離的概率密度函數滿足冪律分布。通過利本-諾威爾、阿達米克、埃達等人的研究案例，說明社會網絡的空間距離分布的冪律特性。從人們追求信息量最大化的角度，因此社會網絡空間結構中冪律特性的普適性。6.4.1空間網絡的實證研究43Internet網絡Internet

節點位置關系和人口分布具有強相關性。通過盒覆蓋方法計算網絡分形維度，與人口分布分形維度吻合。討論科學技討論科學技術發展對通信距離的影響，以及空間因素對網絡性質的影響。術發展對通信距離的影響，以及空間因素對網絡性質的影響。6.4.1空間網絡的實證研究44航空網絡航空網絡受到多種因素的影響，例如地理位置、歷史、政治因素、航空公司利益等。通過吉梅拉、楊華等人的研究案例，說明全球航空網絡和日本航空網絡均存在冪律特性。指出美國航空網絡的距離分布也服從冪律分布。6.4.1空間網絡的實證研究45其他網絡介紹人腦網絡的空間結構研究，指出其具有小世界特性，并指出當前研究的不足。其他空間網絡廣泛存在，例如電力網絡、交通網絡等。6.4.1空間網絡的實證研究46Kleinberg導航模型6.4.2基于網格的導航模型(a)p=1，q=0的6*6二維網格，(b)p=1，q=2的6*6二維網格47如果說一個網絡的搜索時間復雜度隨著網絡的規模呈對數多項式增