Bipartite#

这个模块提供了用于二分图的函数和操作。二分图 B = (U, V, E) 有两个节点集合 U,V 和仅连接不同集合中节点的边 E 。在文献中，通常使用空间比喻来指代这两个节点集合为顶部和底部节点。

二分图算法没有导入到 networkx 命名空间的顶层，所以使用它们的最简单方法是：

`python from networkx.algorithms import bipartite `

NetworkX 没有自定义的二分图类，但可以使用 Graph() 或 DiGraph() 类来表示二分图。然而，你需要跟踪每个节点属于哪个集合，并确保同一集合中的节点之间没有边。NetworkX 的约定是使用名为 bipartite 的节点属性，其值为 0 或 1 来标识每个节点所属的集合。这个约定在二分图函数的源代码中没有强制执行，只是一个推荐。

例如：

`python B = nx.Graph() # 添加带有 "bipartite" 节点属性的节点 B.add_nodes_from([1, 2, 3, 4], bipartite=0) B.add_nodes_from(["a", "b", "c"], bipartite=1) # 仅在不同节点集合的节点之间添加边 B.add_edges_from([(1, "a"), (1, "b"), (2, "b"), (2, "c"), (3, "c"), (4, "a")]) `

NetworkX 的二分图模块中的许多算法需要，除了二分图 B 之外，还需要一个包含属于一个集合的所有节点的容器作为参数。二分图包中的函数不会检查节点集合是否实际上正确，也不会检查输入图是否实际上是二分图。如果 B 是连通的，你可以使用二分图算法找到两个节点集合：

`python nx.is_connected(B) True bottom_nodes, top_nodes = bipartite.sets(B) `

然而，如果输入图不连通，可能存在多个可能的着色方案。这就是为什么我们要求用户在大多数二分图函数中传递一个包含一个二分图节点集合的所有节点的容器作为参数。面对歧义，我们拒绝猜测的诱惑，并在输入图不连通时引发 AmbiguousSolution 异常。

使用 bipartite 节点属性，你可以轻松获取两个节点集合：

`python top_nodes = {n for n, d in B.nodes(data=True) if d["bipartite"] == 0} bottom_nodes = set(B) - top_nodes `

因此，你可以轻松使用需要一个包含一个节点集合的所有节点的容器的二分图算法：

`python print(round(bipartite.density(B, bottom_nodes), 2)) 0.5 G = bipartite.projected_graph(B, top_nodes) `

NetworkX 中的所有二分图生成器都使用 bipartite 节点属性构建二分图。因此，你可以使用相同的方法：

`python RB = bipartite.random_graph(5, 7, 0.2) RB_top = {n for n, d in RB.nodes(data=True) if d["bipartite"] == 0} RB_bottom = set(RB) - RB_top list(RB_top) [0, 1, 2, 3, 4] list(RB_bottom) [5, 6, 7, 8, 9, 10, 11] `

其他二分图生成器请参见 Generators 。

Basic functions#

二分图算法#

`is_bipartite`(G)	如果图 G 是二分图，则返回 True，否则返回 False。
`is_bipartite_node_set`(G, nodes)	返回 True 如果 nodes 和 G/nodes 是 G 的一个二分划分。
`sets`(G[, top_nodes])	返回图 G 的双边节点集。
`color`(G)	返回图的双色着色方案。
`density`(B, nodes)	返回二分图 B 的密度。
`degrees`(B, nodes[, weight])	返回二分图 B 中两个节点集的度数。

Edgelist#

二分图边列表#

读取和写入NetworkX图作为二分图边列表。

Format#

您可以使用这些函数读取或写入三种格式的边列表。

无数据的节点对:

1 2

作为数据的Python字典:

1 2 {'weight':7, 'color':'green'}

任意数据:

1 2 7 green

对于每条边 (u, v)，节点 u 被分配到部分 0，节点 v 被分配到部分 1。

`generate_edgelist`(G[, delimiter, data])	生成二分图 G 的单行边列表格式。
`write_edgelist`(G, path[, comments, ...])	将二分图写成边的列表。
`parse_edgelist`(lines[, comments, delimiter, ...])	解析二分图的边列表表示的行。
`read_edgelist`(path[, comments, delimiter, ...])	从边列表中读取二分图。

Matching#

提供计算二分图中的最大基数匹配和最小权重完全匹配的函数。

如果你不关心最大匹配算法的具体实现，只需使用 maximum_matching() 。如果你关心，可以直接导入一个命名的最大匹配算法。

例如，要在左边有两个顶点，右边有三个顶点的完全二分图中找到一个最大匹配：

>>> G = nx.complete_bipartite_graph(2, 3)
>>> left, right = nx.bipartite.sets(G)
>>> list(left)
[0, 1]
>>> list(right)
[2, 3, 4]
>>> nx.bipartite.maximum_matching(G)
{0: 2, 1: 3, 2: 0, 3: 1}

maximum_matching() 返回的字典包括了左右顶点集中的顶点映射。

同样地，minimum_weight_full_matching() 对于一个完全加权的二分图，生成一个匹配，其基数是两个分区中较小的一个的基数，并且匹配中包含的边的权重和最小。

`eppstein_matching`(G[, top_nodes])	返回二分图 `G` 的最大基数匹配。
`hopcroft_karp_matching`(G[, top_nodes])	返回二分图 `G` 的最大基数匹配。
`to_vertex_cover`(G, matching[, top_nodes])	返回与给定的二分图 `G` 的最大匹配相对应的最小顶点覆盖。
`maximum_matching`(G[, top_nodes])	Returns the maximum cardinality matching in the given bipartite graph.
`minimum_weight_full_matching`(G[, top_nodes, ...])	返回二分图 `G` 的最小权重完全匹配。

Matrix#

双邻接矩阵#

`biadjacency_matrix`(G, row_order[, ...])	返回二分图 G 的双邻接矩阵。
`from_biadjacency_matrix`(A[, create_using, ...])	从给定的SciPy稀疏数组表示的二分邻接矩阵创建一个新的二分图。

Projections#

二部图的一模（单部）投影。

`projected_graph`(B, nodes[, multigraph])	返回B在其一个节点集上的投影。
`weighted_projected_graph`(B, nodes[, ratio])	返回B的一个节点集上的加权投影。
`collaboration_weighted_projected_graph`(B, nodes)	Newman的加权投影，将B投影到其一个节点集上。
`overlap_weighted_projected_graph`(B, nodes[, ...])	重叠加权投影：将B投影到其节点集之一上。
`generic_weighted_projected_graph`(B, nodes[, ...])	用户指定权重函数的B的加权投影。

Spectral#

光谱二分性度量。

spectral_bipartivity(G[, nodes, weight])

返回谱二分性。

Clustering#

用于计算成对聚类的函数

`clustering`(G[, nodes, mode])	计算节点的二分聚类系数。
`average_clustering`(G[, nodes, mode])	计算平均二分图聚类系数。
`latapy_clustering`(G[, nodes, mode])	计算节点的二分聚类系数。
`robins_alexander_clustering`(G)	计算图 G 的双边聚类。

Redundancy#

二分图的节点冗余。

node_redundancy(G[, nodes])

计算二分图 G 中节点的冗余系数。

Centrality#

`closeness_centrality`(G, nodes[, normalized])	计算二分网络中节点的接近中心性。
`degree_centrality`(G, nodes)	计算二分网络中节点的度中心性。
`betweenness_centrality`(G, nodes)	计算二分网络中节点的介数中心性。

Generators#

二分图的生成器和函数。

`complete_bipartite_graph`(n1, n2[, create_using])	返回完整的二分图 `K_{n_1,n_2}` 。
`configuration_model`(aseq, bseq[, ...])	返回一个从给定度序列生成的随机二分图。
`havel_hakimi_graph`(aseq, bseq[, create_using])	返回一个由给定的两个度序列使用Havel-Hakimi风格构造的二分图。
`reverse_havel_hakimi_graph`(aseq, bseq[, ...])	返回一个由给定的两个度序列使用Havel-Hakimi风格的构造方法生成的二分图。
`alternating_havel_hakimi_graph`(aseq, bseq[, ...])	返回一个由给定的两个度序列使用交替Havel-Hakimi风格构造的二分图。
`preferential_attachment_graph`(aseq, p[, ...])	创建一个二分图，使用给定单一度序列的优先连接模型。
`random_graph`(n, m, p[, seed, directed])	返回一个二分随机图。
`gnmk_random_graph`(n, m, k[, seed, directed])	返回一个随机二分图 G_{n,m,k}。

Covering#

与图覆盖相关的函数。

min_edge_cover(G[, matching_algorithm])

返回构成图的最小边覆盖的一组边。

Extendability#

提供了一个函数，用于计算一个无向、简单、连通且为二分图的图的扩展性，该图至少包含一个完美匹配。

maximal_extendability(G)

计算图的扩展性。