关于图的结构分析
图的结构分析通过多个维度揭示网络的特性。度分析关注节点度数来识别最活跃的节点；图距离度量节点间的最短路径长度；中心性衡量节点在网络中的重要性；社区发现紧密连接的节点群体。
这些方法为理解和分析复杂网络提供了强有力的工具， 广泛应用于社交网络分析、生物信息学、交通规划等领域。
✦
17.1
度分析
节点度数分布与重要性
度分析（Degree Analysis）通过节点的度数（连接边的数量） 来分析图的连通性和节点的重要性。 度数高的节点通常在网络中扮演着关键角色， 它们可能是信息传播的枢纽或社交网络中的意见领袖。
📊 基本概念
• 度数：节点连接的边数
• 度序列：按度数排序的节点
• 度分布：不同度数的节点数量
• 平均度：图中所有度数的平均值
🎯 应用场景
• 社交网络：识别KOL
• 交通网络：找出枢纽站
• 生物网络：关键蛋白质
• 互联网：核心路由器
💻 NetworkX
G.degree()
dict(G.degree())
sorted(..., key=lambda x: x[1])
可视化方法
柱状图
展示每个节点的度数
直方图
展示度数分布情况
颜色渲染
用颜色表示度数大小
✦
17.2
距离度量
图距离、离心率、中心点
图距离是两节点间最短路径的长度。离心率是节点到所有其他节点的最大距离。图直径是所有离心率的最大值，图半径是所有离心率的最小值。 离心率等于图半径的节点称为中心点， 离心率等于图直径的节点称为边缘点。
📐 核心概念
图距离 d(u,v)
节点u到节点v的最短路径长度
离心率 e(v)
节点v到所有其他节点的最大距离
图距离矩阵
记录所有节点对间的最短距离
💻 NetworkX函数
距离计算
nx.shortest_path_length(G, u, v)
nx.shortest_path(G, u, v)
离心率与直径
nx.eccentricity(G)
nx.diameter(G)
nx.radius(G)
中心与边缘
nx.center(G)
nx.periphery(G)
🎯 实际意义
中心点
- • 到所有节点距离最近
- • 信息传播最快
- • 网络核心位置
边缘点
- • 到某些节点距离最远
- • 位于网络外围
- • 相对孤立
✦
17.3
中心性
衡量节点重要性的多维度指标
中心性（Centrality）用来描述节点在图中有多"中心"或"重要"。 不同的中心性度量从不同角度评估节点的重要性： 度中心性看连接数量，介数中心性看桥梁作用，紧密中心性看平均距离。
🎯 度中心性
定义
节点度数 / (n-1)
含义
直接连接的节点数量
适用
社交影响力、枢纽识别
🌉 介数中心性
定义
节点在最短路径上的出现频率
含义
充当"桥梁"的程度
适用
信息控制、瓶颈识别
📍 紧密中心性
定义
平均最短距离的倒数
含义
到所有节点的平均接近度
适用
信息传播、配送中心
⭐ 特征向量中心性
除了上述三种中心性，还有特征向量中心性（Eigenvector Centrality）， 它不仅考虑节点的连接数量，还考虑连接节点的重要性。 一个节点如果连接到多个重要节点，其特征向量中心性就会很高。
PageRank算法
• Google的核心排名算法基于特征向量中心性
• 不仅看链接数量，更看链接质量
• 本书后续章节将详细介绍
nx.eigenvector_centrality(G)
✦
17.4
图的社区
发现紧密连接的节点群体
图中的社区（Community）是紧密连接的节点集合， 这些节点间有较多的内部连接，而相对较少的外部连接。 社区检测算法可以自动发现网络中的模块结构， 揭示系统的组织方式和功能划分。
🔍 常用算法
Girvan-Newman
• 基于边介数的层次聚类
• 迭代移除介数最高的边
• 自底向上构建社区层次
Louvain
• 优化模块度的贪心算法
• 计算效率高，适合大图
• 产生层次化社区结构
Label Propagation
• 标签传播算法
• 近线性时间复杂度
• 适合超大规模网络
📊 评估指标
模块度 (Modularity)
• 衡量社区划分质量
• Q ∈ [-1, 1]，越大越好
• Q > 0.3 通常表示明显的社区结构
覆盖率 (Coverage)
• 社区内部边占总边的比例
• 越高表示社区越完整
性能 (Performance)
• 正确分类的节点对比例
• 需要已知真实社区结构
🎯
实际应用
社交网络
- • 兴趣小组识别
- • 好友推荐
- • 社群运营
生物网络
- • 蛋白质功能模块
- • 基因调控网络
- • 代谢通路分析
推荐系统
- • 用户分群
- • 商品聚类
- • 协同过滤
网络安全
- • 僵尸网络检测
- • 异常行为识别
- • 攻击源追踪
✦
本章小结
图的结构分析通过多个维度揭示网络的特性和节点的角色。 这些分析方法相互补充，共同构成了理解复杂网络的完整工具箱。
📊 四大分析维度
1.
度分析
节点连接数量，识别活跃节点
2.
距离度量
最短路径、离心率、中心与边缘
3.
中心性
度/介数/紧密/特征向量中心性
4.
社区
发现紧密连接的节点群体
🎯 选择指南
识别关键节点
→ 度中心性、介数中心性
优化传播路径
→ 紧密中心性、图距离
发现组织结构
→ 社区检测算法
识别瓶颈
→ 桥、介数中心性
💡 实践建议
多维度分析
- • 单一指标可能有偏差
- • 结合多种中心性度量
- • 交叉验证结果
可视化辅助
- • 用颜色/大小编码度量值
- • 观察空间分布模式
- • 识别异常节点