第一章：图论

完全图又被称为团。

Metcalfe's Law：

Metcalfe's law states that the value of a telecommunications network is proportional to the square of the number of connected users of the system (\(n^2\)).

网络的价值与网络节点个数的平方成正比。

互联网估值泡沫：相对价值而言，其成本和用户数是线性相关，所以只要当N足够大，价值总会超越成本。

此处网络的价值主要考虑的是和网络的链接数成线性相关，而1）大多数网络是稀疏的 2）链接是带权的 这两点限制了Metcalfe‘s Law.

图的直径：网络中所有最短路径的最大长度，即所有节点对之间的最大距离。

集聚系数 \(C\)：一个节点的邻居节点之间彼此连接的稠密程度。

度为\(k_i\)的节点，\(L_i\)表示节点i的\(k_i\)个邻居之间的链接数。注意集聚系数的取值在[0,1]之间。

\[C_i=\frac{2L_i}{k_i(k_i - 1)}
\]

\(C_i\) 表示节点i的任意两个邻居彼此相连的概率。

枢纽节点倾向于和小度节点相联，使得该网络呈现出星型的轮辐结构，这源于度相关性。

度相关性影响着很多基于网络的过程，包括信息扩散过程、控制网络所需的驱动节点个数等。

平均集聚系数：\(=\frac{1}{N}\sum_{i=1}^{N}C_i\) 概率化解释是：随机选择一个节点，其两个邻居彼此相连的概率。

全局集聚系数：global clustering coefficient 也叫传递三元组比例。

\[C_\triangle=\frac{3*三角形的个数}{联通三元组的个数（就是联通的两条边）}
\]