IT技术社区_专业开发者平台_最新编程教程与解决方案 -沐辰社区

Python案例如何用Networkx做图的离心率

wen python案例 1

本文目录导读：

Python案例如何用Networkx做图的离心率

  1. 离心率的基本概念
  2. 基础示例
  3. 计算特定节点的离心率
  4. 图论中的相关概念
  5. 复杂图示例
  6. 实际应用案例：社交网络分析
  7. 处理特殊图
  8. 性能优化示例
  9. 关键知识点总结

我来详细讲解如何使用NetworkX计算图的离心率。

离心率的基本概念

离心率（Eccentricity）：对于图中任意节点v,其离心率定义为该节点到图中所有其他节点的最短路径距离的最大值。

ecc(v) = max{dist(v, u) | u ∈ V, u ≠ v}

基础示例

import networkx as nx
import matplotlib.pyplot as plt
# 创建一个简单的图
G = nx.Graph()
# 添加节点和边
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (2, 5)]
G.add_edges_from(edges)
# 计算所有节点的离心率
eccentricity = nx.eccentricity(G)
print("各节点的离心率:")
for node, ecc in eccentricity.items():
    print(f"节点 {node}: {ecc}")
# 可视化图
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', 
        node_size=500, font_size=16, font_weight='bold')
# 在节点上标注离心率
labels = {node: f'{node}\n(ecc={ecc})' for node, ecc in eccentricity.items()}
nx.draw_networkx_labels(G, pos, labels=labels, font_size=12)
"图及其节点离心率")
plt.show()

计算特定节点的离心率

# 计算单个节点的离心率
node_ecc = nx.eccentricity(G, v=1)
print(f"节点1的离心率: {node_ecc}")
# 计算多个节点的离心率
nodes_list = [1, 3, 5]
selective_ecc = nx.eccentricity(G, v=nodes_list)
print(f"选定节点的离心率: {selective_ecc}")

图论中的相关概念

离心率可以推导出其他重要指标：

# 图的半径（所有离心率的最小值）
radius = nx.radius(G)
print(f"图的半径: {radius}")
# 图的直径（所有离心率的最大值）
diameter = nx.diameter(G)
print(f"图的直径: {diameter}")
# 中心节点（离心率等于半径的节点）
center = nx.center(G)
print(f"中心节点: {center}")
# 边缘节点（离心率等于直径的节点）
periphery = nx.periphery(G)
print(f"边缘节点: {periphery}")

复杂图示例

import numpy as np
# 创建不同类型的图进行分析
def analyze_graph_eccentricity(G, title):
    print(f"\n=== {title} ===")
    print(f"节点数: {G.number_of_nodes()}")
    print(f"边数: {G.number_of_edges()}")
    # 计算离心率
    ecc_dict = nx.eccentricity(G)
    # 统计信息
    ecc_values = list(ecc_dict.values())
    print(f"离心率范围: {min(ecc_values)} - {max(ecc_values)}")
    print(f"平均离心率: {np.mean(ecc_values):.2f}")
    print(f"半径: {nx.radius(G)}")
    print(f"直径: {nx.diameter(G)}")
    print(f"中心节点: {nx.center(G)}")
    # 找出离心率极值节点
    max_ecc = max(ecc_values)
    min_ecc = min(ecc_values)
    max_nodes = [n for n, e in ecc_dict.items() if e == max_ecc]
    min_nodes = [n for n, e in ecc_dict.items() if e == min_ecc]
    print(f"最大离心率节点({max_ecc}): {max_nodes}")
    print(f"最小离心率节点({min_ecc}): {min_nodes}")
    # 可视化
    plt.figure(figsize=(8, 6))
    pos = nx.spring_layout(G)
    # 根据离心率大小着色
    node_colors = [ecc_dict[n] for n in G.nodes()]
    nx.draw(G, pos, with_labels=True, 
            node_color=node_colors, 
            cmap=plt.cm.RdYlBu_r,
            node_size=500, 
            font_size=10,
            edge_color='gray')
    plt.title(f"离心率分布 - {title}")
    plt.colorbar(plt.cm.ScalarMappable(cmap=plt.cm.RdYlBu_r), 
                 label='离心率')
    plt.show()
# 创建几种不同结构的图
# 1. 路径图
path_graph = nx.path_graph(6)
analyze_graph_eccentricity(path_graph, "路径图")
# 2. 环形图
cycle_graph = nx.cycle_graph(8)
analyze_graph_eccentricity(cycle_graph, "环形图")
# 3. 星形图
star_graph = nx.star_graph(5)
analyze_graph_eccentricity(star_graph, "星形图")
# 4. 完全图
complete_graph = nx.complete_graph(5)
analyze_graph_eccentricity(complete_graph, "完全图")

实际应用案例：社交网络分析

# 模拟一个社交网络
def social_network_analysis():
    # 创建社交网络图
    social_graph = nx.Graph()
    # 添加人物关系和互动
    friendships = [
        ('Alice', 'Bob'), ('Alice', 'Charlie'), ('Alice', 'David'),
        ('Bob', 'Charlie'), ('Bob', 'Eve'), ('Charlie', 'Frank'),
        ('David', 'Eve'), ('Eve', 'Frank'), ('Frank', 'Grace'),
        ('Grace', 'Henry'), ('Henry', 'Ivy'), ('Ivy', 'Jack'),
        ('Jack', 'Karen'), ('Karen', 'Leo'), ('Leo', 'Mary'),
        ('Bob', 'Grace'), ('Charlie', 'Henry'), ('David', 'Ivy'),
        ('Eve', 'Jack'), ('Frank', 'Karen')
    ]
    social_graph.add_edges_from(friendships)
    # 计算离心率
    ecc = nx.eccentricity(social_graph)
    print("社交网络分析结果:")
    print("=" * 50)
    print(f"好友数: {social_graph.number_of_nodes()}")
    print(f"关系数: {social_graph.number_of_edges()}")
    print(f"网络半径: {nx.radius(social_graph)}")
    print(f"网络直径: {nx.diameter(social_graph)}")
    print("\n各成员的离心率 (越小表示社交位置越中心):")
    sorted_ecc = sorted(ecc.items(), key=lambda x: x[1])
    for name, ecc_value in sorted_ecc:
        position = "中心人物" if ecc_value == min(ecc.values()) else "边缘人物" if ecc_value == max(ecc.values()) else ""
        print(f"{name}: {ecc_value} {position}")
    # 可视化社交网络
    plt.figure(figsize=(12, 8))
    pos = nx.spring_layout(social_graph, k=1, iterations=50)
    # 根据离心率调整节点大小和颜色
    node_sizes = [2000 / (ecc[n] + 1) * 2 for n in social_graph.nodes()]
    node_colors = [ecc[n] for n in social_graph.nodes()]
    nx.draw(social_graph, pos, 
            node_color=node_colors, 
            cmap=plt.cm.viridis,
            node_size=node_sizes, 
            with_labels=True, 
            font_size=10,
            font_weight='bold',
            edge_color='gray',
            alpha=0.7)
    plt.title("社交网络离心率分析\n(节点大小代表中心程度，颜色代表位置)")
    plt.colorbar(plt.cm.ScalarMappable(cmap=plt.cm.viridis), 
                 label='离心率')
    plt.show()
    return ecc
# 运行社交网络分析
social_ecc = social_network_analysis()

处理特殊图

# 处理有向图
def directed_graph_example():
    # 创建有向图
    DG = nx.DiGraph()
    DG.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1)])
    # 有向图的离心率（需要考虑方向）
    try:
        d_ecc = nx.eccentricity(DG)
        print("有向图离心率:", d_ecc)
    except nx.NetworkXError as e:
        print(f"无法计算有向图离心率: {e}")
        print("有向图需要强连通才能计算离心率")
    # 确保图是强连通的
    if nx.is_strongly_connected(DG):
        d_ecc = nx.eccentricity(DG)
        print("强连通有向图离心率:", d_ecc)
# 处理不连通图
def disconnected_graph_example():
    # 创建不连通图
    G1 = nx.path_graph(3)
    G2 = nx.path_graph(4)
    G = nx.disjoint_union(G1, G2)
    print(f"图是否连通: {nx.is_connected(G)}")
    # 对每个连通分量分别计算
    print("\n各连通分量离心率:")
    for i, component in enumerate(nx.connected_components(G)):
        subgraph = G.subgraph(component)
        ecc = nx.eccentricity(subgraph)
        print(f"分量 {i+1}: {ecc}")

性能优化示例

import time
def performance_comparison():
    # 创建大规模图
    sizes = [100, 200, 500]
    for size in sizes:
        # 生成随机图
        G = nx.erdos_renyi_graph(size, 0.1)
        # 确保图连通
        if not nx.is_connected(G):
            continue
        start_time = time.time()
        ecc = nx.eccentricity(G)
        end_time = time.time()
        print(f"节点数 {size}: 计算时间 {end_time - start_time:.4f} 秒")
        # 计算单个节点离心率（更快）
        start_time = time.time()
        single_ecc = nx.eccentricity(G, v=0)
        end_time = time.time()
        print(f"单节点计算: {end_time - start_time:.4f} 秒")
# 运行性能测试
performance_comparison()

关键知识点总结

  1. 离心率计算：nx.eccentricity(G) 计算所有节点，nx.eccentricity(G, v=node) 计算特定节点

  2. 图的要求：

    • 无向图需要连通
    • 有向图需要强连通
    • 不连通图需分别处理各分量

  3. 相关指标：

    • 半径：最小离心率
    • 直径：最大离心率
    • 中心节点：半径对应的节点
    • 边缘节点：直径对应的节点

  4. 应用场景：

    • 社交网络分析 (找出影响力最大的人)
    • 网络拓扑分析 (发现网络瓶颈)
    • 路由优化 (选择中心节点作为中转站)

这些示例涵盖了NetworkX中离心率计算的主要用法和实际应用场景。

上一篇Python案例如何用Networkx做图的色数

下一篇Python案例如何用Networkx做图的直径

相关文章

抱歉，评论功能暂时关闭!