networkx.generators.duplication.partial_duplication_graph¶
-
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 ofN
nodes have been reached.- A random node, u, is picked and a new node, v, is created.
- For each neighbor of u an edge from the neighbor to v is created
with probability
p
. - 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
[1] 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>