1、复杂网络

复杂系统：整体是其各部分的总和以及各部分间的 交互。

如何研究网络：图论。

随机图：G(n,p)，具有 n 个节点、任意两个节点间以概率 p 存在连边的图。

如何研究 复杂网络：统计物理 + 计算科学。传统图论不再适合于复杂网络的研究。

网络中节点连接模式：同配，相似而相连；异配，相异而相连。

社区结构：“内部连接紧密、外部连接稀疏” 的节点集合，高度重叠、相互嵌套。

网络中存在大量三角形，形成 结构平衡，是网络演化的微动力。

小世界模型：

• 随机网络：低聚集性，短直径
• 规则网络：高聚集性，长直径

偏好连接：BA模型

• 生长
• 偏好连接：富者愈富

2、图排序

将节点按照重要度排序：

• 介数中心度

  通过节点 v 的最短路径的期望个数 例子

• 距离中心度

  定义：节点 x 到其他节点距离之和的倒数。

  另一种定义：距离倒数的和。克服不连通图面临的问题。

• 谱中心度

  网络邻接矩阵的主特征值对应的特征向量

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

PageRank

直观解释：被很多 重要 页面 指向 的页面是 重要 的页面。

计算方法：任意给定一个初始归一化向量，反复左乘转移概率矩阵，直至收敛。

保证收敛充分条件，措施：

• 各态历经性：任意两个节点，都是双向可达的；非周期的。
• 不可约简

PageRank收敛特性，例子：

• 收敛速度快。一般100轮之内会收敛。
• 分块收敛。网络具有局部聚集特性，同一个块内的节点，其PageRank值
  收敛速度相近。
• 序收敛比值收敛更快

个性化PageRank：随机跳转向量使用任意非负归一化向量代替，实现排序的个性化。例子

HITS

Hub：导出链接

Authority：导入链接

基本假设：

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