Package networkx :: Package generators :: Module random_graphs

[frames | no frames]

## Module networkx.generators.random_graphs

Generators for random graphs

Function Summary
| ``barabasi_albert_graph`(n, m, seed)` Return random graph using Barabasi-Albert preferential attachment model.
| ``binomial_graph`(n, p, seed)` Return a binomial random graph G_{n,p}.
| ``erdos_renyi_graph`(n, m, seed)` Return the Erdos-Renyi random graph G_{n,m}.
| ``newman_watts_strogatz_graph`(n, k, p, seed)` Return a Newman-Watts-Strogatz small world graph.
| ``powerlaw_cluster_graph`(n, m, p, seed)` Holme and Kim algorithm for growing graphs with powerlaw degree distribution and approximate average clustering.
| ``random_lobster`(n, p1, p2, seed)` Return a random lobster.
| ``random_powerlaw_tree`(n, gamma, seed, tries)` Return a tree with a powerlaw degree distribution.
| ``random_powerlaw_tree_sequence`(n, gamma, seed, tries)` Return a degree sequence for a tree with a powerlaw distribution.
| ``random_regular_graph`(d, n, seed)` Return a random regular graph of n nodes each with degree d, G_{n,d}.
| ``random_shell_graph`(constructor, seed)` Return a random shell graph for the constructor given.
| ``watts_strogatz_graph`(n, k, p, seed)` Return a Watts-Strogatz small world graph.

Variable Summary
`str` | `__author__` = `'Aric Hagberg (hagberg@lanl.gov)\nPieter Sw...`
`str` | `__credits__` = `''`
`str` | `__date__` = `'$Date: 2005-06-17 08:06:22 -0600 (Fri, 17 Ju...`
`str` | `__revision__` = `'$Revision: 1049 $'`

Function Details

### barabasi_albert_graph(n, m, seed=None)

Return random graph using Barabasi-Albert preferential attachment model.

A graph of n nodes is grown by attaching new nodes each with m edges that are preferentially attached to existing nodes with high degree.

The initialization is a graph with with m nodes.

Reference:

    @ARTICLE{barabasi-1999-emergence,
    TITLE = {Emergence of scaling in random networks},
    AUTHOR = {A. L. Barabasi and R. Albert},
    JOURNAL = {SCIENCE},
    VOLUME = {286},
    NUMBER = {5439},
    PAGES = {509 -- 512},
    MONTH = {OCT},
    YEAR = {1999},
    }

  Parameters:
    `n` -

    the number of nodes

    `m` -

    average degree and must be an positive integer

    `seed` -

    seed for random number generator (default=None)

### binomial_graph(n, p, seed=None)

Return a binomial random graph G_{n,p}.

  Parameters:
    `n` -

    the number of nodes

    `p` -

    probability that any given edge exist

    `seed` -

    seed for random number generator (default=None)

### erdos_renyi_graph(n, m, seed=None)

Return the Erdos-Renyi random graph G_{n,m}.

  Parameters:
    `n` -

    the number of nodes

    `m` -

    the number of edges

    `seed` -

    seed for random number generator (default=None)

### newman_watts_strogatz_graph(n, k, p, seed=None)

Return a Newman-Watts-Strogatz small world graph.

The graph is a ring with k neighbors with new edges (shortcuts) added randomly with probability p for each edge. No edges are removed.

  Parameters:
    `n` -

    the number of nodes

    `k` -

    each vertex is connected to k neighbors in the circular topology

    `p` -

    the probability of adding a new edge for each edge

    `seed` -

    seed for random number generator (default=None)

### powerlaw_cluster_graph(n, m, p, seed=None)

Holme and Kim algorithm for growing graphs with powerlaw degree distribution and approximate average clustering.

Reference:

    @Article{growing-holme-2002,
    author =          {P. Holme and B. J. Kim},
    title =   {Growing scale-free networks with tunable clustering},
    journal =         {Phys. Rev. E},
    year =    {2002},
    volume =          {65},
    number =          {2},
    pages =   {026107},
    }

The average clustering has a hard time getting above a certain cutoff that depends on m. This cutoff is often quite low.

It is essentially the Barabasi-Albert growth model with an extra step that each random edge is followed by a chance of making an edge to one of its neighbors too (and thus a triangle).

This algorithm improves on B-A in the sense that it enables a higher average clustering to be attained if desired. The largest average clustering seems to be independent of n and attained with m=1 and p=1 (cc=0.74 or so).

  Parameters:
    `n` -

    the number of nodes

    `m` -

    the number of random edges to add for each new node

    `p` -

    probability of adding a triangle after adding a random edge

    `seed` -

    seed for random number generator (default=None)

### random_lobster(n, p1, p2, seed=None)

Return a random lobster.

> A caterpillar is a tree that reduces to a path graph when pruning all leave nodes. A lobster is a tree that reduces to a caterpillar when pruning all leave nodes.

  Parameters:
    `n` -

    the expected number of nodes in the backbone

    `p1` -

    probability of adding an edge to the backbone

    `p2` -

    probability of adding an edge one level beyond backbone

    `seed` -

    seed for random number generator (default=None)

### random_powerlaw_tree(n, gamma=3, seed=None, tries=100)

Return a tree with a powerlaw degree distribution.

A trial powerlaw degree sequence is chosen and then elements are swapped with new elements from a powerlaw distribution until the sequence makes a tree (#edges=#nodes-1).

  Parameters:
    `n` -

    the number of nodes

    `gamma` -

    exponent of power law is gamma

    `seed` -

    seed for random number generator (default=None)

    `tries` -

    number of attempts to adjust sequence to make a tree

### random_powerlaw_tree_sequence(n, gamma=3, seed=None, tries=100)

Return a degree sequence for a tree with a powerlaw distribution.

A trial powerlaw degree sequence is chosen and then elements are swapped with new elements from a powerlaw distribution until the sequence makes a tree (#edges=#nodes-1).

  Parameters:
    `n` -

    the number of nodes

    `gamma` -

    exponent of power law is gamma

    `seed` -

    seed for random number generator (default=None)

    `tries` -

    number of attempts to adjust sequence to make a tree

### random_regular_graph(d, n, seed=None)

Return a random regular graph of n nodes each with degree d, G_{n,d}. Return False if unsuccessful.

n*d must be even

Nodes are numbered 0...n-1. To get a uniform sample from the space of random graphs you should chose d<n^{1/3}. . For algorith see Kim and Vu's paper.

Reference:

    @inproceedings{kim-2003-generating,
    author = {Jeong Han Kim and Van H. Vu},
    title = {Generating random regular graphs},
    booktitle = {Proceedings of the thirty-fifth ACM symposium on Theory of computing},
    year = {2003},
    isbn = {1-58113-674-9},
    pages = {213--222},
    location = {San Diego, CA, USA},
    doi = {http://doi.acm.org/10.1145/780542.780576},
    publisher = {ACM Press},
    }

The algorithm is based on an earlier paper:

    @misc{ steger-1999-generating,
    author = "A. Steger and N. Wormald",
    title = "Generating random regular graphs quickly",
    text = "Probability and Computing 8 (1999), 377-396.",
    year = "1999",
    url = "citeseer.ist.psu.edu/steger99generating.html",
    }

### random_shell_graph(constructor, seed=None)

Return a random shell graph for the constructor given.

> - constructor: a list of three-tuples [(n1,m1,d1),(n2,m2,d2),..] one for each shell, starting at the center shell.

> - n : the number of nodes in the shell

> - m : the number or edges in the shell

> - d : the ratio of inter (next) shell edges to intra shell edges.

>     d=0 means no intra shell edges. d=1 for the last shell

> - `seed`: seed for random number generator (default=None)

    >>> constructor=[(10,20,0.8),(20,40,0.8)]
    >>> G=random_shell_graph(constructor)

### watts_strogatz_graph(n, k, p, seed=None)

Return a Watts-Strogatz small world graph.

The graph is a ring with k neighbors with edges rewired randomly with probability p.

  Parameters:
    `n` -

    the number of nodes

    `k` -

    each vertex is connected to k neighbors in the circular topology

    `p` -

    the probability of rewiring an edge

    `seed` -

    seed for random number generator (default=None)

Variable Details

### __author__

  Type:
    `str`
  Value:

        '''Aric Hagberg (hagberg@lanl.gov)
        Pieter Swart (swart@lanl.gov)
        Dan Schult(dschult@colgate.edu)'''

### __credits__

  Type:
    `str`
  Value:

        ''

### __date__

  Type:
    `str`
  Value:

        '$Date: 2005-06-17 08:06:22 -0600 (Fri, 17 Jun 2005) $'

### __revision__

  Type:
    `str`
  Value:

        '$Revision: 1049 $'

Generated by Epydoc 2.1 on Sun Aug 21 08:06:58 2005 | http://epydoc.sf.net