NetworkX
1.10.1
  • Overview
  • Download
  • Installing
  • Tutorial
  • Reference
    • Introduction
    • Graph types
    • Algorithms
    • Functions
    • Graph generators
      • Atlas
      • Classic
      • Expanders
      • Small
      • Random Graphs
      • Degree Sequence
      • Random Clustered
      • Directed
      • Geometric
        • random_geometric_graph
        • geographical_threshold_graph
        • waxman_graph
        • navigable_small_world_graph
      • Line Graph
      • Ego Graph
      • Stochastic
      • Intersection
      • Social Networks
      • Community
      • Non Isomorphic Trees
    • Linear algebra
    • Converting to and from other data formats
    • Relabeling nodes
    • Reading and writing graphs
    • Drawing
    • Exceptions
    • Utilities
    • License
    • Citing
    • Credits
    • Glossary
    • Reference
      • Overview
      • Introduction
      • Graph types
      • Algorithms
      • Functions
      • Graph generators
        • Atlas
        • Classic
        • Expanders
        • Small
        • Random Graphs
        • Degree Sequence
        • Random Clustered
        • Directed
        • Geometric
        • Line Graph
        • Ego Graph
        • Stochastic
        • Intersection
        • Social Networks
        • Community
        • Non Isomorphic Trees
      • Linear algebra
      • Converting to and from other data formats
      • Reading and writing graphs
      • Drawing
      • Exceptions
      • Utilities
      • License
      • Citing
      • Credits
      • Glossary
  • Testing
  • Developer Guide
  • History
  • Bibliography
  • NetworkX Examples
 
NetworkX
  • Docs »
  • Reference »
  • Reference »
  • Graph generators »
  • navigable_small_world_graph

navigable_small_world_graph¶

networkx.generators.geometric.navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None)[source]¶

Return 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 imes 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 \geq 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 \ge 0 and r \ge 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 `u has endpoint v with probability proportional to [d(u,v)]^{-r}.

—[1]

Parameters:
  • n (int) – The number of nodes.
  • p (int) – The diameter of short range connections. Each node is joined with every other node within this lattice distance.
  • q (int) – The number of long-range connections for each node.
  • r (float) – Exponent for decaying probability of connections. The probability of connecting to a node at lattice distance d is 1/d^r.
  • dim (int) – Dimension of grid
  • seed (int, optional) – Seed for random number generator (default=None).

References

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

© Copyright 2015, NetworkX Developers. Last updated on Feb 16, 2016.

Built with Sphinx using a theme provided by Read the Docs.