数学推导与算法

Brandes 介数算法

节点 $v$ 的介数 $B(v)=\sum_{s\ne v\ne t}\sigma_{st}(v)/\sigma_{st}$，其中 $\sigma_{st}$ 是 $s$ 到 $t$ 的最短路径条数，$\sigma_{st}(v)$ 是其中经过 $v$ 的条数。按定义计算需要先求所有节点对的最短路径并逐对累加，代价为 $O(N^3)$。Brandes（2001）引入单源“依赖值”

$$\delta_s(v)=\sum_{t}\frac{\sigma_{st}(v)}{\sigma_{st}},\qquad B(v)=\sum_{s\ne v}\delta_s(v),$$

并证明它满足递推关系

$$\delta_s(v)=\sum_{w:\,v\in P_s(w)}\frac{\sigma_{sv}}{\sigma_{sw}}\bigl(1+\delta_s(w)\bigr),$$

其中 $P_s(w)$ 是从 $s$ 出发的最短路径上 $w$ 的前驱节点集合。于是对每个源点 $s$：先用 BFS（无权）或 Dijkstra（加权）求出到各点的距离、最短路径条数 $\sigma_{sv}$ 与前驱集合，再按距离从远到近回传依赖值。每个源点的代价为 $O(M)$（无权）或 $O(M+N\log N)$（加权），对全部源点求和即得上文的复杂度。

抽样估计：随机均匀抽取 $k$ 个源点组成集合 $S$，令 $\hat B(v)=\frac{N}{k}\sum_{s\in S}\delta_s(v)$。由于每个源点被抽中的概率为 $k/N$，$\mathbb E[\hat B(v)]=\sum_s\delta_s(v)=B(v)$，即估计无偏；其方差随 $k$ 增大大致按 $1/k$ 减小。高介数节点的依赖值来自很多源点，相对误差较小，这解释了为什么抽样介数对“前几名”的排序更可靠。

力导向布局的力与能量

Fruchterman–Reingold 设理想边长 $\ell=C\sqrt{\text{面积}/N}$，相距 $d$ 的节点之间：

$$f_{\text{attr}}(d)=\frac{d^2}{\ell}\ (\text{仅相连节点}),\qquad f_{\text{rep}}(d)=-\frac{\ell^2}{d}\ (\text{所有节点对}).$$

两力在 $d=\ell$ 时平衡。每次迭代按合力方向移动节点，位移不超过当前“温度”，温度逐步降低。朴素实现每步需计算全部节点对的斥力，代价 $O(N^2)$。

Kamada–Kawai 的能量函数为

$$E=\sum_{i<j}\frac{1}{2}\,\frac{K}{d_{ij}^2}\bigl(\lVert \mathbf x_i-\mathbf x_j\rVert-\ell\, d_{ij}\bigr)^2,$$

其中 $d_{ij}$ 是图上最短路径距离，$\ell$ 是单位边长。权重 $1/d_{ij}^2$ 使近邻之间的距离误差受到更大惩罚。最小化 $E$ 相当于一种加权的多维尺度分析。

ForceAtlas2 的斥力为 $F_r=k_r\,(\deg(i)+1)(\deg(j)+1)/d$，吸引力为 $F_a=d$（LinLog 模式下为 $\log(1+d)$），另加一个把节点拉向中心的“重力”项。斥力中的度因子让枢纽彼此远离，而只连接一个枢纽的低度节点留在其附近。

谱布局的推导

设一维坐标 $\mathbf x\in\mathbb R^N$，希望相连节点尽量靠近：

$$\min_{\mathbf x}\ \frac{1}{2}\sum_{i,j}A_{ij}(x_i-x_j)^2=\mathbf x^{\top}L\mathbf x,\qquad L=D-A .$$

不加约束时 $\mathbf x$ 全部相同即可取到 0，所以加上约束 $\mathbf x^{\top}\mathbf x=1$ 且 $\mathbf x\perp\mathbf 1$（排除平凡解）。由瑞利商的性质，最优解是 $L$ 的第二小特征值对应的特征向量（Fiedler 向量）；二维布局的第二个坐标取与之正交的下一个特征向量，即第三小特征值的特征向量（Hall 1970）。由于 $\mathbf x^{\top}L\mathbf x$ 正是图分割中“割边数”的连续松弛，谱布局与谱聚类有相同的数学基础，这解释了它为何能把社团分得很开（见谱方法与层次聚类）。

稀疏存储的内存

CSR（compressed sparse row）格式用三个数组存储矩阵：非零值 data（长度 nnz）、列索引 indices（长度 nnz）、行指针 indptr（长度 $N+1$）。无向图 nnz $=2M$。以 64 位浮点值和 32 位整数索引计，内存约为 $2M\times(8+4)+4(N+1)$ 字节。代码示例中 $N=20000$、$M=59991$，得到约 2.08 MB；同样大小的稠密矩阵为 $N^2\times8\approx3.2\times10^9$ 字节。对稀疏网络，稀疏存储的优势随 $N$ 线性扩大。

度匹配随机基因集的经验 $p$ 值

设观测统计量为 $T_{\text{obs}}$，$R$ 个度匹配随机集合的统计量为 $T_1,\dots,T_R$。经验 $p$ 值

$$\hat p=\frac{1+\#\{r: T_r\ge T_{\text{obs}}\}}{R+1}.$$

分子分母加 1 保证 $\hat p>0$，可达到的最小 $p$ 值为 $1/(R+1)$（详见零模型与空模型）。度匹配的理由是：度高的基因在几乎任何网络统计量上都占优势，若疾病基因恰好偏向高度（常见于研究较多的基因），不做度匹配会把“度偏倚”误当成“聚集”。