Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Graph generators

Atlas

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.

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

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]) 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 degree distribution and approximate average clustering.
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 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 degree and triangle degree sequence.

Directed

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.

Geometric

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.

Hybrid

Hybrid

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.

Bipartite

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 Havel-Hakimi style construction.
bipartite_reverse_havel_hakimi_graph(aseq, bseq) Return a bipartite graph from two given degree sequences using a Havel-Hakimi style construction.
bipartite_alternating_havel_hakimi_graph(...) Return a bipartite graph from two given degree sequences using an alternating Havel-Hakimi style construction.
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 graph algorithms.

Undirected Graphs

For an undirected graph G without multiple edges, each edge can be written as a set {u,v}. Its line graph L has the edges of G as its nodes. If x and y are two nodes in L, then {x,y} is an edge in L if and only if the intersection of x and y is nonempty. Thus, the set of all edges is determined by the set of all pair-wise intersections of edges in G.

Trivially, every edge x={u,v} in G would have a nonzero intersection with itself, and so every node in L should have a self-loop. This is not so interesting, and the original context of line graphs was with simple graphs, which had no self-loops or multiple edges. The line graph was also meant to be simple graph and thus, self-loops in L are not part of the standard definition of a line graph. In a pair-wise intersection matrix, this is analogous to not including the diagonal as part of the line graph definition.

Self-loops and multiple edges in G add nodes to L in a natural way, and do not require any fundamental changes to the definition. It might be argued that the self-loops we excluded before should now be included. However, the self-loops are still “trivial” in some sense and thus, are usually excluded.

Directed Graphs

For a directed graph G without multiple edges, each edge can be written as a tuple (u,v). Its line graph L has the edges of G as its nodes. If x=(a,b) and y=(c,d) are two nodes in L, then (x,y) is an edge in L if and only if the tail of x matches the head of y—e.g., b=c.

Due to the directed nature of the edges, it is no longer the case that every edge x=(u,v) should be connected to itself with a self-loop in L. Now, the only time self-loops arise is if G itself has a self-loop. So such self-loops are no longer “trivial” but instead, represent essential features of the topology of G. For this reason, the historical development of line digraphs is such that self-loops are included. When the graph G has multiple edges, once again only superficial changes are required to the definition.

References

Harary, Frank, and Norman, Robert Z., “Some properties of line digraphs”,
Rend. Circ. Mat. Palermo, II. Ser. 9 (1960), 161–168.
Hemminger, R. L.; Beineke, L. W. (1978), “Line graphs and line digraphs”,
in Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, Academic Press Inc., pp. 271–305.
line_graph(G[, create_using]) 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.

Stochastic

Stocastic graph.

stochastic_graph(G[, copy, weight]) Return a right-stochastic representation of 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.