Graph generators

Atlas

Generators for the small graph atlas.

graph_atlas(i) Returns graph number i from the Graph Atlas.
graph_atlas_g() Return 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]) Return the perfectly balanced r-ary tree of height h.
barbell_graph(m1, m2[, create_using]) Return 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]) Return the circular ladder graph \(CL_n\) of length n.
cycle_graph(n[, create_using]) Return the cycle graph \(C_n\) of cyclically connected nodes.
dorogovtsev_goltsev_mendes_graph(n[, …]) Return the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph.
empty_graph([n, create_using]) Return the empty graph with n nodes and zero edges.
ladder_graph(n[, create_using]) Return the Ladder graph of length n.
lollipop_graph(m, n[, create_using]) Return the Lollipop Graph; K_m connected to P_n.
null_graph([create_using]) Return the Null graph with no nodes or edges.
path_graph(n[, create_using]) Return 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]) Return the Margulis-Gabber-Galil undirected MultiGraph on n^2 nodes.
chordal_cycle_graph(p[, create_using]) Return 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 relevent 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]) Return the Bull graph.
chvatal_graph([create_using]) Return the Chvátal graph.
cubical_graph([create_using]) Return the 3-regular Platonic Cubical graph.
desargues_graph([create_using]) Return the Desargues graph.
diamond_graph([create_using]) Return the Diamond graph.
dodecahedral_graph([create_using]) Return the Platonic Dodecahedral graph.
frucht_graph([create_using]) Return the Frucht Graph.
heawood_graph([create_using]) Return the Heawood graph, a (3,6) cage.
house_graph([create_using]) Return the House graph (square with triangle on top).
house_x_graph([create_using]) Return the House graph with a cross inside the house square.
icosahedral_graph([create_using]) Return the Platonic Icosahedral graph.
krackhardt_kite_graph([create_using]) Return the Krackhardt Kite Social Network.
moebius_kantor_graph([create_using]) Return the Moebius-Kantor graph.
octahedral_graph([create_using]) Return the Platonic Octahedral graph.
pappus_graph() Return the Pappus graph.
petersen_graph([create_using]) Return 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]) Return the skeleton of the truncated cube.
truncated_tetrahedron_graph([create_using]) Return the skeleton of the truncated Platonic tetrahedron.
tutte_graph([create_using]) Return 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]) Return a Newman–Watts–Strogatz small-world graph.
watts_strogatz_graph(n, k, p[, seed]) Return 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.
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[, …]) Return 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.

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]) Return 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[, …]) Return a random graph with the given degree sequence.
directed_configuration_model(…[, …]) Return a directed_random graph with the given degree sequences.
expected_degree_graph(w[, seed, selfloops]) Return a random graph with given expected degrees.
havel_hakimi_graph(deg_sequence[, create_using]) Return a simple graph with given degree sequence constructed using the Havel-Hakimi algorithm.
directed_havel_hakimi_graph(in_deg_sequence, …) Return 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[, …]) Return 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]) Return the growing network (GN) digraph with n nodes.
gnr_graph(n, p[, create_using, seed]) Return the growing network with redirection (GNR) digraph with n nodes and redirection probability p.
gnc_graph(n[, create_using, seed]) Return 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, pos, p]) Returns a random geometric graph in the unit cube.
geographical_threshold_graph(n, theta[, …]) Returns a geographical threshold graph.
waxman_graph(n[, beta, alpha, L, domain, metric]) Return a Waxman random graph.
navigable_small_world_graph(n[, p, q, r, …]) Return a navigable small-world graph.

Line Graph

Functions for generating line graphs.

line_graph(G[, create_using]) Returns the line graph of the graph or digraph 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[, …]) Return a uniform random intersection graph.
k_random_intersection_graph(n, m, k) Return a intersection graph with randomly chosen attribute sets for each node that are of equal size (k).
general_random_intersection_graph(n, m, p) Return a random intersection graph with independent probabilities for connections between node and attribute sets.

Social Networks

Famous social networks.

karate_club_graph() Return Zachary’s Karate Club graph.
davis_southern_women_graph() Return Davis Southern women social network.
florentine_families_graph() Return Florentine families graph.

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]) Return a relaxed caveman graph.
random_partition_graph(sizes, p_in, p_out[, …]) Return the random partition graph with a partition of sizes.
planted_partition_graph(l, k, p_in, p_out[, …]) Return 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.
windmill_graph(n, k) Generate a windmill graph.

Trees

Functions for generating trees.

random_tree(n[, seed]) Returns a uniformly random tree on n nodes.

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.