Warning

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

Source code for networkx.generators.geometric

# -*- coding: utf-8 -*-
"""
Generators for geometric graphs.
"""
#    Copyright (C) 2004-2015 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.

__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
                        'Dan Schult (dschult@colgate.edu)',
                        'Ben Edwards (BJEdwards@gmail.com)'])

__all__ = ['random_geometric_graph',
           'waxman_graph',
           'geographical_threshold_graph',
           'navigable_small_world_graph']

from bisect import bisect_left
from functools import reduce
from itertools import product
import math, random, sys
import networkx as nx

#---------------------------------------------------------------------------
#  Random Geometric Graphs
#---------------------------------------------------------------------------

[docs]def random_geometric_graph(n, radius, dim=2, pos=None): """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 Euclidean distance between the nodes is at most ``radius``. Parameters ---------- n : int Number 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. Returns ------- Graph 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) Notes ----- This algorithm currently only supports Euclidean distance. 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. """ G=nx.Graph() G.name="Random Geometric Graph" G.add_nodes_from(range(n)) if pos is None: # random positions for n in G: G.node[n]['pos']=[random.random() for i in range(0,dim)] else: nx.set_node_attributes(G,'pos',pos) # connect nodes within "radius" of each other # n^2 algorithm, could use a k-d tree implementation nodes = G.nodes(data=True) while nodes: u,du = nodes.pop() pu = du['pos'] for v,dv in nodes: pv = dv['pos'] d = sum(((a-b)**2 for a,b in zip(pu,pv))) if d <= radius**2: G.add_edge(u,v) return G
[docs]def geographical_threshold_graph(n, theta, alpha=2, dim=2, pos=None, weight=None): r"""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 .. math:: w_u + w_v \ge \theta r^{\alpha} where `r` is the Euclidean distance between `u` and `v`, and `\theta`, `\alpha` are parameters. Parameters ---------- n : int Number of nodes theta: float Threshold value alpha: float, optional Exponent of distance function dim : int, optional Dimension of graph pos : dict Node positions as a dictionary of tuples keyed by node. weight : dict Node weights as a dictionary of numbers keyed by node. Returns ------- Graph Examples -------- >>> G = nx.geographical_threshold_graph(20, 50) 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 """ G=nx.Graph() # add n nodes G.add_nodes_from([v for v in range(n)]) if weight is None: # choose weights from exponential distribution for n in G: G.node[n]['weight'] = random.expovariate(1.0) else: nx.set_node_attributes(G,'weight',weight) if pos is None: # random positions for n in G: G.node[n]['pos']=[random.random() for i in range(0,dim)] else: nx.set_node_attributes(G,'pos',pos) G.add_edges_from(geographical_threshold_edges(G, theta, alpha)) return G
def geographical_threshold_edges(G, theta, alpha=2): """Generates edges for a geographical threshold graph given a graph with positions and weights assigned as node attributes ``'pos'`` and ``'weight'``. """ nodes = G.nodes(data=True) while nodes: u,du = nodes.pop() wu = du['weight'] pu = du['pos'] for v,dv in nodes: wv = dv['weight'] pv = dv['pos'] r = math.sqrt(sum(((a-b)**2 for a,b in zip(pu,pv)))) if wu+wv >= theta*r**alpha: yield(u,v)
[docs]def waxman_graph(n, alpha=0.4, beta=0.1, L=None, domain=(0, 0, 1, 1)): r"""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 Euclidean distance `d` is joined by an edge with probability .. math:: 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 Number 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)`. Returns ------- G: Graph References ---------- .. [1] B. M. Waxman, Routing of multipoint connections. IEEE J. Select. Areas Commun. 6(9),(1988) 1617-1622. """ # build graph of n nodes with random positions in the unit square G = nx.Graph() G.add_nodes_from(range(n)) (xmin,ymin,xmax,ymax)=domain for n in G: G.node[n]['pos']=(xmin + ((xmax-xmin)*random.random()), ymin + ((ymax-ymin)*random.random())) if L is None: # find maximum distance L between two nodes l = 0 pos = list(nx.get_node_attributes(G,'pos').values()) while pos: x1,y1 = pos.pop() for x2,y2 in pos: r2 = (x1-x2)**2 + (y1-y2)**2 if r2 > l: l = r2 l=math.sqrt(l) else: # user specified maximum distance l = L nodes=G.nodes() if L is None: # Waxman-1 model # try all pairs, connect randomly based on euclidean distance while nodes: u = nodes.pop() x1,y1 = G.node[u]['pos'] for v in nodes: x2,y2 = G.node[v]['pos'] r = math.sqrt((x1-x2)**2 + (y1-y2)**2) if random.random() < alpha*math.exp(-r/(beta*l)): G.add_edge(u,v) else: # Waxman-2 model # try all pairs, connect randomly based on randomly chosen l while nodes: u = nodes.pop() for v in nodes: r = random.random()*l if random.random() < alpha*math.exp(-r/(beta*l)): G.add_edge(u,v) return G