第12章 网络分析

12.1 节点属性

• 最早是七桥问题
• 网络里节点（node）与连接（link）对应图论里的交点（vertex）与边（edge）
• (N,L)表示一个包含节点与连接的系统
• 节点的度指的是节点对内对外的连接数
• 网络的度指的是所有节点的平均度，无方向的除2
• 均值 $<x^n> = \frac{x_1^n+x_2^n+...+x_N^n}{N} = \frac{1}{N}\sum_{i=1}^N x_i^n$
• 方差 $\sigma_x = \sqrt{\frac{1}{N}\sum_{i=1}^N (x_i-<x>)^2}$
• 度的概率分布 $p_x = \frac{1}{N}\sum_i \delta_{x,x_i}$ $\sum_ip_x = 1$
• 连接矩阵 $A_{ij}$ $A_{ij} = 1$ 表示点有链接 无方向的上下矩阵对称
• 非加权网络中$A_{ij}$ 等于 1 或 0
• 无方向网络$A_{ij} = A_{ji}$
• 连接矩阵通常是稀疏的
• 全连接网络 $L_{max} = \frac{N(N-1)}{2}$ 平均度 $<k> = N-1$
• 密度，存在的边与可能存在边的比值
• 介数中心性，它代表了某节点与其他节点之间的互动程度，具有较高介数中心性的节点控制网络信息流
• 平均路径长度，表示网络的平均节点两两最短距离
• 半径，表示网络的最大的节点两两最短距离
• 组分，几个子网络
• 二分图，顶点可分成互斥独立集U和V
• 聚集系数，邻居互相连接的比例 $C_i = \frac{2e_i}{k_i(k_i-1)}$ $C_i =1$ 表示全连接，0表示全不连接，你朋友互相认识的概率

12.2 网络集群

• 假设1:集群存在与节点的连接关系中
• 假设2:集群内部联通度高
• 假设3:随机网络里没有集群
• 假设4:最大模块假设 $M=\sum_{c=1}^{n_c}[\frac{l_c}{L}-(\frac{k_c}{2L})^2]$
• 集群是否存在无法验证，所以只有假设
• 集群存在共享节点
• 算法很多， Louvain 与 the Infomap 比较快（$o(NlogN)$），cfinder 比较慢($o(e^N)$)
• 集群也存在生成与进化问题
• 模块化指数（modularity index）群组内边的比例 $Q = \frac{1}{2m}(A_{ij}-\frac{k_ik_j}{2m})\delta(c_i,c_j)$
• m 是总边数，$\delta(c_i,c_j)$ 是Kroenecker delta function，当两个节点属于一个模块时为1，否则为0
• 寻找集群本质是最大化模块化指数，目前并无最优算法
• Newman & Girvan 2004 利用边介数来寻找社群
• Clauset et al. 2004 分层算法，对大网络稀疏网络设计
• Pons & Latapy 2005 基于随机行走的凝聚算法
• Reichardt & Bornholdt 2006 基于磁子低能态算法
• Newman 2006 基于模块矩阵与特征向量的算法
• 同质性（homophily 或 assortment），考虑节点性质的均一性
• 同质化系数（assortment coefficient）$r=\frac{\sum_{ij}(A_{ij}-k_ik_j/2,)x_ix_j}{\sum_{ij}(k_i\delta_{ij}-k_ik_j/2,)x_ix_j}$，其中$k_i\delta_{ij}$ 是节点i排除与节点j相连后的度，类似皮尔逊相关系数，越大均质化程度越高

12.3 随机网络模型

• 任意两点链接概率固定，符合二项分布的概率，度取决于概率与节点数
• 稀疏网络近似符合泊松分布，参数只有平均度
• 100点之下还是用二项分布
• 度是泊松分布
• 随机网络里出现高度节点的概率很低，与现实不符
• 平均度为1，也就是概率为$\frac{1}{N}$时，随机网络可出现大节点。小于1时网络高度节点的增长赶不上节点数增长。到了1时出现临界点，大的节点大概是 $N^{\frac{2}{3}}$ 。当平均度达到 $lnN(p>lnN/N)$ 时，所有节点连接在一起。
• 真实世界里平均度大于1小于$lnN$，也就是存在大节点，但并不完全贯通，处于亚临界与全联通之间，为超临界状态
• 随机网络里节点数固定，单总距离数 $N(d)\approx 1+<k>+<k>^2+...+<k>^d = \frac{<k>^{d+1}-1}{<k>-1}$
• 最大距离 $N(d_{max})\approx N \approx <k>^{d_{max}}$ 距离 $d_{max} \approx\frac{lnN}{ln<k>}$
• 网络连接越密集，平均距离越短
• 互联网平均距离 $<d> \approx 0.35+0.89lnN$
• 小世界特性，随机网络里平均距离比较短
• 聚集系数，邻居互相连接的比例 $C_i = \frac{2<L_i>}{k_i(k_i-1)} = p = \frac{<k>}{N}$
• Watts-Strogatz 小世界模型，低平均距离与高聚集系数，处于完全聚集长距离的正则网络与不聚集短距离的随机网络之间

12.4 无尺度网络

• 度的概率分布事符合幂律的 $log p_k = -\gamma logCk+b$ ，其中$\gamma$是度指数
• 因为 $\sum_{k=1}^\infty p_k = 1$，所以 $C = \frac{1}{\sum_{k=1}^{\infty}k^{-\gamma}} = \frac{1}{\zeta(\gamma)}$
• 后面那个是 Riemann-zeta 函数，因此概率 $p_k = \frac{k^{-\gamma}}{\zeta(\gamma)}$
• 最大的度 $k_{max} = k_{min}N^{\frac{1}{\gamma -1}}$ 节点数越多，最大节点数越大，比随机网络大很多
• 无尺度主要是说n阶矩的分布 $<k^n> = C\frac{k_{max}^{n-\gamma+1} - k_{min}^{n-\gamma+1}}{n-\gamma+1}$ ，多数无尺度网络的 $\gamma$ 在2-3之间，因此除了一阶矩以外，所有的高阶矩都会非常大，随机网络则有尺度
• 超小特性，平均距离要比随机网络小很多，$\gamma =2$ 平均距离是常数，2-3之间为$lnlnN$，3为$\frac{lnN}{lnlnN}$，大于3为$lnN$（小世界网络）。在无尺度网络里大节点会缩小距离。

12.5 无尺度的生成 - Barabási-Albert 模型

• 网络的生长存在选择性依附，新节点会依附在度更高的节点上
• 生长概率 $\prod (K_i) = \frac{k_i}{\sum_jk_j}$
• 度动力学 $\frac{dk_i}{dt} = m\prod(k_i) = m\frac{k_i}{\sum_{j=1}^{N-1}k_j}$
• m个连接 $\sum_{j=1}^{N-1}k_j = 2mt-m$
• 整理后得到 $k_i(t) = m(\frac{t}{t_i})^{\beta}$，$\beta$ 为0.5

12.6 网络的进化 - Bianconi-Barabási 模型

• 选择依附会导致后来的成为节点概率低，无法解释现实世界里后来居上的现象
• 生长概率$\prod (K_i) = \frac{\eta_ik_i}{\sum_j\eta_i k_j}$ $\eta$ 代表适应度（fitness）
• 后来者适应度如果高，其度也很超过先来的
• 互联网适应度与概率指数分布，期刊适应度峰分布
• 物理机制可对应 波色-爱因斯坦凝聚态，适应度对应能量，新节点对应能级上新粒子，节点度对应能级上的粒子数。波色-爱因斯坦凝聚态可以无限吸引新粒子，因此不再无尺度，出现强者恒强
• 还要考虑节点删除与老化

12.7 度相关现象

• 大节点似乎不连接大节点，小节点总是连接小节点
• 两个节点连接概率 $p_{k,k'} = \frac{kk'}{2L}$
• 神经网络是随机连接，符合概率
• 匹配性网络（assortative network），大节点互相连接，小节点只连接小节点，光环效应
• 非匹配性网络（disassortative network），大节点连接小节点但互相不连接
• 度相关矩阵 $e_{ij}$且$\sum_{i,j}e_{ij} = 1$
• 度的概率 $q_k = \frac{kp_k}{<k>}$，因此 $\sum_je_{ij} = q_i$
• 单一节点度相关性 $k_{nn}(k_i) = \frac{1}{k_i}\sum_{j=1}^NA_{ij}k_j$
• 网络总相关性 $k_{nn}(k) = \sum_{k'}k'P(k'|k)$
• 神经网络里 $k_{nn}(k)=\frac{<k^2>}{k}$
• 近似公式 $k_{nn}(k)=ak^{\mu}$
• 神经网络 $\mu = 0$，匹配性网络科学家合作网络 $\mu>0$，非匹配性网络代谢网络 $\mu<0$
• 度相关系数 $r=\sum_{jk}\frac{jk(e_{jk}-q_{j}q_{k})}{\sigma^2}$，其中$\sigma^2=\sum_{k}k^2q_k - [\sum_kkq_k]^2$
• 度相关系数$r$与相关指数$\mu$假设不同但基本相关
• 朋友悖论：朋友总比你受欢迎
• 真实网络存在度相关，改变度相关会改变网络性质，对网络功能的进一步描述
• 模型生成的配置模型与隐参数模型可根据度来生成模型
• 静态生成模型是非匹配或随机网络
• 当$\gamma>3$，动态生成模型可能是弱匹配网络

12.8 网络稳健性

• 去掉节点后网络功能性的影响，复原能力与冗余机制是稳健性保障
• 渗透理论（percolation），少量节点去除后不影响整体，但超过关键点后会碎裂成小集群，林火理论
• Malloy-Reed 法则：$\frac{<k^2>}{k}>2$ 判断是否存在大组分
• 随机错误 $f_c = 1-\frac{1}{\frac{<k^2>}{<k>}-1}$
• 随机网络 $f_c^{ER}=1-\frac{1}{<k>}$ 无尺度网络二阶矩很大，所以容错高
• 提高稳健性 $f_c>f_c^{ER}$
• 遭受攻击时 $f_c^{\frac{2-\gamma}{1-\gamma}}=2+\frac{2-\gamma}{1-\gamma}k_{min}(f_c^{\frac{3-\gamma}{1-\gamma}}-1)$
• 如果优先攻击高度节点，那么稳健性会很低，随机进攻影响不大
• 攻击会造成级联反应，最稳健的网络一个中心节点，其余节点度相同，非无尺度网络
• 拉萨路效应（Lazarus effect）：一个突变细菌继续敲除基因后会死而复生，继续繁殖，相当于林火模型里放任小火堆

12.9 网络回归

• 网络间的回归分析
• Mantel Test 可用来检测矩阵相关性
• Quadratic Assignment Procedure 是Mantel检测的回归版
• The Multiple Regression Quadratic Assignment Procedure 是QAP的多元回归版

12.10 网络扩散行为

• 节点间连接存在系统意义，有利于物质能量信息的传输
• 不合群传播通过试错，后面越来越慢
• 社群传播通过模仿，S型学习曲线，存在高速增长

12.11 网络可视化

• force-directed algorithm 最优化布局：节点间距离最大，有连接的节点距离最小
• 常见的有 Fruchterman-Reingold (1991) 算法、Kamada & Kawai (1989) 算法、Davidson & Harel (1996) 算法及“GEM” (Frick et al. 1995) 算法