waxman_graph

waxman_graph(n, alpha=0.4, beta=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 = \alpha \exp(-d / \beta 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

  • alpha (float) – Model parameter

  • beta (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) ≥ 0,
    2. d*(*x, y) = 0 if and only if x = y,
    3. d*(*x, y) = d*(*y, x),
    4. d*(*x, z) ≤ 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)

References

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