Warning

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

networkx.generators.directed.random_k_out_graph

random_k_out_graph(n, k, alpha, self_loops=True, seed=None)[source]

Returns a random k-out graph with preferential attachment.

A random k-out graph with preferential attachment is a multidigraph generated by the following algorithm.

  1. Begin with an empty digraph, and initially set each node to have weight alpha.
  2. Choose a node u with out-degree less than k uniformly at random.
  3. Choose a node v from with probability proportional to its weight.
  4. Add a directed edge from u to v, and increase the weight of v by one.
  5. If each node has out-degree k, halt, otherwise repeat from step 2.

For more information on this model of random graph, see [1].

Parameters:
  • n (int) – The number of nodes in the returned graph.
  • k (int) – The out-degree of each node in the returned graph.
  • alpha (float) – A positive float representing the initial weight of each vertex. A higher number means that in step 3 above, nodes will be chosen more like a true uniformly random sample, and a lower number means that nodes are more likely to be chosen as their in-degree increases. If this parameter is not positive, a ValueError is raised.
  • self_loops (bool) – If True, self-loops are allowed when generating the graph.
  • seed (int) – If provided, this is used as the seed for the random number generator.
Returns:

A k-out-regular multidigraph generated according to the above algorithm.
Return type:

MultiDiGraph
Raises:

ValueError – If alpha is not positive.

Notes

The returned multidigraph may not be strongly connected, or even weakly connected.

References

[1]: Peterson, Nicholas R., and Boris Pittel.
“Distance between two random k-out digraphs, with and without preferential attachment.” arXiv preprint arXiv:1311.5961 (2013). <https://arxiv.org/abs/1311.5961>