第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）：一个突变细菌继续敲除基因后会死而复生，继续繁殖，相当于林火模型里放任小火堆