source: networkx/networkx/generators/geometric.py @ 1711:e48e5bb50cf0

Revision 1711:e48e5bb50cf0, 11.2 KB checked in by Aric Hagberg <aric.hagberg@…>, 3 years ago (diff)

Small documentation fixes. Remove :math: role tag.

Line 
1# -*- coding: utf-8 -*-
2"""
3Generators for geometric graphs.
4"""
5#    Copyright (C) 2004-2011 by
6#    Aric Hagberg <hagberg@lanl.gov>
7#    Dan Schult <dschult@colgate.edu>
8#    Pieter Swart <swart@lanl.gov>
9#    All rights reserved.
10#    BSD license.
11
12from __future__ import print_function
13
14__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
15                        'Dan Schult (dschult@colgate.edu)',
16                        'Ben Edwards (BJEdwards@gmail.com)'])
17
18__all__ = ['random_geometric_graph',
19           'waxman_graph',
20           'geographical_threshold_graph',
21           'navigable_small_world_graph']
22
23from bisect import bisect_left
24from functools import reduce
25from itertools import product
26import math, random, sys
27import networkx as nx
28
29#---------------------------------------------------------------------------
30#  Random Geometric Graphs
31#---------------------------------------------------------------------------
32       
33def random_geometric_graph(n, radius, dim=2, pos=None):
34    r"""Return the random geometric graph in the unit cube.
35
36    The random geometric graph model places n nodes uniformly at random
37    in the unit cube  Two nodes `u,v` are connected with an edge if
38    `d(u,v)<=r` where `d` is the Euclidean distance and `r` is a radius
39    threshold.
40
41    Parameters
42    ----------
43    n : int
44        Number of nodes
45    radius: float
46        Distance threshold value 
47    dim : int, optional
48        Dimension of graph
49    pos : dict, optional
50        A dictionary keyed by node with node positions as values.
51
52    Returns
53    -------
54    Graph
55     
56    Examples
57    --------
58    >>> G = nx.random_geometric_graph(20,0.1)
59
60    Notes
61    -----
62    This uses an `n^2` algorithm to build the graph.  A faster algorithm
63    is possible using k-d trees.
64
65    The pos keyword can be used to specify node positions so you can create
66    an arbitrary distribution and domain for positions.  If you need a distance
67    function other than Euclidean you'll have to hack the algorithm.
68
69    E.g to use a 2d Gaussian distribution of node positions with mean (0,0)
70    and std. dev. 2
71
72    >>> import random
73    >>> n=20
74    >>> p=dict((i,(random.gauss(0,2),random.gauss(0,2))) for i in range(n))
75    >>> G = nx.random_geometric_graph(n,0.2,pos=p)
76
77    References
78    ----------
79    .. [1] Penrose, Mathew, Random Geometric Graphs,
80       Oxford Studies in Probability, 5, 2003.
81    """
82    G=nx.Graph()
83    G.name="Random Geometric Graph"
84    G.add_nodes_from(range(n)) 
85    if pos is None:
86        # random positions
87        for n in G:
88            G.node[n]['pos']=[random.random() for i in range(0,dim)]
89    else:
90        nx.set_node_attributes(G,'pos',pos)
91    # connect nodes within "radius" of each other
92    # n^2 algorithm, could use a k-d tree implementation
93    nodes = G.nodes(data=True)
94    while nodes:
95        u,du = nodes.pop()
96        pu = du['pos']
97        for v,dv in nodes:
98            pv = dv['pos']
99            d = sum(((a-b)**2 for a,b in zip(pu,pv)))
100            if d <= radius**2:
101                G.add_edge(u,v)
102    return G
103
104def geographical_threshold_graph(n, theta, alpha=2, dim=2, 
105                                 pos=None, weight=None):
106    r"""Return a geographical threshold graph.
107
108    The geographical threshold graph model places n nodes uniformly at random
109    in a rectangular domain.  Each node `u` is assigned a weight `w_u`.
110    Two nodes `u,v` are connected with an edge if
111
112    .. math::
113
114       w_u + w_v \ge \theta r^{\alpha}
115
116    where `r` is the Euclidean distance between `u` and `v`,
117    and `\theta`, `\alpha` are parameters.
118
119    Parameters
120    ----------
121    n : int
122        Number of nodes
123    theta: float
124        Threshold value
125    alpha: float, optional
126        Exponent of distance function
127    dim : int, optional
128        Dimension of graph
129    pos : dict
130        Node positions as a dictionary of tuples keyed by node.
131    weight : dict
132        Node weights as a dictionary of numbers keyed by node.
133
134    Returns
135    -------
136    Graph
137     
138    Examples
139    --------
140    >>> G = nx.geographical_threshold_graph(20,50)
141
142    Notes
143    -----
144    If weights are not specified they are assigned to nodes by drawing randomly
145    from an the exponential distribution with rate parameter `\lambda=1`.
146    To specify a weights from a different distribution assign them to a
147    dictionary and pass it as the weight= keyword
148
149    >>> import random
150    >>> n = 20
151    >>> w=dict((i,random.expovariate(5.0)) for i in range(n))
152    >>> G = nx.geographical_threshold_graph(20,50,weight=w)
153   
154    If node positions are not specified they are randomly assigned from the
155    uniform distribution.
156
157    References
158    ----------
159    .. [1] Masuda, N., Miwa, H., Konno, N.:
160       Geographical threshold graphs with small-world and scale-free properties.
161       Physical Review E 71, 036108 (2005)
162    .. [2]  Milan Bradonjić, Aric Hagberg and Allon G. Percus,
163       Giant component and connectivity in geographical threshold graphs,
164       in Algorithms and Models for the Web-Graph (WAW 2007),
165       Antony Bonato and Fan Chung (Eds), pp. 209--216, 2007
166    """
167    G=nx.Graph()
168    # add n nodes
169    G.add_nodes_from([v for v in range(n)]) 
170    if weight is None:
171        # choose weights from exponential distribution
172        for n in G:
173            G.node[n]['weight'] = random.expovariate(1.0)
174    else:
175        nx.set_node_attributes(G,'weight',weight)
176    if pos is None:
177        # random positions
178        for n in G:
179            G.node[n]['pos']=[random.random() for i in range(0,dim)]
180    else:
181        nx.set_node_attributes(G,'pos',pos)
182    G.add_edges_from(geographical_threshold_edges(G, theta, alpha))
183    return G
184
185def geographical_threshold_edges(G, theta, alpha=2):
186    # generate edges for a geographical threshold graph given a graph
187    # with positions and weights assigned as node attributes 'pos' and 'weight'.
188    nodes = G.nodes(data=True)
189    while nodes:
190        u,du = nodes.pop()
191        wu = du['weight']
192        pu = du['pos']
193        for v,dv in nodes:
194            wv = dv['weight']
195            pv = dv['pos']
196            r = math.sqrt(sum(((a-b)**2 for a,b in zip(pu,pv))))
197            if wu+wv >= theta*r**alpha:
198                yield(u,v)
199
200def waxman_graph(n, alpha=0.4, beta=0.1, L=None, domain=(0,0,1,1)):
201    r"""Return a Waxman random graph.
202
203    The Waxman random graph models place n nodes uniformly at random
204    in a rectangular domain. Two nodes u,v are connected with an edge
205    with probability
206
207    .. math::
208            p = \alpha*exp(d/(\beta*L)).
209
210    This function implements both Waxman models.           
211
212    Waxman-1:  `L` not specified
213       The distance `d` is the Euclidean distance between the nodes u and v.
214       `L` is the maximum distance between all nodes in the graph.
215
216    Waxman-2: `L` specified
217       The distance `d` is chosen randomly in `[0,L]`.
218
219    Parameters
220    ----------
221    n : int
222        Number of nodes
223    alpha: float
224        Model parameter
225    beta: float
226        Model parameter
227    L : float, optional
228        Maximum distance between nodes.  If not specified the actual distance
229        is calculated.
230    domain : tuple of numbers, optional
231         Domain size (xmin, ymin, xmax, ymax)
232
233    Returns
234    -------
235    G: Graph
236
237    References
238    ----------
239    .. [1]  B. M. Waxman, Routing of multipoint connections.
240       IEEE J. Select. Areas Commun. 6(9),(1988) 1617-1622.
241    """
242    # build graph of n nodes with random positions in the unit square
243    G = nx.Graph()
244    G.add_nodes_from(range(n))
245    (xmin,ymin,xmax,ymax)=domain
246    for n in G:
247        G.node[n]['pos']=((xmin + (xmax-xmin))*random.random(),
248                          (ymin + (ymax-ymin))*random.random())
249    if L is None:
250        # find maximum distance L between two nodes
251        l = 0
252        pos = list(nx.get_node_attributes(G,'pos').values())
253        while pos:
254            x1,y1 = pos.pop()
255            for x2,y2 in pos:
256                r2 = (x1-x2)**2 + (y1-y2)**2
257                if r2 > l:
258                    l = r2
259        l=math.sqrt(l)
260    else: 
261        # user specified maximum distance
262        l = L
263
264    nodes=G.nodes()
265    if L is None:
266        # Waxman-1 model
267        # try all pairs, connect randomly based on euclidean distance
268        while nodes:
269            u = nodes.pop()
270            x1,y1 = G.node[u]['pos']
271            for v in nodes:
272                x2,y2 = G.node[v]['pos']
273                r = math.sqrt((x1-x2)**2 + (y1-y2)**2)
274                if random.random() < alpha*math.exp(-r/(beta*l)):
275                    G.add_edge(u,v)
276    else:
277        # Waxman-2 model
278        # try all pairs, connect randomly based on randomly chosen l
279        while nodes:
280            u = nodes.pop()
281            for v in nodes:
282                r = random.random()*l
283                if random.random() < alpha*math.exp(-r/(beta*l)):
284                    G.add_edge(u,v)
285    return G
286
287
288def navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None):
289    r"""Return a navigable small-world graph.
290
291    A navigable small-world graph is a directed grid with additional
292    long-range connections that are chosen randomly.  From [1]_:
293
294    Begin with a set of nodes that are identified with the set of lattice
295    points in an `n \times n` square, `{(i,j): i\in {1,2,\ldots,n}, j\in {1,2,\ldots,n}}`
296    and define the lattice distance between two nodes `(i,j)` and `(k,l)`
297    to be the number of "lattice steps" separating them: `d((i,j),(k,l)) = |k-i|+|l-j|`. 
298
299    For a universal constant `p`, the node `u` has a directed edge to every other
300    node within lattice distance `p` (local contacts) .
301
302    For universal constants `q\ge 0` and `r\ge 0` construct directed edges from `u` to `q`
303    other nodes (long-range contacts) using independent random trials;  the i'th
304    directed edge from `u` has endpoint `v` with probability proportional to `d(u,v)^{-r}`.
305
306    Parameters
307    ----------
308    n : int
309        The number of nodes.
310    p : int
311        The diameter of short range connections. Each node is connected
312        to every other node within lattice distance p.
313    q : int
314        The number of long-range connections for each node.
315    r : float
316        Exponent for decaying probability of connections.  The probability of
317        connecting to a node at lattice distance d is 1/d^r.
318    dim : int
319        Dimension of grid
320    seed : int, optional
321        Seed for random number generator (default=None).
322     
323    References
324    ----------
325    .. [1] J. Kleinberg. The small-world phenomenon: An algorithmic
326       perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
327    """
328    if (p < 1):
329        raise nx.NetworkXException("p must be >= 1")
330    if (q < 0):
331        raise nx.NetworkXException("q must be >= 0")
332    if (r < 0):
333        raise nx.NetworkXException("r must be >= 1")
334    if not seed is None:
335        random.seed(seed)
336    G = nx.DiGraph()
337    nodes = list(product(range(n),repeat=dim))
338    for p1 in nodes:
339        probs = [0]
340        for p2 in nodes:
341            if p1==p2:
342                continue
343            d = sum((abs(b-a) for a,b in zip(p1,p2)))
344            if d <= p:
345                G.add_edge(p1,p2)
346            probs.append(d**-r)
347        cdf = list(nx.utils.cumulative_sum(probs))
348        for _ in range(q):
349            target = nodes[bisect_left(cdf,random.uniform(0, cdf[-1]))]
350            G.add_edge(p1,target)
351    return G
352 
Note: See TracBrowser for help on using the repository browser.