networkx

NetworkX - 网络分析与图论

NetworkX 是分析复杂网络的首选库。它将图视为灵活的容器，其中包含节点（可以是任何可哈希对象）和边，边可以携带任意元数据。

适用场景

• 分析社交、生物或基础设施网络。
• 计算路径指标（最短路径、直径、流量）。
• 衡量节点的重要性（中心性、PageRank）。
• 检测网络中的社区和簇。
• 生成随机图模型（Erdős-Rényi、Barabási-Albert）。
• 查找连通分量和团。
• 设计并优化路由或依赖树。

参考文档

官方文档：https://networkx.org/
算法参考：https://networkx.org/documentation/stable/reference/algorithms/index.html
搜索模式：nx.Graph、nx.shortest_path、nx.degree_centrality、nx.connected_components

核心原则

图类型

类	描述
Graph	无向图；如果重复添加自环，则会忽略。
DiGraph	有向图；边具有特定方向（A → B ≠ B → A）。
MultiGraph	无向图；同一对节点之间可以有多条边。
MultiDiGraph	有向图；节点之间可以有多条有向边。

节点和边

• 节点：可以是任何可哈希的 Python 对象（字符串、数字、元组，甚至对象）。
• 边：表示两个节点之间的关系。可以存储权重、容量或标签等属性。

快速参考

安装

pip install networkx matplotlib scipy

标准导入

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

基本模式 - 创建与分析

import networkx as nx

# 1. Create a graph
G = nx.Graph()

# 2. Add edges (nodes are created automatically)
G.add_edge("A", "B", weight=4.5)
G.add_edges_from([("B", "C"), ("C", "A"), ("C", "D")])

# 3. Analyze
print(f"Nodes: {G.number_of_nodes()}")
print(f"Shortest path A to D: {nx.shortest_path(G, 'A', 'D')}")

# 4. Draw
nx.draw(G, with_labels=True)

关键规则

✅ 应该做

• 使用带权边 - 用于任何现实世界的距离或成本分析。
• 检查连通性 - 运行假设图只有一个连通分量的算法前，务必验证 nx.is_connected(G)。
• 设置正确的类 - 如果交互方向很重要（例如网站链接、代谢通路），请使用 DiGraph。
• 使用稀疏矩阵 - 对于大量计算，可使用 nx.to_scipy_sparse_array 导出为 SciPy 稀疏矩阵。
• 访问属性 - 使用 G.nodes[n]['attr'] 或 G.edges[u, v]['attr'] 存储或检索元数据。
• 节点不可变性 - 确保节点对象可哈希，并且在用作键时其状态不会改变。

❌ 不要做

• 用于高性能可视化 - nx.draw 适用于小型调试图。大型可视化请使用 Gephi 或 Cytoscape。
• 手动编写路径循环 - 避免自行编写 BFS/DFS；NetworkX 的内置算法已经过高度优化。
• 在节点中存储大型对象 - 保持节点简单（ID）；如有可能，将复杂数据存储在单独的字典中以节省内存。
• 忽略图生成器 - 不要手动创建复杂的合成图；请使用 nx.random_graphs。

反模式（绝不要）

import networkx as nx

# ❌ BAD: Manual neighbor iteration for degree calculation
count = 0
for n in G.nodes():
    for neighbor in G.neighbors(n):
        count += 1

# ✅ GOOD: Use built-in degree property
degrees = dict(G.degree())

# ❌ BAD: Re-calculating shortest paths in a loop
for target in targets:
    path = nx.dijkstra_path(G, source, target) # Re-scans graph every time

# ✅ GOOD: Calculate single-source shortest paths once
paths = nx.single_source_dijkstra_path(G, source)
# 'paths' now contains the shortest path to every reachable node

# ❌ BAD: Using lists for edges in large graphs
# (Creating a graph from a massive edge list one by one is slow)

# ✅ GOOD: Bulk loading
G.add_edges_from(edge_list)

深入了解算法

最短路径和流量

# Shortest path with weights (Dijkstra)
path = nx.shortest_path(G, source="A", target="D", weight="weight")
length = nx.shortest_path_length(G, source="A", target="D", weight="weight")

# All-pairs shortest paths (returns a generator)
all_paths = dict(nx.all_pairs_dijkstra_path(G))

# Max Flow / Min Cut
from networkx.algorithms.flow import preflow_push
flow_value, flow_dict = nx.maximum_flow(G, "source_node", "sink_node", capacity="cap")

中心性和重要性

# Degree Centrality (fraction of nodes it's connected to)
deg_cent = nx.degree_centrality(G)

# Betweenness Centrality (importance as a bridge/bottleneck)
bet_cent = nx.betweenness_centrality(G)

# PageRank (influence in directed networks)
pagerank = nx.pagerank(G, alpha=0.85)

# Eigenvector Centrality
eig_cent = nx.eigenvector_centrality(G)

社区检测和聚类

# Clustering coefficient (measure of "tightness")
avg_clustering = nx.average_clustering(G)

# Community detection (Girvan-Newman)
from networkx.algorithms import community
comp = community.girvan_newman(G)
top_level_communities = next(comp)

# Louvain Community Detection (standard for large networks)
# requires: pip install python-louvain
communities = community.louvain_communities(G)

连通性和分量

# Undirected components
components = list(nx.connected_components(G))
largest_cc = max(components, key=len)

# Directed connectivity
is_strong = nx.is_strongly_connected(DG) # Path in both directions
is_weak = nx.is_weakly_connected(DG)     # Path if direction is ignored

# Cliques (fully connected subgraphs)
cliques = list(nx.find_cliques(G))

图 I/O 与互操作性

格式和转换器

# Reading/Writing files
nx.write_gexf(G, "network.gexf")   # For Gephi
nx.write_graphml(G, "data.graphml") # For general graph tools
G = nx.read_edgelist("edges.txt")   # From simple text file

# Integration with Pandas
df = nx.to_pandas_edgelist(G)
G_new = nx.from_pandas_edgelist(df, source='source', target='target', edge_attr='weight')

# Integration with NumPy/SciPy
adj_matrix = nx.to_numpy_array(G)
sparse_adj = nx.to_scipy_sparse_array(G)

实用工作流

1. 分析蛋白质-蛋白质相互作用（PPI）网络

def analyze_ppi(edge_list_file):
    G = nx.read_edgelist(edge_list_file)
    
    # 1. Basic stats
    print(f"Network density: {nx.density(G):.4f}")
    
    # 2. Find hubs (high degree)
    degree_dict = dict(G.degree())
    hubs = sorted(degree_dict.items(), key=lambda x: x[1], reverse=True)[:10]
    
    # 3. Find essential clusters
    communities = nx.community.louvain_communities(G)
    
    # 4. Check for articulation points (bottlenecks)
    bottlenecks = list(nx.articulation_points(G))
    
    return hubs, communities, bottlenecks

2. 带约束的交通路由

def find_route(G, start, end, max_load):
    """Find shortest path that respects a capacity constraint."""
    # Filter edges by capacity
    view = nx.subgraph_view(G, filter_edge=lambda u, v: G[u][v]['capacity'] >= max_load)
    
    if not nx.has_path(view, start, end):
        return None
    
    return nx.shortest_path(view, start, end, weight='distance')

3. 可视化层级结构

def plot_tree(G, root):
    """Custom layout for tree-like structures."""
    pos = nx.spring_layout(G) # Basic layout
    # Or use graphviz for better tree layouts
    # pos = nx.nx_agraph.graphviz_layout(G, prog='dot')
    
    plt.figure(figsize=(12, 8))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', 
            node_size=500, font_size=10, arrowsize=20)
    plt.show()

性能优化

使用图视图

筛选节点/边时，不要创建图的副本，而应使用“视图”，其时间和内存开销均为 O(1)。

# Create a view of the graph with only heavy edges
heavy_edges = nx.subgraph_view(G, filter_edge=lambda u, v: G[u][v]['weight'] > 10)

高效访问节点

遍历节点及其属性时，请使用 data=True。

# Faster than calling G.nodes[n] inside the loop
for n, attrs in G.nodes(data=True):
    if attrs.get('type') == 'target':
        do_something(n)

常见问题与解决方案

迭代期间修改字典

# ❌ Problem: Changing the graph while looping over nodes
for n in G.nodes():
    if G.degree(n) == 0:
        G.remove_node(n) # Error!

# ✅ Solution: Convert nodes to a list first
for n in list(G.nodes()):
    if G.degree(n) == 0:
        G.remove_node(n)

简单图中的自环和多重边

# ❌ Problem: Adding a second edge between A and B in nx.Graph() 
G.add_edge("A", "B", weight=10)
G.add_edge("A", "B", weight=20) # Overwrites the first weight!

# ✅ Solution: Use MultiGraph if multiple relations exist
MG = nx.MultiGraph()
MG.add_edge("A", "B", weight=10)
MG.add_edge("A", "B", weight=20) # Both are preserved

流算法中的方向性

# ❌ Problem: Running PageRank on an Undirected graph
# It works, but it's just a scaled degree centrality.

# ✅ Solution: Ensure you use DiGraph for influence metrics
DG = nx.DiGraph(G) # Converts undirected to directed with symmetric edges

NetworkX 在易用性和算法深度之间实现了完美平衡。无论你是在解决一个小型逻辑谜题，还是在分析一个复杂的生物系统，它都能提供理解数据底层结构所需的工具。