Networkx

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

import networkx as nx

建图

• 无向图

  G=nx.Graph()

• 有向图

  D=nx.DiGraph()

• 可重复边的

  M=nx.MultiGraph()

属性

• 图的节点

  list(G.nodes())

• 图的边

  list(G.edges())

• 节点的相邻节点

  [n for n in G.neighbors(node)]

添加边和节点

• 添加节点

  G.add_node('Alice')

• 添加边

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

• 通过字典添加节点

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

• 通过字典添加边

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

绘图功能

• 将节点排列成一个圆圈，并将他们与边连接起来

  nx.draw_circular(G, node_color='b', node_size=2000, with_labels=True)

• 以位置字典作为第二个参数排列绘图

  nx.draw(G, positions, node_shape='s', node_size=2500, with_labels=True)

• 给边添加标签

  nx.draw_networkx_edge_labels(G, positions, edge_labels=drive_times)

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

生成图

• 随机图
  当图的节点联通率为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)