NetworkX
  • Overview
    • Who uses NetworkX?
    • Goals
    • The Python programming language
    • Free software
    • History
  • Download
    • Software
    • Documentation
  • Installing
    • Quick install
    • Installing from source
    • Requirements
    • Optional packages
  • Tutorial
    • Creating a graph
    • Nodes
    • Edges
    • What to use as nodes and edges
    • Accessing edges
    • Adding attributes to graphs, nodes, and edges
    • Directed graphs
    • Multigraphs
    • Graph generators and graph operations
    • Analyzing graphs
    • Drawing graphs
  • Reference
    • Introduction
    • Graph types
    • Algorithms
    • Functions
    • Graph generators
    • Linear algebra
    • Converting to and from other data formats
    • Relabeling nodes
    • Reading and writing graphs
    • Drawing
    • Exceptions
    • Utilities
    • License
    • Citing
    • Credits
    • Glossary
    • Reference
  • Testing
    • Requirements for testing
    • Testing a source distribution
    • Testing an installed package
    • Testing for developers
  • Developer Guide
    • Working with networkx source code
  • History
    • API changes
    • Release Log
  • Bibliography
  • NetworkX Examples
    • 3D_Drawing
    • Advanced
    • Algorithms
    • Basic
    • Drawing
    • Graph
    • Javascript
    • Multigraph
    • Pygraphviz
    • Subclass
 
NetworkX
  • Docs »
  • Reference »
  • 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]¶

Return a navigable small-world graph.

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

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 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\), the node \(u\) has a directed edge to every other node within lattice distance \(p\) (local contacts) .

For universal constants \(q\ge 0\) and \(r\ge 0\) construct directed edges from \(u\) to \(q\) other nodes (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}\).

Parameters :

n : int

The number of nodes.

p : int

The diameter of short range connections. Each node is connected to every other node within lattice distance p.

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

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

© Copyright 2014, NetworkX Developers. Last updated on Nov 12, 2014.

Sphinx theme provided by Read the Docs