引論

慕課網，複雜網路分析，樊瑛，北京師範大學系統科學學院，icourse163.org/spoc/cou

參考書：網路科學導論，汪小帆，李翔，陳關榮 編著，高等教育出版社，2012.

本筆記結合慕課網PPT和參考書整理。

不同領域的複雜網路

  • 社會網：演員合作網，朋友網，姻親關係網，科研合作網，
  • Email網，簡訊網…
  • 生物網：食物鏈網，神經網，新陳代謝網，蛋白質網，基因網路…
  • 信息網路： WWW，專利使用，論文引用， …
  • 技術網路：電力網， Internet，電話線路網，
  • 交通運輸網：航線網，鐵路網，公路網，自然河流網
  • 經濟系統：投入產出網，國際貿易網， …

網路研究的歷史

1736，歐拉：哥尼斯堡七橋

  • Euler 開啟了數學圖論，抽象為頂點與邊的集合
  • 圖論是網路研究的基礎
  • 網路結構是理解複雜世界的關鍵

1950， Erdos, Renyi: 隨機圖論

1998， Strogatz； 1999， Barabasi: 小世界和無標度網路

  • Watts D. J., Strogatz S.H., Collective dynamics of small-world networks. Nature, 1998, 393(6684):440-442.
  • Barabasi A-L, Albert R., Emergence of scaling in random networks. Science, 1999,286(5439):509-512.

網路科學的研究內容

網路的複雜性體現在：

  • 結構複雜性；
  • 節點複雜性；
  • 結構與節點之間的相互影響；
  • 網路之間的相互影響。

網路科學的主要研究內容

  • 發現。揭示刻畫網路系統結構的拓撲性質，以及度量這些性質的合適方法；
  • 建模。建立合適的網路模型以幫助人們理解這些統計性質的意義與產生機理；
  • 分析。基於單個節點的特性和整個網路的結構性質分析與預測網路的行為；
  • 設計。提出改善已有網路性能和設計新的網路的有效防範；
  • 從網路科學到網路工程。

網路的拓撲結構——靜態幾何量及其統計性質

  • 度、聚集係數、最短路徑、介數、權、相關性
  • 網路上的聚類分析

對網路結構的描述——幾何量及其分佈

  • 度（Degree）：朋友的個數
  • 集聚係數（羣係數）（Clustering coefficient）：朋友的朋友還是不是朋友的情況
  • 最短路徑（Shortest path）：兩個頂點之間邊數最少的路徑
  • 介數（Betweenness）：經過我的最短路徑的條數

網路的演化性質和機制模型

  • 時間演化性質，偏好性的檢驗
  • Small World Network ， Scale Free Network-BA 模型

網路的結構與功能

  • 網路的容錯與抗攻擊能力
  • 網路上的動力學性質

複雜網路的4種結構

規則網路

隨機網路

  • 度分佈:Poisson 分佈
  • 齊次特徵:每個節點大約有相同的連接數：
  • 節點數不增加

小世界網路

  • 齊次性:每個節點有大約相同的連接數
  • 節點不增加

無標度網路

  • 度分佈:Power Law Degree Distribution（冪律度分佈）

P(k)propto k^{-gamma}

ln P(k)propto -gamma ln k

P(lambda k)propto (lambda k)^{-gamma}=lambda^{-gamma}k^{-gamma}=lambda^{-gamma}P(k)

  • 非齊次性:
  • 很少的節點有很多連接，很多節點只有很少的連接
  • 節點數增加

複雜網路中頂點度的匹配關係(Assortative Mixing by Degree)

同向匹配&反向匹配

  • 如果網路中度值高的頂點傾向於與其他高度值的頂點相互連接，則稱網路具有同向匹配性質；
  • [ ] 例如：社會網路
  • 如果網路中度值高的頂點傾向於與度值低的頂點相互連接，則稱網路具有反向匹配性質；
  • [ ] 例如：大部分生物、技術網路

複雜網路中的社團結構（Community Structures）

  • 社團內部連接緊密，社團之間連接相對稀疏
  • 網路模體---Network Motifs 模體——在網路中密度明顯較高的子圖（基 本結構單元）

網路的結構與功能

網路上的動力學行為和過程

  • 動力系統：自旋、振子或混沌的同步、可激發系統…
  • 傳播過程：信息傳播與擁堵、網路搜尋、運輸過程、疾病傳播、謠言的傳播、輿論形成…
  • 博弈與其他社會行為：囚徒困境、少數者博弈…
  • 其他過程：電力網的級聯失效等…

推薦閱讀：

相關文章