Graph generators#

Atlas#

小型图集生成器。

graph_atlas(i)

返回图集中的第 i 个图。

graph_atlas_g()

返回包含Graph Atlas中最多七个节点的所有图的列表。

Classic#

一些经典图的生成器。

典型的图构建函数调用如下：

>>> G = nx.complete_graph(100)

返回一个包含0到99节点的完全图，作为一个简单图。除了 empty_graph 之外，本模块中的所有函数都返回一个Graph类（即一个简单、无向图）。

balanced_tree(r, h[, create_using])

返回高度为 h 的完美平衡 r 叉树。

barbell_graph(m1, m2[, create_using])

返回杠铃图：两个完全图通过一条路径连接。

binomial_tree(n[, create_using])

返回阶数为 n 的二项树。

complete_graph(n[, create_using])

返回具有 n 个节点的完全图 K_n 。

complete_multipartite_graph(*subset_sizes)

返回具有指定子集大小的完整多部图。

circular_ladder_graph(n[, create_using])

返回长度为 n 的圆形梯形图 \(CL_n\)。

circulant_graph(n, offsets[, create_using])

返回具有 \(n\) 个节点的循环图 \(Ci_n(x_1, x_2, ..., x_m)\)。

cycle_graph(n[, create_using])

返回循环图 \(C_n\)，由循环连接的节点组成。

dorogovtsev_goltsev_mendes_graph(n[, ...])

返回层次化构造的Dorogovtsev--Goltsev--Mendes图。

empty_graph([n, create_using, default])

返回具有 n 个节点且无边的空图。

full_rary_tree(r, n[, create_using])

创建一个包含 n 个节点的完整 r-叉树。

kneser_graph(n, k)

返回具有参数 n 和 k 的 Kneser 图。

ladder_graph(n[, create_using])

返回长度为 n 的梯形图。

lollipop_graph(m, n[, create_using])

返回棒棒糖图； K_m 连接到 P_n 。

null_graph([create_using])

返回一个没有节点或边的空图。

path_graph(n[, create_using])

返回线性连接节点的路径图 P_n 。

star_graph(n[, create_using])

返回星形图

tadpole_graph(m, n[, create_using])

返回 (m,n)-蝌蚪图； C_m 连接到 P_n 。

trivial_graph([create_using])

返回一个仅有一个节点（标签为0）且没有边的平凡图。

turan_graph(n, r)

返回 Turan 图

wheel_graph(n[, create_using])

返回轮图

Expanders#

提供扩展图的显式构造方法。

margulis_gabber_galil_graph(n[, create_using])

返回在 n^2 个节点上的 Margulis-Gabber-Galil 无向多重图。

chordal_cycle_graph(p[, create_using])

返回具有 p 个节点的弦环图。

paley_graph(p[, create_using])

返回具有 \(p\) 个节点的 Paley \(\frac{(p-1)}{2}\) -正则图。

maybe_regular_expander(n, d, *[, ...])

创建随机规则扩展图的实用工具。

is_regular_expander(G, *[, epsilon])

确定图 G 是否为正则扩展图。[Rc4fb9a2e4990-1]

random_regular_expander_graph(n, d, *[, ...])

返回一个具有 \(n\) 个节点和度数 \(d\) 的随机正则扩展图。

Lattice#

生成网格图和格点的函数

grid_2d_graph() , triangular_lattice_graph() , 和 hexagonal_lattice_graph() 函数分别对应于平面的三种 正则铺砌 ，即正方形、三角形和六边形铺砌。grid_graph() 和 hypercube_graph() 则适用于任意维度。关于 三角形铺砌 和 正方形、六边形和三角形网格 的相关讨论也很有用。

grid_2d_graph(m, n[, periodic, create_using])

返回二维网格图。

grid_graph(dim[, periodic])

返回 n 维网格图。

hexagonal_lattice_graph(m, n[, periodic, ...])

返回一个 m 行 n 列的六边形网格图。

hypercube_graph(n)

返回 n 维超立方体图。

triangular_lattice_graph(m, n[, periodic, ...])

返回一个 \(m\) 行 \(n\) 列的三角形网格图。

Small#

各种小型和命名图，以及一些紧凑的生成器。

LCF_graph(n, shift_list, repeats[, create_using])

返回指定LCF表示法的立方图。

bull_graph([create_using])

返回牛图

chvatal_graph([create_using])

返回 Chvátal 图

cubical_graph([create_using])

返回3-正则的柏拉图立方体图

desargues_graph([create_using])

返回Desargues图

diamond_graph([create_using])

返回菱形图

dodecahedral_graph([create_using])

返回正十二面体图。

frucht_graph([create_using])

返回 Frucht 图。

heawood_graph([create_using])

返回Heawood图，一个(3,6)笼图。

hoffman_singleton_graph()

返回Hoffman-Singleton图。

house_graph([create_using])

返回房屋图（顶部带有三角形的正方形）

house_x_graph([create_using])

返回带有十字形内部的房屋图。

icosahedral_graph([create_using])

返回柏拉图式二十面体图。

krackhardt_kite_graph([create_using])

返回Krackhardt风筝社交网络。

moebius_kantor_graph([create_using])

返回莫比乌斯-康托尔图。

octahedral_graph([create_using])

返回正八面体图。

pappus_graph()

返回帕普斯图。

petersen_graph([create_using])

返回 Petersen 图。

sedgewick_maze_graph([create_using])

返回一个带有环的小迷宫。

tetrahedral_graph([create_using])

返回3-正则的柏拉图四面体图。

truncated_cube_graph([create_using])

返回截角立方体的骨架。

truncated_tetrahedron_graph([create_using])

返回截角四面体的骨架。

tutte_graph([create_using])

返回Tutte图。

Random Graphs#

随机图生成器。

fast_gnp_random_graph(n, p[, seed, directed])

返回一个 \(G_{n,p}\) 随机图，也称为 Erdős-Rényi 图或二项图。

gnp_random_graph(n, p[, seed, directed])

返回一个 \(G_{n,p}\) 随机图，也称为 Erdős-Rényi 图或二项图。

dense_gnm_random_graph(n, m[, seed])

返回一个 \(G_{n,m}\) 随机图。

gnm_random_graph(n, m[, seed, directed])

返回一个 \(G_{n,m}\) 随机图。

erdos_renyi_graph(n, p[, seed, directed])

返回一个 \(G_{n,p}\) 随机图，也称为 Erdős-Rényi 图或二项图。

binomial_graph(n, p[, seed, directed])

返回一个 \(G_{n,p}\) 随机图，也称为 Erdős-Rényi 图或二项图。

newman_watts_strogatz_graph(n, k, p[, seed])

返回一个Newman–Watts–Strogatz小世界图。

watts_strogatz_graph(n, k, p[, seed])

返回一个 Watts–Strogatz 小世界图。

connected_watts_strogatz_graph(n, k, p[, ...])

返回一个连接的Watts-Strogatz小世界图。

random_regular_graph(d, n[, seed])

返回一个包含 \(n\) 个节点的随机 \(d\)-正则图。

barabasi_albert_graph(n, m[, seed, ...])

返回一个使用Barabási–Albert优先连接的随机图

dual_barabasi_albert_graph(n, m1, m2, p[, ...])

返回一个使用双Barabási–Albert优先连接的随机图

extended_barabasi_albert_graph(n, m, p, q[, ...])

返回一个扩展的Barabási–Albert模型图。

powerlaw_cluster_graph(n, m, p[, seed])

Holme和Kim算法用于生成具有幂律度分布和近似平均聚类系数的增长图。

random_kernel_graph(n, kernel_integral[, ...])

返回一个基于指定核的随机图。

random_lobster(n, p1, p2[, seed])

返回一个随机的龙虾图。

random_shell_graph(constructor[, seed])

返回一个给定构造函数的随机壳层图。

random_powerlaw_tree(n[, gamma, seed, tries])

返回一个具有幂律度分布的树。

random_powerlaw_tree_sequence(n[, gamma, ...])

返回一个具有幂律分布的树的度序列。

random_kernel_graph(n, kernel_integral[, ...])

返回一个基于指定核的随机图。

Duplication Divergence#

基于“复制”方法生成图形的函数。

这些图生成器从一个小的初始图开始，然后复制节点并（部分）复制它们的边。这些函数通常受到生物网络的启发。

duplication_divergence_graph(n, p[, seed])

返回一个使用重复-分歧模型的无向图。

partial_duplication_graph(N, n, p, q[, seed])

返回一个使用部分复制模型生成的随机图。

Degree Sequence#

生成具有给定度序列或期望度序列的图。

configuration_model(deg_sequence[, ...])

返回一个具有给定度序列的随机图。

directed_configuration_model(...[, ...])

返回一个具有给定度序列的有向随机图。

expected_degree_graph(w[, seed, selfloops])

返回一个具有给定期望度的随机图。

havel_hakimi_graph(deg_sequence[, create_using])

返回一个使用Havel-Hakimi算法构造的具有给定度序列的简单图。

directed_havel_hakimi_graph(in_deg_sequence, ...)

返回一个具有给定度序列的有向图。

degree_sequence_tree(deg_sequence[, ...])

为给定的度序列构建一棵树。

random_degree_sequence_graph(sequence[, ...])

返回一个具有给定度序列的简单随机图。

Random Clustered#

生成具有给定度和三角形序列的图。

random_clustered_graph(joint_degree_sequence)

生成一个具有给定联合独立边度和三角形度序列的随机图。

Directed#

生成一些有向图的生成器，包括增长网络（GN）图和无标度图。

gn_graph(n[, kernel, create_using, seed])

返回具有 n 个节点的增长网络（GN）有向图。

gnr_graph(n, p[, create_using, seed])

返回具有重定向的生成网络（GNR）有向图，包含 n 个节点和重定向概率 p 。

gnc_graph(n[, create_using, seed])

返回具有复制机制的递增网络（GNC）有向图，包含 n 个节点。

random_k_out_graph(n, k, alpha[, ...])

返回一个具有优先连接的随机 k -out 图。

scale_free_graph(n[, alpha, beta, gamma, ...])

返回一个无标度有向图。

Geometric#

几何图生成器。

geometric_edges(G, radius[, p, pos_name])

返回节点对列表，这些节点对之间的距离在 radius 范围内。

geographical_threshold_graph(n, theta[, ...])

返回一个地理阈值图。

navigable_small_world_graph(n[, p, q, r, ...])

返回一个可导航的小世界图。

random_geometric_graph(n, radius[, dim, ...])

返回一个在单位立方体中具有 dim 维度的随机几何图。

soft_random_geometric_graph(n, radius[, ...])

返回单位立方体中的软随机几何图。

thresholded_random_geometric_graph(n, ...[, ...])

返回一个单位立方体中的阈值随机几何图。

waxman_graph(n[, beta, alpha, L, domain, ...])

返回一个 Waxman 随机图。

geometric_soft_configuration_graph(*, beta)

返回一个从几何软配置模型中随机生成的图。

Line Graph#

生成折线图的函数。

line_graph(G[, create_using])

返回图或有向图 G 的线图。

inverse_line_graph(G)

返回图 G 的逆线图。

Ego Graph#

自我图谱。

ego_graph(G, n[, radius, center, ...])

返回以节点 n 为中心，在给定半径内的邻居诱导子图。

Stochastic#

生成给定加权有向图的随机图的函数。

stochastic_graph(G[, copy, weight])

返回有向图 G 的右随机表示形式。

AS graph#

生成类似互联网自治系统网络的图表

random_internet_as_graph(n[, seed])

生成一个类似于互联网AS网络的随机无向图

Intersection#

随机交集图生成器。

uniform_random_intersection_graph(n, m, p[, ...])

返回一个均匀随机交集图。

k_random_intersection_graph(n, m, k[, seed])

返回一个交集图，其中每个节点的属性集是随机选择的，并且大小相等（k）。

general_random_intersection_graph(n, m, p[, ...])

返回一个具有独立概率的随机交集图，用于节点和属性集之间的连接。

Social Networks#

著名的社交网络。

karate_club_graph()

返回 Zachary 的空手道俱乐部图。

davis_southern_women_graph()

返回戴维斯南方女性社交网络。

florentine_families_graph()

返回佛罗伦萨家族图。

les_miserables_graph()

返回小说《悲惨世界》中角色的共现网络。

Community#

用于研究社交网络的图类生成器。

caveman_graph(l, k)

返回一个由 l 个大小为 k 的团组成的洞穴人图。

connected_caveman_graph(l, k)

返回一个由 l 个大小为 k 的团组成的连通洞穴人图。

gaussian_random_partition_graph(n, s, v, ...)

生成一个高斯随机分区图。

LFR_benchmark_graph(n, tau1, tau2, mu[, ...])

返回LFR基准图。

planted_partition_graph(l, k, p_in, p_out[, ...])

返回种植的 l-分区图。

random_partition_graph(sizes, p_in, p_out[, ...])

返回具有指定大小分区的随机分区图。

relaxed_caveman_graph(l, k, p[, seed])

返回一个松弛的洞穴人图。

ring_of_cliques(num_cliques, clique_size)

定义一个“团环”图。

stochastic_block_model(sizes, p[, nodelist, ...])

返回一个随机块模型图。

windmill_graph(n, k)

生成一个风车图。 风车图是由 n 个大小为 k 的完全子图组成，这些子图都连接在一个节点上。 可以将其视为取 n 个大小为 k 的完全子图的不相交并集，选择每个子图中的一个点，并将所有选中的点收缩。 或者，可以生成 n 个大小为 k-1 的完全子图和一个连接到图中所有其他节点的节点。

Spectral#

生成具有给定特征向量结构的图

spectral_graph_forge(G, alpha[, ...])

返回一个具有与 G 相似谱的随机简单图

Trees#

生成树的函数。

本模块中随机采样树的函数分为两种变体：有标签和无标签。有标签变体从具有给定节点数的所有可能树中均匀随机采样。无标签变体从具有给定节点数的所有可能的*同构类*树中均匀随机采样。

要理解差异，请考虑以下示例。有四个节点的树有两个同构类。一个是路径图，另一个是星形图。无标签变体会以1/2的概率返回线图或星形图。

有标签变体会以3/4的概率返回线图，以1/4的概率返回星形图，因为线图的有标签变体比星形图多。更确切地说，线图的自同构群的阶数为2，而星形图的自同构群的阶数为6，因此线图的有标签变体是星形图的三倍，从而有更多的机会被抽中。

此外，本模块中的一些函数可以均匀随机采样有根树和森林。有根树是具有指定根节点的树。有根森林是不相交的有根树的并集。

prefix_tree(paths)

从路径列表创建一个有向前缀树。

random_labeled_tree(n, *[, seed])

返回一个在 n 个节点上均匀随机选择的标记树。

random_labeled_rooted_tree(n, *[, seed])

返回一个包含 n 个节点的标记根树。

random_labeled_rooted_forest(n, *[, seed])

返回一个带有 n 个节点的标记根森林。

random_unlabeled_tree(n, *[, ...])

返回一个随机选择的树或树列表。

random_unlabeled_rooted_tree(n, *[, ...])

返回一个随机均匀选择的未标记有根树的数量

random_unlabeled_rooted_forest(n, *[, q, ...])

返回一个随机选择的森林或森林列表。

Non Isomorphic Trees#

Wright、Richmond、Odlyzko和McKay（WROM）算法的实现，用于枚举给定阶数的所有非同构自由树。有根树通过层序列表示，即列表中第i个元素指定顶点i到根的距离。

nonisomorphic_trees(order[, create])

生成非同构树的列表

number_of_nonisomorphic_trees(order)

返回非同构树的数量

Triads#

生成三元图的函数，即在三个节点上的可能有向图。

triad_graph(triad_name)

返回具有给定名称的三元图。

Joint Degree Sequence#

生成具有给定联合度和有向联合度的图

is_valid_joint_degree(joint_degrees)

检查给定的联合度字典是否可实现。

joint_degree_graph(joint_degrees[, seed])

生成具有给定联合度字典的随机简单图。

is_valid_directed_joint_degree(in_degrees, ...)

检查给定的有向联合度输入是否可实现

directed_joint_degree_graph(in_degrees, ...)

生成具有联合度序列的随机简单有向图。

Mycielski#

与Mycielski操作和Mycielskian图族相关的函数。

mycielskian(G[, iterations])

返回一个简单无向图 G 的 Mycielski 图

mycielski_graph(n)

生成第 n 个 Mycielski 图的生成器。

Harary Graph#

哈拉里图生成器

本模块提供了两种生成哈拉里图的方法，这种图是由著名数学家弗兰克·哈拉里在其1962年的著作[H]中提出的。第一个生成器生成的哈拉里图在给定节点数和边数的情况下，最大化节点连通性。第二个生成器生成的哈拉里图在给定节点连通性和节点数的情况下，最小化图中的边数。

References#

[H]

Harary, F. “图的最大连通性.” 美国国家科学院院刊 48, 1142-1146, 1962.

hnm_harary_graph(n, m[, create_using])

返回具有给定节点数和边数的Harary图。

hkn_harary_graph(k, n[, create_using])

返回具有给定节点连通性和节点数量的Harary图。

Cographs#

生成cograph的生成器

cograph是一种不包含四个顶点路径的图。 cograph或:math:P_4-free图可以通过不相交并集和补集操作从一个单个顶点获得。

References#

[0]

D.G. Corneil, H. Lerchs, L.Stewart Burlingham, “补图可约图”, 离散应用数学, 第3卷, 第3期, 1981年, 第163-174页, ISSN 0166-218X.

random_cograph(n[, seed])

返回一个包含 \(2 ^ n\) 个节点的随机cograph。

Interval Graph#

区间图生成器。

interval_graph(intervals)

生成给定区间列表的区间图。

Sudoku#

数独图生成器

此模块提供了一个生成n-数独图的工具。它可以用于开发解决或生成数独谜题的算法。

一个完成的数独网格是一个9x9的整数数组，范围在1到9之间，没有任何数字在同一行、列或3x3的方框中出现两次。

8 6 4
3 2 5
9 7 1
3 7 1
8 4 9
2 6 5
2 5 9
7 6 1
8 4 3
4 3 6
1 9 8
2 5 7
1 9 2
6 5 7
4 8 3
5 8 7
4 3 2
9 1 6
6 8 9
7 1 3
5 4 2
7 3 4
5 2 8
9 1 6
1 2 5
6 9 4
3 7 8

数独图是一个无向图，包含81个顶点，对应于数独网格的单元格。它是一个度数为20的正则图。两个不同的顶点相邻当且仅当对应的单元格属于同一行、列或方框。一个完成的数独网格对应于数独图的九种颜色的顶点着色。

更一般地，n-数独图是一个包含n^4个顶点的图，对应于一个n^2乘n^2的网格。两个不同的顶点相邻当且仅当它们属于同一行、列或n乘n的方框。

References#

[1]

Herzberg, A. M., & Murty, M. R. (2007). 数独方块与染色多项式。美国数学学会通告, 54(6), 708-717.

[2]

Sander, Torsten (2009), “数独图是整数”, 组合学电子杂志, 16 (1): 注释25, 7页, MR 2529816

[3]

Wikipedia contributors. “数独术语表.” 维基百科, 自由百科全书, 2019年12月3日. 网络. 2019年12月22日.

sudoku_graph([n])

返回 n-数独图。默认值 n 为 3。

Time Series#

时间序列图

visibility_graph(series)

返回输入时间序列的可视图（Visibility Graph）。
On this page