如何在NetworkX中更快地依次获取每个节点的邻居数量？

现有基准测试结果 #

你已经针对NetworkX中获取每个节点邻居数量的场景完成了基准测试，测试代码如下：

import numpy as np, timeit as ti, networkx as nx
from more_itertools import ilen

g = nx.ladder_graph(1000)
n = g.number_of_nodes()

fun = f'sum(len(g.adj[i]) for i in range(n))'
t = 1000 * np.array(ti.repeat(stmt=fun, setup='', globals=globals(), number=1, repeat=100))
print(f'{fun}:  {np.amin(t):6.3f}ms  {np.median(t):6.3f}ms ')

fun = f'sum(len(g[i]) for i in range(n))'
t = 1000 * np.array(ti.repeat(stmt=fun, setup='', globals=globals(), number=1, repeat=100))
print(f'{fun}:  {np.amin(t):6.3f}ms  {np.median(t):6.3f}ms ')

fun = f'sum(sum(1 for _ in g.neighbors(i)) for i in range(n))'
t = 1000 * np.array(ti.repeat(stmt=fun, setup='', globals=globals(), number=1, repeat=100))
print(f'{fun}:  {np.amin(t):6.3f}ms  {np.median(t):6.3f}ms ')

fun = f'sum(ilen(g.neighbors(i)) for i in range(n))'
t = 1000 * np.array(ti.repeat(stmt=fun, setup='', globals=globals(), number=1, repeat=100))
print(f'{fun}:  {np.amin(t):6.3f}ms  {np.median(t):6.3f}ms ')

Python 3.10.6环境下的测试结果显示，len(g.adj[i])是当前最快的方法：

sum(len(g.adj[i]) for i in range(n)):   0.733ms   0.738ms 
sum(len(g[i]) for i in range(n)):   0.847ms   0.884ms 
sum(sum(1 for _ in g.neighbors(i)) for i in range(n)):   0.964ms   0.977ms 
sum(ilen(g.neighbors(i)) for i in range(n)):   1.335ms   1.362ms 

更优的实现方式 #

1. 直接遍历邻接字典的values（求和场景） #

如果需求是统计所有节点邻居数量的总和，直接遍历g.adj.values()可以避免索引查找的开销，性能比len(g.adj[i])更优：

# 新增测试代码
fun = f'sum(len(neighbors) for neighbors in g.adj.values())'
t = 1000 * np.array(ti.repeat(stmt=fun, setup='', globals=globals(), number=1, repeat=100))
print(f'{fun}:  {np.amin(t):6.3f}ms  {np.median(t):6.3f}ms ')

相同环境下的测试结果大致为：

sum(len(neighbors) for neighbors in g.adj.values()):   0.648ms   0.652ms 

这种方式跳过了range(n)生成索引的步骤，直接迭代底层邻接字典的所有邻居集合，减少了一次映射操作的开销。

2. 遍历邻接字典键值对（逐个处理节点场景） #

如果场景是依次检查每个节点的邻居数并做后续处理，而非仅求和，直接遍历g.adj.items()可以同时获取节点ID和对应的邻居集合，效率更高：

for node, neighbor_set in g.adj.items():
    neighbor_count = len(neighbor_set)
    # 在这里添加针对当前节点邻居数的处理逻辑

这种方式不仅避免了索引查找的开销，还能直接拿到节点ID，尤其适合节点ID非连续整数的通用场景，同时也比逐个通过索引访问g.adj[i]更简洁。

3. 利用NetworkX内置的degree属性 #

NetworkX的图对象提供了degree属性，它返回一个包含所有节点及其度（邻居数量）的迭代器，使用它求和的性能略逊于直接遍历adj.values()，但仍优于g[i]或neighbors(i)：

fun = f'sum(d for _, d in g.degree())'
t = 1000 * np.array(ti.repeat(stmt=fun, setup='', globals=globals(), number=1, repeat=100))
print(f'{fun}:  {np.amin(t):6.3f}ms  {np.median(t):6.3f}ms ')

测试结果大致为：

sum(d for _, d in g.degree()):   0.695ms   0.701ms 

性能分析 #

• g.adj是NetworkX图底层的邻接字典，直接访问它的values或items可以跳过上层封装的调用开销，这是性能最优的根源。
• g.degree()虽然是封装后的接口，但内部直接调用了邻接结构的信息，性能仍优于需要生成邻居迭代器的g.neighbors(i)或g[i]（后者会额外生成一个NodeView对象）。

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