网络分析：图论与社会网络分析基础

网络分析是研究复杂系统结构的重要工具，广泛应用于社交网络、生物网络、信息网络等领域。

1. 基本概念

1.1 图的定义

一个图 $G = (V, E)$ 由顶点集 $V$ 和边集 $E$ 组成。

图的类型：

无向图 vs 有向图
加权图 vs 无权图
简单图 vs 多重图

1.2 图的表示方法

邻接矩阵

对于有 $n$ 个顶点的图，邻接矩阵 $A$ 是一个 $n \times n$ 矩阵，其中： $$ A_{ij} = \begin{cases} 1 & \text{如果顶点 i 和 j 之间有边} \ 0 & \text{否则} \end{cases} $$

邻接表

更节省空间的表示方法，特别适合稀疏图。

2. 网络的基本性质

2.1 度分布

顶点度 $k$ 的概率分布 $P(k)$，对于许多真实网络服从幂律分布： $$P(k) \sim k^{-\gamma}$$

2.2 聚类系数

衡量节点的邻居之间相互连接的程度： $$C_i = \frac{2L_i}{k_i(k_i-1)}$$ 其中 $L_i$ 是节点 $i$ 的邻居之间的边数。

2.3 路径与距离

最短路径长度：两个节点之间的最小边数
平均路径长度：所有节点对之间最短路径的平均值
直径：最长最短路径的长度

2.4 中心性指标

度中心性：$C_D(i) = \frac{k_i}{n-1}$
接近中心性：$C_C(i) = \frac{n-1}{\sum_{j \neq i} d(i,j)}$
介数中心性：$C_B(i) = \sum_{s \neq i \neq t} \frac{\sigma_{st}(i)}{\sigma_{st}}$
特征向量中心性：$Ax = \lambda x$

3. 网络类型与模型

3.1 规则网络

完全图
环状图
网格图

3.2 随机网络（Erdős-Rényi模型）

每条边以概率 $p$ 独立存在：

平均度：$\langle k \rangle = p(n-1)$
度分布：二项分布（大n时近似泊松分布）

3.3 小世界网络（Watts-Strogatz模型）

结合了高聚类系数和短平均路径长度：

从环状规则网络开始
以概率 $p$ 重连每条边

3.4 无标度网络（Barabási-Albert模型）

通过优先连接机制生成：

增长：网络逐渐增加新节点
优先连接：新节点连接已有节点的概率与节点度成正比

4. 社区检测

4.1 模块度

衡量社区划分质量的指标： $$Q = \frac{1}{2m} \sum_{ij} \left[ A_{ij} - \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)$$ 其中 $m$ 是总边数，$c_i$ 是节点 $i$ 的社区。

4.2 常用算法

Girvan-Newman算法：基于边介数
Louvain算法：基于模块度优化
标签传播算法：基于局部信息
谱聚类方法：基于图拉普拉斯矩阵

5. Python实现：NetworkX基础

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
from collections import Counter

# 创建图
G = nx.Graph()  # 无向图
# G = nx.DiGraph()  # 有向图

# 添加节点和边
G.add_nodes_from([1, 2, 3, 4, 5])
G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4), (4, 5)])

# 基本属性
print(f"节点数: {G.number_of_nodes()}")
print(f"边数: {G.number_of_edges()}")
print(f"节点度: {dict(G.degree())}")

# 可视化
plt.figure(figsize=(8, 6))
pos = nx.spring_layout(G, seed=42)
nx.draw(G, pos, with_labels=True, node_color='lightblue', 
        node_size=500, font_size=12, font_weight='bold')
plt.title("简单网络图")
plt.show()