如何使用NetworkX计算图的二阶度数？

NetworkX没有专门计算二阶度数（与顶点距离恰好为2的顶点数量）的内置函数，但可以通过现有工具快速实现，以下是两种可行方案：

方案1：基于最短路径长度统计（通用型） #

适用于无向图、有向图或带权图，通过计算顶点到所有其他节点的最短路径长度，筛选出长度为2的节点数量：

import networkx as nx

# 构建示例图（可替换为你的图数据）
G = nx.Graph()
G.add_edges_from([(1,2), (2,3), (3,4), (2,4), (1,5)])

def calculate_second_order_degree(G, target_node):
    # 获取目标节点到所有节点的最短路径长度
    path_lengths = nx.shortest_path_length(G, source=target_node)
    # 统计路径长度恰好为2的节点数量
    return sum(1 for node, length in path_lengths.items() if length == 2)

# 计算顶点1的二阶度数
print(calculate_second_order_degree(G, 1))  # 输出：2（对应顶点3、4）

方案2：基于邻接集合运算（无向无权图优化版） #

对于无向无权图，可通过“邻居的邻居”集合减去自身和直接邻居，得到距离为2的节点，效率比方案1更高：

def calculate_second_order_degree_optimized(G, target_node):
    direct_neighbors = set(G.neighbors(target_node))
    # 收集所有直接邻居的邻居
    neighbor_of_neighbors = set()
    for neighbor in direct_neighbors:
        neighbor_of_neighbors.update(G.neighbors(neighbor))
    # 排除自身和直接邻居，剩余即为距离为2的节点
    second_order_nodes = neighbor_of_neighbors - direct_neighbors - {target_node}
    return len(second_order_nodes)

# 验证结果一致性
print(calculate_second_order_degree_optimized(G, 1))  # 输出：2

注意事项 #

• 若处理有向图，需调整方案：方案1自动适配方向；方案2需根据需求使用G.successors()（出邻居）或G.predecessors()（入邻居）替代G.neighbors()。
• 大型图优先选择方案2，避免全图最短路径计算的性能开销。

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