二分图#

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

二分图算法并未在顶层导入 networkx 命名空间，因此最简单的使用方法是：

>>> from networkx.algorithms import bipartite

NetworkX 没有自定义的二分图类，但可以使用 Graph() 或 DiGraph() 类来表示二分图。但是，您必须记录每个节点属于哪个集合，并确保同一集合内的节点之间没有边。NetworkX 中使用的约定是使用名为 bipartite 的节点属性，其值为 0 或 1，以标识每个节点所属的集合。此约定在二分图函数的源代码中并未强制执行，仅作为一项建议。

例如

>>> B = nx.Graph()
>>> # Add nodes with the node attribute "bipartite"
>>> B.add_nodes_from([1, 2, 3, 4], bipartite=0)
>>> B.add_nodes_from(["a", "b", "c"], bipartite=1)
>>> # Add edges only between nodes of opposite node sets
>>> B.add_edges_from([(1, "a"), (1, "b"), (2, "b"), (2, "c"), (3, "c"), (4, "a")])

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

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

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

使用 bipartite 节点属性，您可以轻松获取这两个节点集

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

因此您可以轻松使用需要一个包含属于某个节点集的所有节点的容器作为参数的二分图算法

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

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

>>> 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]

有关其他二分图生成器，请参阅 生成器。

基本函数#

is_bipartite(G)

如果图 G 是二分图，则返回 True；否则返回 False。

is_bipartite_node_set(G, nodes)

如果 nodes 和 G/nodes 是图 G 的一个二部划分，则返回 True。

sets(G[, top_nodes])

返回图 G 的二分节点集。

color(G)

返回图的一个二着色。

density(B, nodes)

返回二分图 B 的密度。

degrees(B, nodes[, weight])

返回二分图 B 中两个节点集的度。

边列表#

以二分边列表形式读取和写入 NetworkX 图。

格式#

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

无数据的节点对

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, ...])

从边列表中读取二分图。

匹配#

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

如果您不关心最大匹配算法的具体实现，只需使用 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])

返回给定二分图中的最大基数匹配。

minimum_weight_full_matching(G[, top_nodes, ...])

返回二分图 G 的最小权重完全匹配。

矩阵#

biadjacency_matrix(G, row_order[, ...])

返回二分图 G 的二分邻接矩阵。

from_biadjacency_matrix(A[, create_using, ...])

从 SciPy 稀疏数组表示的二分邻接矩阵创建新的二分图。

投影#

二分图的单模（非二分）投影。

projected_graph(B, nodes[, multigraph])

返回 B 在其一个节点集上的投影。

weighted_projected_graph(B, nodes[, ratio])

返回 B 在其一个节点集上的加权投影。

collaboration_weighted_projected_graph(B, nodes)

B 在其一个节点集上的 Newman 加权投影。

overlap_weighted_projected_graph(B, nodes[, ...])

B 在其一个节点集上的重叠加权投影。

generic_weighted_projected_graph(B, nodes[, ...])

使用用户指定的权重函数计算 B 的加权投影。

谱属性#

谱二部性度量。

spectral_bipartivity(G[, nodes, weight])

返回谱二部性。

聚类#

计算对聚类的函数

clustering(G[, nodes, mode])

计算节点的二分聚类系数。

average_clustering(G[, nodes, mode])

计算平均二分聚类系数。

latapy_clustering(G[, nodes, mode])

计算节点的二分聚类系数。

robins_alexander_clustering(G)

计算 G 的二分聚类。

冗余#

二分图的节点冗余。

node_redundancy(G[, nodes])

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

中心性#

closeness_centrality(G, nodes[, normalized])

计算二分网络中节点的紧密度中心性。

degree_centrality(G, nodes)

计算二分网络中节点的度中心性。

betweenness_centrality(G, nodes)

计算二分网络中节点的中介中心性。

生成器#

二分图的生成器和函数。

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}。

覆盖#

与图覆盖相关的函数。

min_edge_cover(G[, matching_algorithm])

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

可扩性#

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

maximal_extendability(G)

计算图的可扩性。
在此页面上