Warning

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

networkx.generators.geometric.waxman_graph

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

Return 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:
  • n (int or iterable) – Number of nodes or iterable of nodes

  • beta (float) – Model parameter

  • alpha (float) – Model parameter

  • L (float, optional) – Maximum distance between nodes. If not specified, the actual distance is calculated.

  • domain (four-tuple of numbers, optional) – Domain size, given as a tuple of the form (x_min, y_min, x_max, y_max).

  • metric (function) – 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.

Returns:

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.

Return type:

Graph

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)

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