5.6.2. networkx.generators.duplication.partial_duplication_graph

networkx.generators.duplication.partial_duplication_graph(N, n, p, q, seed=None)[source]

Return a random graph using the partial duplication model.

Parameters:

N : int

The total number of nodes in the final graph.

n : int

The number of nodes in the initial clique.

p : float

The probability of joining each neighbor of a node to the duplicate node. Must be a number in the between zero and one, inclusive.

q : float

The probability of joining the source node to the duplicate node. Must be a number in the between zero and one, inclusive.

seed : int, optional

Seed for random number generator (default=None).

Notes

A graph of nodes is grown by creating a fully connected graph of size n. The following procedure is then repeated until a total of N nodes have been reached.

  1. A random node, u, is picked and a new node, v, is created.
  2. For each neighbor of u an edge from the neighbor to v is created with probability p.
  3. An edge from u to v is created with probability q.

This algorithm appears in [1].

This implementation allows the possibility of generating disconnected graphs.

References

[R1024]Knudsen Michael, and Carsten Wiuf. “A Markov chain approach to randomly grown graphs.” Journal of Applied Mathematics 2008. <https://dx.doi.org/10.1155/2008/190836>