random_geometric_graph¶
-
random_geometric_graph
(n, radius, dim=2, pos=None, metric=None)[source]¶ Returns a random geometric graph in the unit cube.
The random geometric graph model places
n
nodes uniformly at random in the unit cube. Two nodes are joined by an edge if the distance between the nodes is at mostradius
.Parameters: n (int or iterable) – Number of nodes or iterable of nodes
radius (float) – Distance threshold value
dim (int, optional) – Dimension of graph
pos (dict, optional) – A dictionary keyed by node with node positions as values.
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
- d*(*x, y) ≥ 0,
- d*(*x, y) = 0 if and only if x = y,
- d*(*x, y) = d*(*y, x),
- d*(*x, z) ≤ d*(*x, y) + d*(*y, z).
If this argument is not specified, the Euclidean distance metric is used.
Returns: A random geometric graph, undirected and without self-loops. Each node has a node attribute
'pos'
that stores the position of that node in Euclidean space as provided by thepos
keyword argument or, ifpos
was not provided, as generated by this function.Return type: Examples
Create a random geometric graph on twenty nodes where nodes are joined by an edge if their distance is at most 0.1:
>>> G = nx.random_geometric_graph(20, 0.1)
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.random_geometric_graph(10, 0.1, metric=dist)
Notes
This uses an
O(n^2)
algorithm to build the graph. A faster algorithm is possible using k-d trees.The
pos
keyword argument can be used to specify node positions so you can create an arbitrary distribution and domain for positions.For example, to use a 2D Gaussian distribution of node positions with mean (0, 0) and standard deviation 2:
>>> import random >>> n = 20 >>> p = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)} >>> G = nx.random_geometric_graph(n, 0.2, pos=p)
References
[1] Penrose, Mathew, Random Geometric Graphs, Oxford Studies in Probability, 5, 2003.