Skip to main content
This page is documentation for a DEVELOPMENT / PRE-RELEASE version. Switch to stable version
Ctrl+K

NetworkX User Survey 2023 🎉 Fill out the survey to tell us about your ideas, complaints, praises of NetworkX!

Logo image

Site Navigation

  • Install
  • Tutorial
  • Reference
  • Gallery
  • Developer
  • Releases
  • Guides
    • devel (latest)
    • current (stable)

Site Navigation

  • Install
  • Tutorial
  • Reference
  • Gallery
  • Developer
  • Releases
  • Guides
    • devel (latest)
    • current (stable)

Section Navigation

  • Introduction
  • Graph types
  • Algorithms
  • Functions
  • Graph generators
    • graph_atlas
    • graph_atlas_g
    • balanced_tree
    • barbell_graph
    • binomial_tree
    • complete_graph
    • complete_multipartite_graph
    • circular_ladder_graph
    • circulant_graph
    • cycle_graph
    • dorogovtsev_goltsev_mendes_graph
    • empty_graph
    • full_rary_tree
    • ladder_graph
    • lollipop_graph
    • null_graph
    • path_graph
    • star_graph
    • trivial_graph
    • turan_graph
    • wheel_graph
    • margulis_gabber_galil_graph
    • chordal_cycle_graph
    • paley_graph
    • grid_2d_graph
    • grid_graph
    • hexagonal_lattice_graph
    • hypercube_graph
    • triangular_lattice_graph
    • LCF_graph
    • bull_graph
    • chvatal_graph
    • cubical_graph
    • desargues_graph
    • diamond_graph
    • dodecahedral_graph
    • frucht_graph
    • heawood_graph
    • hoffman_singleton_graph
    • house_graph
    • house_x_graph
    • icosahedral_graph
    • krackhardt_kite_graph
    • moebius_kantor_graph
    • octahedral_graph
    • pappus_graph
    • petersen_graph
    • sedgewick_maze_graph
    • tetrahedral_graph
    • truncated_cube_graph
    • truncated_tetrahedron_graph
    • tutte_graph
    • fast_gnp_random_graph
    • gnp_random_graph
    • dense_gnm_random_graph
    • gnm_random_graph
    • erdos_renyi_graph
    • binomial_graph
    • newman_watts_strogatz_graph
    • watts_strogatz_graph
    • connected_watts_strogatz_graph
    • random_regular_graph
    • barabasi_albert_graph
    • dual_barabasi_albert_graph
    • extended_barabasi_albert_graph
    • powerlaw_cluster_graph
    • random_kernel_graph
    • random_lobster
    • random_shell_graph
    • random_powerlaw_tree
    • random_powerlaw_tree_sequence
    • random_kernel_graph
    • duplication_divergence_graph
    • partial_duplication_graph
    • configuration_model
    • directed_configuration_model
    • expected_degree_graph
    • havel_hakimi_graph
    • directed_havel_hakimi_graph
    • degree_sequence_tree
    • random_degree_sequence_graph
    • random_clustered_graph
    • gn_graph
    • gnr_graph
    • gnc_graph
    • random_k_out_graph
    • scale_free_graph
    • geometric_edges
    • geographical_threshold_graph
    • navigable_small_world_graph
    • random_geometric_graph
    • soft_random_geometric_graph
    • thresholded_random_geometric_graph
    • waxman_graph
    • line_graph
    • inverse_line_graph
    • ego_graph
    • stochastic_graph
    • random_internet_as_graph
    • uniform_random_intersection_graph
    • k_random_intersection_graph
    • general_random_intersection_graph
    • karate_club_graph
    • davis_southern_women_graph
    • florentine_families_graph
    • les_miserables_graph
    • caveman_graph
    • connected_caveman_graph
    • gaussian_random_partition_graph
    • LFR_benchmark_graph
    • planted_partition_graph
    • random_partition_graph
    • relaxed_caveman_graph
    • ring_of_cliques
    • stochastic_block_model
    • windmill_graph
    • spectral_graph_forge
    • random_tree
    • prefix_tree
    • nonisomorphic_trees
    • number_of_nonisomorphic_trees
    • triad_graph
    • is_valid_joint_degree
    • joint_degree_graph
    • is_valid_directed_joint_degree
    • directed_joint_degree_graph
    • mycielskian
    • mycielski_graph
    • hnm_harary_graph
    • hkn_harary_graph
    • random_cograph
    • interval_graph
    • sudoku_graph
  • Linear algebra
  • Converting to and from other data formats
  • Relabeling nodes
  • Reading and writing graphs
  • Drawing
  • Randomness
  • Exceptions
  • Utilities
  • Glossary
  • Reference
  • Graph generators
  • navigable_small_world_graph

navigable_small_world_graph#

navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None)[source]#

Returns a navigable small-world graph.

A navigable small-world graph is a directed grid with additional long-range connections that are chosen randomly.

[…] we begin with a set of nodes […] that are identified with the set of lattice points in an \(n \times n\) square, \(\{(i, j): i \in \{1, 2, \ldots, n\}, j \in \{1, 2, \ldots, n\}\}\), and we define the lattice distance between two nodes \((i, j)\) and \((k, l)\) to be the number of “lattice steps” separating them: \(d((i, j), (k, l)) = |k - i| + |l - j|\).

For a universal constant \(p >= 1\), the node \(u\) has a directed edge to every other node within lattice distance \(p\)—these are its local contacts. For universal constants \(q >= 0\) and \(r >= 0\) we also construct directed edges from \(u\) to \(q\) other nodes (the long-range contacts) using independent random trials; the \(i`th directed edge from :math:`u\) has endpoint \(v\) with probability proportional to \([d(u,v)]^{-r}\).

—[1]

Parameters:
nint

The length of one side of the lattice; the number of nodes in the graph is therefore \(n^2\).

pint

The diameter of short range connections. Each node is joined with every other node within this lattice distance.

qint

The number of long-range connections for each node.

rfloat

Exponent for decaying probability of connections. The probability of connecting to a node at lattice distance \(d\) is \(1/d^r\).

dimint

Dimension of grid

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

References

[1]

J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.

Ctrl+K
On this page
  • navigable_small_world_graph()

© Copyright 2004-2023, NetworkX Developers.

Created using Sphinx 6.1.3.

Built with the PyData Sphinx Theme 0.13.1.