如何用Python高效将网站链接集合转换为有向图并生成邻接矩阵

问题背景 #

我有一组格式如下的网站及其链接数据：

{
  "thisite.com": ["test.com", "example.com"],
  "test.com": ["examples.com"]
  ...
}

我需要将其转换为有向图，并且要能生成邻接矩阵。我了解NetworkX等库，但不知道高效实现方法。

当前解决方案 #

我目前用pygraphviz实现的代码如下，但在大规模数据下效率不足：

def loadgraph(fname):
        G=pg.AGraph(directed=True)
        for line in open(fname):
            j=json.loads(line)
            url=j["url"]
            G.add_node(url)
            for linked_url in j["linkedurls"]:
                G.add_edge(url,linked_url)
        return G

请问是否存在更高效的实现方式，或是当前方案已是最优解？

优化方案分析 #

1. 切换到NetworkX做批量操作 #

pygraphviz单节点/单边添加的底层开销较高，NetworkX支持批量添加节点和边，能显著提升效率：

import json
import networkx as nx

def load_graph_networkx(fname):
    G = nx.DiGraph()
    # 一次性加载全量数据（文件不大时），避免逐行解析的重复开销
    with open(fname, 'r') as f:
        data = json.load(f)
    
    # 收集所有唯一节点并批量添加
    all_nodes = set(data.keys())
    for links in data.values():
        all_nodes.update(links)
    G.add_nodes_from(all_nodes)
    
    # 批量生成边列表并添加
    edges = []
    for source, targets in data.items():
        edges.extend([(source, target) for target in targets])
    G.add_edges_from(edges)
    
    return G

如果文件过大无法一次性加载，可分块读取，但单块内依然用批量操作处理，比逐行单条添加高效。

2. 流式解析JSON优化内存与速度 #

若每行是独立的JSON对象（而非整个文件是一个大JSON），用ijson流式解析可降低内存占用，同时提升解析速度：

import ijson
import networkx as nx

def load_graph_ijson(fname):
    G = nx.DiGraph()
    nodes = set()
    edges = []
    
    with open(fname, 'r') as f:
        for obj in ijson.items(f, ''):
            url = obj["url"]
            nodes.add(url)
            for linked_url in obj["linkedurls"]:
                nodes.add(linked_url)
                edges.append((url, linked_url))
    
    G.add_nodes_from(nodes)
    G.add_edges_from(edges)
    return G

3. 直接生成邻接矩阵（跳过图结构） #

如果最终只需要邻接矩阵，可直接构建矩阵，省去图库的中间层开销：

import json
import numpy as np

def build_adjacency_matrix(fname):
    with open(fname, 'r') as f:
        data = json.load(f)
    
    # 映射节点到索引
    all_nodes = set(data.keys())
    for links in data.values():
        all_nodes.update(links)
    node_to_idx = {node: idx for idx, node in enumerate(all_nodes)}
    size = len(node_to_idx)
    
    # 初始化并填充邻接矩阵
    adj_matrix = np.zeros((size, size), dtype=int)
    for source, targets in data.items():
        source_idx = node_to_idx[source]
        for target in targets:
            target_idx = node_to_idx[target]
            adj_matrix[source_idx][target_idx] = 1
    
    return adj_matrix, node_to_idx

这种方式内存占用更低，速度更快，适合超大规模数据。

4. 原pygraphviz方案的小优化 #

若必须使用pygraphviz，改用批量添加节点和边，减少底层API调用次数：

import json
import pygraphviz as pg

def loadgraph_optimized(fname):
    G = pg.AGraph(directed=True)
    nodes = set()
    edges = []
    
    with open(fname, 'r') as f:
        for line in f:
            j = json.loads(line)
            url = j["url"]
            nodes.add(url)
            for linked_url in j["linkedurls"]:
                nodes.add(linked_url)
                edges.append((url, linked_url))
    
    G.add_nodes_from(nodes)
    G.add_edges_from(edges)
    return G

邻接矩阵生成 #

用NetworkX生成邻接矩阵时，推荐用稀疏矩阵节省内存（适合大规模图）：

G = load_graph_networkx(fname)
# 稠密矩阵
dense_adj = nx.to_numpy_array(G)
# 稀疏矩阵（优先选择）
sparse_adj = nx.to_scipy_sparse_matrix(G)

内容的提问来源于stack exchange，提问作者R3FL3CT