Graph generators

Atlas

Generators for the small graph atlas.

graph_atlas(i)

Returns graph number i from the Graph Atlas.

graph_atlas_g()

Returns the list of all graphs with up to seven nodes named in the Graph Atlas.

Classic

Generators for some classic graphs.

The typical graph generator is called as follows:

>>> G = nx.complete_graph(100)

returning the complete graph on n nodes labeled 0, .., 99 as a simple graph. Except for empty_graph, all the generators in this module return a Graph class (i.e. a simple, undirected graph).

balanced_tree(r, h[, create_using])

Returns the perfectly balanced r-ary tree of height h.

barbell_graph(m1, m2[, create_using])

Returns the Barbell Graph: two complete graphs connected by a path.

complete_graph(n[, create_using])

Return the complete graph K_n with n nodes.

complete_multipartite_graph(*subset_sizes)

Returns the complete multipartite graph with the specified subset sizes.

circular_ladder_graph(n[, create_using])

Returns the circular ladder graph \(CL_n\) of length n.

circulant_graph(n, offsets[, create_using])

Generates the circulant graph \(Ci_n(x_1, x_2, ..., x_m)\) with \(n\) vertices.

cycle_graph(n[, create_using])

Returns the cycle graph \(C_n\) of cyclically connected nodes.

dorogovtsev_goltsev_mendes_graph(n[, …])

Returns the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph.

empty_graph([n, create_using, default])

Returns the empty graph with n nodes and zero edges.

full_rary_tree(r, n[, create_using])

Creates a full r-ary tree of n vertices.

ladder_graph(n[, create_using])

Returns the Ladder graph of length n.

lollipop_graph(m, n[, create_using])

Returns the Lollipop Graph; K_m connected to P_n.

null_graph([create_using])

Returns the Null graph with no nodes or edges.

path_graph(n[, create_using])

Returns the Path graph P_n of linearly connected nodes.

star_graph(n[, create_using])

Return the star graph

trivial_graph([create_using])

Return the Trivial graph with one node (with label 0) and no edges.

turan_graph(n, r)

Return the Turan Graph

wheel_graph(n[, create_using])

Return the wheel graph

Expanders

Provides explicit constructions of expander graphs.

margulis_gabber_galil_graph(n[, create_using])

Returns the Margulis-Gabber-Galil undirected MultiGraph on n^2 nodes.

chordal_cycle_graph(p[, create_using])

Returns the chordal cycle graph on p nodes.

Lattice

Functions for generating grid graphs and lattices

The grid_2d_graph(), triangular_lattice_graph(), and hexagonal_lattice_graph() functions correspond to the three regular tilings of the plane, the square, triangular, and hexagonal tilings, respectively. grid_graph() and hypercube_graph() are similar for arbitrary dimensions. Useful relevant discussion can be found about Triangular Tiling, and Square, Hex and Triangle Grids

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

Returns the two-dimensional grid graph.

grid_graph(dim[, periodic])

Returns the n-dimensional grid graph.

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

Returns an m by n hexagonal lattice graph.

hypercube_graph(n)

Returns the n-dimensional hypercube graph.

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

Returns the \(m\) by \(n\) triangular lattice graph.

Small

Various small and named graphs, together with some compact generators.

make_small_graph(graph_description[, …])

Return the small graph described by graph_description.

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

Return the cubic graph specified in LCF notation.

bull_graph([create_using])

Returns the Bull graph.

chvatal_graph([create_using])

Returns the Chvátal graph.

cubical_graph([create_using])

Returns the 3-regular Platonic Cubical graph.

desargues_graph([create_using])

Return the Desargues graph.

diamond_graph([create_using])

Returns the Diamond graph.

dodecahedral_graph([create_using])

Return the Platonic Dodecahedral graph.

frucht_graph([create_using])

Returns the Frucht Graph.

heawood_graph([create_using])

Return the Heawood graph, a (3,6) cage.

hoffman_singleton_graph()

Return the Hoffman-Singleton Graph.

house_graph([create_using])

Returns the House graph (square with triangle on top).

house_x_graph([create_using])

Returns the House graph with a cross inside the house square.

icosahedral_graph([create_using])

Returns the Platonic Icosahedral graph.

krackhardt_kite_graph([create_using])

Return the Krackhardt Kite Social Network.

moebius_kantor_graph([create_using])

Returns the Moebius-Kantor graph.

octahedral_graph([create_using])

Returns the Platonic Octahedral graph.

pappus_graph()

Return the Pappus graph.

petersen_graph([create_using])

Returns the Petersen graph.

sedgewick_maze_graph([create_using])

Return a small maze with a cycle.

tetrahedral_graph([create_using])

Return the 3-regular Platonic Tetrahedral graph.

truncated_cube_graph([create_using])

Returns the skeleton of the truncated cube.

truncated_tetrahedron_graph([create_using])

Returns the skeleton of the truncated Platonic tetrahedron.

tutte_graph([create_using])

Returns the Tutte graph.

Random Graphs

Generators for random graphs.

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

Returns a \(G_{n,p}\) random graph, also known as an Erdős-Rényi graph or a binomial graph.

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

Returns a \(G_{n,p}\) random graph, also known as an Erdős-Rényi graph or a binomial graph.

dense_gnm_random_graph(n, m[, seed])

Returns a \(G_{n,m}\) random graph.

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

Returns a \(G_{n,m}\) random graph.

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

Returns a \(G_{n,p}\) random graph, also known as an Erdős-Rényi graph or a binomial graph.

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

Returns a \(G_{n,p}\) random graph, also known as an Erdős-Rényi graph or a binomial graph.

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

Returns a Newman–Watts–Strogatz small-world graph.

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

Returns a Watts–Strogatz small-world graph.

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

Returns a connected Watts–Strogatz small-world graph.

random_regular_graph(d, n[, seed])

Returns a random \(d\)-regular graph on \(n\) nodes.

barabasi_albert_graph(n, m[, seed])

Returns a random graph according to the Barabási–Albert preferential attachment model.

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

Returns a random graph according to the dual Barabási–Albert preferential attachment model.

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

Returns an extended Barabási–Albert model graph.

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

Holme and Kim algorithm for growing graphs with powerlaw degree distribution and approximate average clustering.

random_kernel_graph(n, kernel_integral[, …])

Returns an random graph based on the specified kernel.

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

Returns a random lobster graph.

random_shell_graph(constructor[, seed])

Returns a random shell graph for the constructor given.

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

Returns a tree with a power law degree distribution.

random_powerlaw_tree_sequence(n[, gamma, …])

Returns a degree sequence for a tree with a power law distribution.

random_kernel_graph(n, kernel_integral[, …])

Returns an random graph based on the specified kernel.

Duplication Divergence

Functions for generating graphs based on the “duplication” method.

These graph generators start with a small initial graph then duplicate nodes and (partially) duplicate their edges. These functions are generally inspired by biological networks.

duplication_divergence_graph(n, p[, seed])

Returns an undirected graph using the duplication-divergence model.

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

Returns a random graph using the partial duplication model.

Degree Sequence

Generate graphs with a given degree sequence or expected degree sequence.

configuration_model(deg_sequence[, …])

Returns a random graph with the given degree sequence.

directed_configuration_model(…[, …])

Returns a directed_random graph with the given degree sequences.

expected_degree_graph(w[, seed, selfloops])

Returns a random graph with given expected degrees.

havel_hakimi_graph(deg_sequence[, create_using])

Returns a simple graph with given degree sequence constructed using the Havel-Hakimi algorithm.

directed_havel_hakimi_graph(in_deg_sequence, …)

Returns a directed graph with the given degree sequences.

degree_sequence_tree(deg_sequence[, …])

Make a tree for the given degree sequence.

random_degree_sequence_graph(sequence[, …])

Returns a simple random graph with the given degree sequence.

Random Clustered

Generate graphs with given degree and triangle sequence.

random_clustered_graph(joint_degree_sequence)

Generate a random graph with the given joint independent edge degree and triangle degree sequence.

Directed

Generators for some directed graphs, including growing network (GN) graphs and scale-free graphs.

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

Returns the growing network (GN) digraph with n nodes.

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

Returns the growing network with redirection (GNR) digraph with n nodes and redirection probability p.

gnc_graph(n[, create_using, seed])

Returns the growing network with copying (GNC) digraph with n nodes.

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

Returns a random k-out graph with preferential attachment.

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

Returns a scale-free directed graph.

Geometric

Generators for geometric graphs.

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

Returns a random geometric graph in the unit cube of dimensions dim.

soft_random_geometric_graph(n, radius[, …])

Returns a soft random geometric graph in the unit cube.

geographical_threshold_graph(n, theta[, …])

Returns a geographical threshold graph.

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

Returns a Waxman random graph.

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

Returns a navigable small-world graph.

thresholded_random_geometric_graph(n, …[, …])

Returns a thresholded random geometric graph in the unit cube.

Line Graph

Functions for generating line graphs.

line_graph(G[, create_using])

Returns the line graph of the graph or digraph G.

inverse_line_graph(G)

Returns the inverse line graph of graph G.

Ego Graph

Ego graph.

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

Returns induced subgraph of neighbors centered at node n within a given radius.

Stochastic

Functions for generating stochastic graphs from a given weighted directed graph.

stochastic_graph(G[, copy, weight])

Returns a right-stochastic representation of directed graph G.

Intersection

Generators for random intersection graphs.

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

Returns a uniform random intersection graph.

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

Returns a intersection graph with randomly chosen attribute sets for each node that are of equal size (k).

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

Returns a random intersection graph with independent probabilities for connections between node and attribute sets.

Social Networks

Famous social networks.

karate_club_graph()

Returns Zachary’s Karate Club graph.

davis_southern_women_graph()

Returns Davis Southern women social network.

florentine_families_graph()

Returns Florentine families graph.

les_miserables_graph()

Returns coappearance network of characters in the novel Les Miserables.

Community

Generators for classes of graphs used in studying social networks.

caveman_graph(l, k)

Returns a caveman graph of l cliques of size k.

connected_caveman_graph(l, k)

Returns a connected caveman graph of l cliques of size k.

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

Returns a relaxed caveman graph.

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

Returns the random partition graph with a partition of sizes.

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

Returns the planted l-partition graph.

gaussian_random_partition_graph(n, s, v, …)

Generate a Gaussian random partition graph.

ring_of_cliques(num_cliques, clique_size)

Defines a “ring of cliques” graph.

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

Returns a stochastic block model graph.

windmill_graph(n, k)

Generate a windmill graph.

Spectral

Generates graphs with a given eigenvector structure

spectral_graph_forge(G, alpha[, …])

Returns a random simple graph with spectrum resembling that of G

Trees

Functions for generating trees.

random_tree(n[, seed])

Returns a uniformly random tree on n nodes.

prefix_tree(paths)

Creates a directed prefix tree from the given list of iterables.

Non Isomorphic Trees

Implementation of the Wright, Richmond, Odlyzko and McKay (WROM) algorithm for the enumeration of all non-isomorphic free trees of a given order. Rooted trees are represented by level sequences, i.e., lists in which the i-th element specifies the distance of vertex i to the root.

nonisomorphic_trees(order[, create])

Returns a list of nonisomporphic trees

number_of_nonisomorphic_trees(order)

Returns the number of nonisomorphic trees

Triads

Functions that generate the triad graphs, that is, the possible digraphs on three nodes.

triad_graph(triad_name)

Returns the triad graph with the given name.

Joint Degree Sequence

Generate graphs with a given joint degree

is_valid_joint_degree(joint_degrees)

Checks whether the given joint degree dictionary is realizable as a simple graph.

joint_degree_graph(joint_degrees[, seed])

Generates a random simple graph with the given joint degree dictionary.

Mycielski

Functions related to the Mycielski Operation and the Mycielskian family of graphs.

mycielskian(G[, iterations])

Returns the Mycielskian of a simple, undirected graph G

mycielski_graph(n)

Generator for the n_th Mycielski Graph.