geographical_threshold_graph¶
- geographical_threshold_graph(n, theta, dim=2, pos=None, weight=None, metric=None, p_dist=None, seed=None)[source]¶
Returns a geographical threshold graph.
The geographical threshold graph model places \(n\) nodes uniformly at random in a rectangular domain. Each node \(u\) is assigned a weight \(w_u\). Two nodes \(u\) and \(v\) are joined by an edge if
\[(w_u + w_v)p_{dist}(r) \ge \theta\]where
r
is the distance betweenu
andv
,p_dist
is any function ofr
, and \(\theta\) as the threshold parameter.p_dist
is used to give weight to the distance between nodes when deciding whether or not they should be connected. The largerp_dist
is, the more prone nodes separated byr
are to be connected, and vice versa.- Parameters
- nint or iterable
Number of nodes or iterable of nodes
- theta: float
Threshold value
- dimint, optional
Dimension of graph
- posdict
Node positions as a dictionary of tuples keyed by node.
- weightdict
Node weights as a dictionary of numbers keyed by node.
- 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
\(d(x, y) \ge 0\),
\(d(x, y) = 0\) if and only if \(x = y\),
\(d(x, y) = d(y, x)\),
\(d(x, z) \le d(x, y) + d(y, z)\).
If this argument is not specified, the Euclidean distance metric is used.
- p_distfunction, optional
Any function used to give weight to the distance between nodes when deciding whether or not they should be connected.
p_dist
was originally conceived as a probability density function giving the probability of connecting two nodes that are of metric distancer
apart. The implementation here allows for more arbitrary definitions ofp_dist
that do not need to correspond to valid probability density functions. Thescipy.stats
package has many probability density functions implemented and tools for custom probability density definitions, and passing the.pdf
method of scipy.stats distributions can be used here. Ifp_dist=None
(the default), the exponential function \(r^{-2}\) is used.- seedinteger, random_state, or None (default)
Indicator of random number generation state. See Randomness.
- Returns
- Graph
A random geographic threshold 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. Similarly, each node has a node attributeweight
that stores the weight of that node as provided or as generated.
Notes
If weights are not specified they are assigned to nodes by drawing randomly from the exponential distribution with rate parameter \(\lambda=1\). To specify weights from a different distribution, use the
weight
keyword argument:>>> import random >>> n = 20 >>> w = {i: random.expovariate(5.0) for i in range(n)} >>> G = nx.geographical_threshold_graph(20, 50, weight=w)
If node positions are not specified they are randomly assigned from the uniform distribution.
References
- 1
Masuda, N., Miwa, H., Konno, N.: Geographical threshold graphs with small-world and scale-free properties. Physical Review E 71, 036108 (2005)
- 2
Milan Bradonjić, Aric Hagberg and Allon G. Percus, Giant component and connectivity in geographical threshold graphs, in Algorithms and Models for the Web-Graph (WAW 2007), Antony Bonato and Fan Chung (Eds), pp. 209–216, 2007
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.geographical_threshold_graph(10, 0.1, metric=dist)