1、復(fù)雜網(wǎng)絡(luò)

復(fù)雜系統(tǒng)：整體是其各部分的總和以及各部分間的 交互。

如何研究網(wǎng)絡(luò)：圖論。

隨機圖：G(n,p)，具有 n 個節(jié)點、任意兩個節(jié)點間以概率 p 存在連邊的圖。

如何研究 復(fù)雜網(wǎng)絡(luò)：統(tǒng)計物理 + 計算科學。傳統(tǒng)圖論不再適合于復(fù)雜網(wǎng)絡(luò)的研究。

網(wǎng)絡(luò)中節(jié)點連接模式：同配，相似而相連；異配，相異而相連。

社區(qū)結(jié)構(gòu)：“內(nèi)部連接緊密、外部連接稀疏” 的節(jié)點集合，高度重疊、相互嵌套。

網(wǎng)絡(luò)中存在大量三角形，形成 結(jié)構(gòu)平衡，是網(wǎng)絡(luò)演化的微動力。

小世界模型：

• 隨機網(wǎng)絡(luò)：低聚集性，短直徑
• 規(guī)則網(wǎng)絡(luò)：高聚集性，長直徑

偏好連接：BA模型

• 生長
• 偏好連接：富者愈富

2、圖排序

將節(jié)點按照重要度排序：

• 介數(shù)中心度

  通過節(jié)點 v 的最短路徑的期望個數(shù) 例子

• 距離中心度

  定義：節(jié)點 x 到其他節(jié)點距離之和的倒數(shù)。

  另一種定義：距離倒數(shù)的和。克服不連通圖面臨的問題。

• 譜中心度

  網(wǎng)絡(luò)鄰接矩陣的主特征值對應(yīng)的特征向量

• Katz中心度是泛化的譜中心度

PageRank

直觀解釋：被很多 重要 頁面 指向 的頁面是 重要 的頁面。

計算方法：任意給定一個初始歸一化向量，反復(fù)左乘轉(zhuǎn)移概率矩陣，直至收斂。

保證收斂充分條件，措施：

• 各態(tài)歷經(jīng)性：任意兩個節(jié)點，都是雙向可達的；非周期的。
• 不可約簡

PageRank收斂特性，例子：

• 收斂速度快。一般100輪之內(nèi)會收斂。
• 分塊收斂。網(wǎng)絡(luò)具有局部聚集特性，同一個塊內(nèi)的節(jié)點，其PageRank值
  收斂速度相近。
• 序收斂比值收斂更快

個性化PageRank：隨機跳轉(zhuǎn)向量使用任意非負歸一化向量代替，實現(xiàn)排序的個性化。例子

HITS

Hub：導(dǎo)出鏈接

Authority：導(dǎo)入鏈接

基本假設(shè)：

• 被很多高hub頁面指向的頁面具有高authority值
• 指向很多高authority頁面的頁面具有高hub值