二分体#

该模块为二部图提供函数和操作。二部图 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)

但是，如果输入图没有连接，则可能有多个颜色。这就是为什么我们要求用户将一个包含一个二部分节点集的所有节点的容器作为参数传递给大多数二部分函数的原因。面对歧义，我们拒绝了猜测和提出 AmbiguousSolution 如果的输入图 bipartite.sets 已断开连接。

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

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

网络中的所有二部图生成器都使用 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]

有关其他二部图生成器，请参见 Generators .

基本功能#

is_bipartite(G)

如果图G是二部的，则返回true，否则返回false。

is_bipartite_node_set(G, nodes)

如果节点和g/节点是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的加权投影到它的一个节点集上。

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

返回一组边，这些边构成了图形的最小边覆盖。