waxman_graph

waxman_graph(n, beta=0.4, alpha=0.1, L=None, domain=(0, 0, 1, 1), metric=None, seed=None)[source]

Returns a Waxman random graph.

The Waxman random graph model places n nodes uniformly at random in a rectangular domain. Each pair of nodes at distance d is joined by an edge with probability

\[p = \beta \exp(-d / \alpha L).\]

This function implements both Waxman models, using the L keyword argument.

  • Waxman-1: if L is not specified, it is set to be the maximum distance between any pair of nodes.

  • Waxman-2: if L is specified, the distance between a pair of nodes is chosen uniformly at random from the interval [0, L].

Parameters
nint or iterable

Number of nodes or iterable of nodes

beta: float

Model parameter

alpha: float

Model parameter

Lfloat, optional

Maximum distance between nodes. If not specified, the actual distance is calculated.

domainfour-tuple of numbers, optional

Domain size, given as a tuple of the form (x_min, y_min, x_max, y_max).

metricfunction

A metric on vectors of numbers (represented as lists or tuples). This must be a function that accepts two lists (or tuples) as input and yields a number as output. The function must also satisfy the four requirements of a metric. Specifically, if \(d\) is the function and \(x\), \(y\), and \(z\) are vectors in the graph, then \(d\) must satisfy

  1. \(d(x, y) \ge 0\),

  2. \(d(x, y) = 0\) if and only if \(x = y\),

  3. \(d(x, y) = d(y, x)\),

  4. \(d(x, z) \le d(x, y) + d(y, z)\).

If this argument is not specified, the Euclidean distance metric is used.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

Returns
Graph

A random Waxman graph, undirected and without self-loops. Each node has a node attribute 'pos' that stores the position of that node in Euclidean space as generated by this function.

Notes

Starting in NetworkX 2.0 the parameters alpha and beta align with their usual roles in the probability distribution. In earlier versions their positions in the expression were reversed. Their position in the calling sequence reversed as well to minimize backward incompatibility.

References

1

B. M. Waxman, Routing of multipoint connections. IEEE J. Select. Areas Commun. 6(9),(1988) 1617–1622.

Examples

Specify an alternate distance metric using the metric keyword argument. For example, to use the “taxicab metric” instead of the default Euclidean metric:

>>> dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y))
>>> G = nx.waxman_graph(10, 0.5, 0.1, metric=dist)