Table Of Contents

Previous topic


Next topic


Graph generators


Generators for the small graph atlas.

See “An Atlas of Graphs” by Ronald C. Read and Robin J. Wilson, Oxford University Press, 1998.

Because of its size, this module is not imported by default.

graph_atlas_g() Return the list [G0,G1,...,G1252] of graphs as named in the Graph Atlas.


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-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_bipartite_graph(n1, n2[, create_using]) Return the complete bipartite graph K_{n1_n2}.
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 over n 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.
grid_2d_graph(m, n[, periodic, create_using]) Return the 2d grid graph of mxn nodes, each connected to its nearest neighbors.
grid_graph(dim[, periodic]) Return the n-dimensional grid graph.
hypercube_graph(n) Return the n-dimensional hypercube.
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 n nodes linearly connected by n-1 edges.
star_graph(n[, create_using]) Return the Star graph with n+1 nodes: one center node, connected to n outer nodes.
trivial_graph([create_using]) Return the Trivial graph with one node (with integer label 0) and no edges.
wheel_graph(n[, create_using]) Return the wheel graph: a single hub node connected to each node of the (n-1)-node cycle graph.


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]) Return a random graph G_{n,p} (Erdős-Rényi graph, binomial graph).
gnp_random_graph(n, p[, seed, directed]) Return a random graph G_{n,p} (Erdős-Rényi graph, binomial graph).
dense_gnm_random_graph(n, m[, seed]) Return the random graph G_{n,m}.
gnm_random_graph(n, m[, seed, directed]) Return the random graph G_{n,m}.
erdos_renyi_graph(n, p[, seed, directed]) Return a random graph G_{n,p} (Erdős-Rényi graph, binomial graph).
binomial_graph(n, p[, seed, directed]) Return a random graph G_{n,p} (Erdős-Rényi graph, 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[, ...]) Return a connected Watts-Strogatz small-world graph.
random_regular_graph(d, n[, seed]) Return a random regular graph of n nodes each with degree d.
barabasi_albert_graph(n, m[, seed]) Return random graph using Barabási-Albert preferential attachment model.
powerlaw_cluster_graph(n, m, p[, seed]) Holme and Kim algorithm for growing graphs with powerlaw
random_lobster(n, p1, p2[, seed]) Return a random lobster.
random_shell_graph(constructor[, seed]) Return a random shell graph for the constructor given.
random_powerlaw_tree(n[, gamma, seed, tries]) Return a tree with a powerlaw degree distribution.
random_powerlaw_tree_sequence(n[, gamma, ...]) Return a degree sequence for a tree with a powerlaw distribution.

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
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 degree and triangle degree sequence.


Generators for some directed graphs.

gn_graph: growing network gnc_graph: growing network with copying gnr_graph: growing network with redirection scale_free_graph: scale free directed graph

gn_graph(n[, kernel, create_using, seed]) Return the GN digraph with n nodes.
gnr_graph(n, p[, create_using, seed]) Return the GNR digraph with n nodes and redirection probability p.
gnc_graph(n[, create_using, seed]) Return the GNC digraph with n nodes.
scale_free_graph(n[, alpha, beta, gamma, ...]) Return a scale free directed graph.


Generators for geometric graphs.

random_geometric_graph(n, radius[, dim, pos]) Return the random geometric graph in the unit cube.
geographical_threshold_graph(n, theta[, ...]) Return a geographical threshold graph.
waxman_graph(n[, alpha, beta, L, domain]) Return a Waxman random graph.
navigable_small_world_graph(n[, p, q, r, ...]) Return a navigable small-world graph.



kl_connected_subgraph(G, k, l[, low_memory, ...]) Returns the maximum locally (k,l) connected subgraph of G.
is_kl_connected(G, k, l[, low_memory]) Returns True if G is kl connected.


Generators and functions for bipartite graphs.

bipartite_configuration_model(aseq, bseq[, ...]) Return a random bipartite graph from two given degree sequences.
bipartite_havel_hakimi_graph(aseq, bseq[, ...]) Return a bipartite graph from two given degree sequences using a
bipartite_reverse_havel_hakimi_graph(aseq, bseq) Return a bipartite graph from two given degree sequences using a
bipartite_alternating_havel_hakimi_graph(...) Return a bipartite graph from two given degree sequences using
bipartite_preferential_attachment_graph(aseq, p) Create a bipartite graph with a preferential attachment model from a given single degree sequence.
bipartite_random_graph(n, m, p[, seed, directed]) Return a bipartite random graph.
bipartite_gnmk_random_graph(n, m, k[, seed, ...]) Return a random bipartite graph G_{n,m,k}.

Line Graph

Line graphs.

line_graph(G) Return 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.


Stocastic graph.

stochastic_graph(G[, copy, weight]) Return a right-stochastic representation of G.


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.