Skip to content

Networkx

Jump to bottom
Starslayerx edited this page Apr 20, 2021 · 40 revisions

green-pi
networkx
使用 NetworkX，您可以以标准和非标准数据格式加载和存储网络，生成多种类型的随机和经典网络，分析网络结构，构建网络模型，设计新的网络算法，绘制网络等等。

import networkx as nx

图论矩阵

  • 关联矩阵
    表示了每个节点和每条边之间的关系
    associated

  • 邻接矩阵
    邻接矩阵表示了两个节点之间的关系
    neighbor

  • 导出矩阵

    nx.to_numpy_matrix(G) # 导出为numpy矩阵
nx.to_scipy_sparse_matrix(G) # 导出为稀疏矩阵

建图

  • 无向图

    G = nx.Graph()
G = nx.Graph(A) # 使用邻接矩阵A创建图G

  • 有向图

    D = nx.DiGraph()
D = nx.DiGraph(A) # 使用邻接矩阵A创建图D

  • 可重复边的的无向图

    M = nx.MultiGraph()

  • 可重复边的有向图

    M = MultiDigraph()

  • 创建完全图

    nx.complete_graph(n, create_using=None)

    n: 如果n为一个数，节点为0~(n-1)，或者使用元祖指定节点
    create_using: 图的类型，例如无向图和有向图

  • 添加边

    G.add_edge('Alice', 'Bob')

  • 通过字典或列表，添加多条边

    drive_times  = {('Albany', 'Boston'): 3,
                ('Albany', 'NYC'): 4,
                ('Boston', 'NYC'): 4,
                ('NYC', 'Philly'): 2}
G.add_edges_from(drive_times)

  • 添加节点

    G.add_node('Alice')

  • 通过字典或列表，添加多个节点

    positions = dict(Albang = (-74, 43),
                 Boston = (-71, 42),
                 NYC = (-74, 41),
                 Philly = (-75, 40))
G = nx.Graph()
G.add_nodes_from(positions)

图

  • 图的节点

    list(G.nodes())

  • 图的边

    list(G.edges())

  • 边的权值

    nx.get_edge_attributes(G, name)

    name: 边属性的名字，例如'weight'权重，'color'颜色

节点

  • 节点度数

    nx.degree(G, nbunch=None, weight=None)

    返回{节点:度数}字典

  • 图中的所有节点

    nx.nodes(G)

    使用方法: list(nx.nodes(G))

  • 节点数量

    nx.number_of_nodes(G)

  • 相邻节点

    nx.neighbors(G, n)

    使用方法: list(nx.neighbors(G, 2)) 或 [n for n in G.neighbors(node)]

  • 不相邻节点

    nx.non_neighbors(graph, node)

  • 两个节点相同的节点

    nx.common_neighbors(G, u, v)

    返回 list(nx.common_neighbors(G, 1, 3))

  • 节点度数频度视图

    nx.degree_histogram(G)

    返回从0开始到最大度数列表

边

  • 边的视图

    nx.edges(G, nbunch=None)

    返回对应的边的列表，用两个节点表示一条边 [(node_i, node_j)]

  • 边的数量

    nx.number_of_edges(G)

  • 图的密度

    nx.density(G)

    density

绘图

这里是官网绘图文档

  • 基础绘图

    nx.draw(G, pos=None, ax=None, **kwds)
    • pos: key为node,value为元祖坐标的字典 或 预定的布局
    • ax: 可在某个轴上绘制该图(matplotlib) 还可以使用with_labels等参数

  • 详细绘图

    nx.draw_networkx(G, pos=None, arrows=True, with_labels=True, **kwds)

    arrows: 对于有向图是否画箭头 arrowstyle: 箭头样式，默认’-|>’.详见matplotlib.patches.ArrowStyle
    arrowsize: 箭头大小，默认10.
    with_labels: 是否显示节点标签
    ax: 在matplotlib的某个axes对象上绘图
    nodelist: 只画出指定的几个节点
    edgelist: 只画出指定的几条边
    node_size: 节点大小，默认300
    node_color: 节点颜色，默认’#1f78b4’
    node_shape: 节点形状，默认'o'，可选'so^>v<dph8’
    alpha: 节点透明度
    cmap: Matplotlib colormap, optional (default=None)
    edge_color: 边的颜色
    style: 边的样式，默认’solid’,可选(solid|dashed|dotted,dashdot)
    font_size: 标签字体大小
    font_color: 字体颜色
    font_weight: 字体宽度
    font_family: 字体样式
    label: 图例标签

  • 只绘制节点

    nx.draw_networkx_nodes(G, pos, nodelist=None, node_size=300, node_color='#1f78b4', node_shape='o', alpha=None, cmap=None, vmin=None, vmax=None, ax=None, linewidths=None, edgecolors=None, label=None)

    返回值：matplotlib.collections.PathCollection类型的节点

  • 只绘制边

    draw_networkx_edges(G, pos, edgelist=None, width=1.0, edge_color='k', style='solid', alpha=None, arrowstyle='-|>', arrowsize=10, edge_cmap=None, edge_vmin=None, edge_vmax=None, ax=None, arrows=True, label=None, node_size=300, nodelist=None, node_shape='o', connectionstyle=None, min_source_margin=0, min_target_margin=0)

    返回值：matplotlib.collection.LineCollection类型的边

  • 绘制节点标签

    draw_networkx_labels(G, pos, labels=None, font_size=12, font_color='k', font_family='sans-serif', font_weight='normal', alpha=None, bbox=None, horizontalalignment='center', verticalalignment='center', ax=None)

    返回字典类型

  • 绘制边标签

    draw_networkx_edge_labels(G, pos, edge_labels=None, label_pos=0.5, font_size=10, font_color='k', font_family='sans-serif', font_weight='normal', alpha=None, bbox=None, horizontalalignment='center', verticalalignment='center', ax=None, rotate=True)
    • edge_labels: 可以使其等于nx.get_edge_attributes(G, 'weight')将边权重作为标签信息绘制 或者可以使用字典 返回字典类型

  • 下面几种绘图方式是直接使用某种类型绘图

    # 节点在圆环均匀分布绘图
nx.draw_circular(G, node_color='b', node_size=2000, with_labels=True)

# Draw the graph G with a Kamada-Kawai force-directed layout.
draw_kamada_kawai(G, **kwargs)

# Draw a planar networkx graph with planar layout.
draw_planar(G, **kwargs)

# Draw the graph G with a random layout.
draw_random(G, **kwargs)

# Draw the graph G with a spectral 2D layout.
draw_spectral(G, **kwargs)

# Draw the graph G with a spring layout.
draw_spring(G, **kwargs)

# Draw networkx graph with shell layout.
draw_shell(G, **kwargs)

  • 绘图布局
    绘图函数有pos参数，可以使用字典自行规定每个节点的坐标，或者使用预制的layout

    • circular_layout: 顶点在圆环上均匀分布
    • random_layout: 顶点随机分布
    • shell_layout: 顶点在同心圆上分布
    • spring_layout: 用Fruchterman-Reingold算法排列顶点
    • spectral_layout: 根据图的Laplace特征向量排列顶点

图的概念

连通图

  • 随机图
    当图的节点联通率为p > p*=(ln n)/n时，图很有可能为连通的，在p*位置，图的连通率会发生突变

  • 构造完全图(每两个节点之间相互相连)

    def all_pairs(nodes):
  for i, u in enumerate(nodes):
      for j, v in enumerate(nodes):
          if i>j:
              yield u,v
              
def make_complete_graph(n):
  G = nx.Graph()
  nodes = range(n)
  G.add_nodes_from(nodes)
  G.add_edges_from(all_pairs(nodes))
  return G

  • 连通图(每两个节点都有路径相连)
    该函数接受一个图和一个起始节点start，从起始节点开始，返回可以到达的节点集

    def reachable_nodes(G, start):
  seen = set()
  stack = [start]
  while stack:
      node = stack.pop()
      if node not in seen:
          seen.add(node)
          stack.extend(G.neighbors(node))
  return seen

    该函数判断图G是否连通

    def is_connected(G):
  start = next(iter(G))
  reachable = reachable_nodes(G, start)
  return len(reachable) == len(G)

ER图

ER图有两个特点，n为节点数目，p为两个节点间存在一条边的概率

  • 下面的生成器枚举了所有的边，并选择哪些便应该添加到图中

     def flip(p):
     return np.random.random() < p; # 返回0-1随机分布数字

 def random_pairs(nodes, p):
     for edge in all_pairs(nodes):
         if flip(p):
             yield edge

  • 生成并返回ER图

    def make_random_graph(n, p):
    G = nx.Graph()
    nodes = range(n)
    G.add_nodes_from(nodes)
    G.add_edges_from(random_pairs(nodes, p))
    return G

  • 多次跌代计算图的连通率

    def prob_connected(n, p, iters=100):
    tf = [is_connected(make_random_graph(n, p))
          for i in range(iters)]
    return np.mean(tf)

算法

最短路径

  1. 求两个节点之间的最短路径
nx.shortest_path(G, source=None, target=None, weight=None, method='dijkstra')
  • weight: (weight/distance/cost)
  • method: 采用算法(‘dijkstra’, ‘bellman-ford’)

返回值：最短路径节点组成的列表或字典

  • 如果只传入source开始节点，返回由目标节点为key的最短路径集合(只传入target目标节点同理)
  • 如果两个节点都没传入，则返回一个嵌套字典{开始节点:{结束节点:[路径]}}
  1. 求两个节点之间的全部最短路径
nx.all_shortest_paths(G, source, target, weight=None, method='dijkstra')

返回值：返回一个含有所有最短路径的生成器

  • 使用方法: print( p for p in nx.all_shortest_paths(G, source, target, weight=None, method='dijkstra') )
  1. 计算最短路径长度
 nx.shortest_path_length(G, source=None, target=None, weight=None, method='dijkstra')

返回值：

  • 若只指定了source和target中的一个，则返回字典类型(同上)
  • 若两个值都未指定，则返回一个迭代器(source, dictionary)
  • 使用方法: p = dict( nx.shortest_path_length(G, source=None, target=None, weight='weight', method='dijkstra') )
  1. 平均最短路径长度
nx.average_shortest_path_length(G, weight=None, method=None)

average_shortest_path

  1. 判断两节点之间是否存在通路
nx.has_path(G, source, target)

返回布尔值

数学模型

差值和拟合

微分方程模型

数学规划模型

图论

Scipy

Numpy

Networkx

Pandas

Matplotlb

Sympy

Clone this wiki locally