Generation Functions for Four Network Models in NetworkX

1. Regular graph

random_graphs.random_regular_graph(d, n)

A regular graph containing n nodes, where each node has d neighbors.

2. ER graph

random_graphs.erdos_renyi_graph(n,p)

Generates a graph containing n nodes, connecting each pair of the n nodes with probability p.

3. WS small-world model

random_graphs.watts_strogatz_graph(n, k, p)

Generates a WS small-world network containing n nodes, each having k neighbors, with edges randomly rewired with probability p.

Put simply, in a small-world network the outer ring is a circle, and then each node on the circle is randomly connected to other nodes.

This class of network models is a collective term for networks that have both a relatively short average path length and a relatively high clustering coefficient.

By adjusting a single parameter one can transition from a regular network to a random network; this model is called the WS small-world model.

Start from a ring-shaped regular network: the network contains N nodes, each node draws K edges to its K nearest neighbors, and satisfies N>>K>>ln(N)>>1.

With probability p, randomly rewire each edge in the network: keep one endpoint of the edge fixed, and choose the other endpoint as a node selected at random from the network. It is stipulated that there can be at most one edge between any two distinct nodes, and no node may have an edge connecting to itself.

This produces pNK/2 long-range edges linking a node to distant nodes. By changing the value of p, one can transition from a regular network (p=0) to a random network (p=1).

Note that the randomization process in the WS small-world model construction algorithm may destroy network connectivity; a better model needs to consider the NW small-world network model.

4. BA graph (scale-free)

random_graphs.barabasi_albert_graph(n, m)

Generates a BA scale-free network containing n nodes, adding m edges each time a node is joined.

The hallmark of a scale-free network is severe heterogeneity: the distribution of connection degrees among its nodes is severely non-uniform.

A typical example is routers: in the network, a small number of nodes called Hub nodes possess an enormous number of connections, while the vast majority of nodes have only very few.

Another example is call centers, power plants, and the like, where a few Hub nodes play a dominant role in the operation of the scale-free network.

The scale-free property of scale-free networks is an intrinsic nature that describes the severely non-uniform distribution of large complex systems as a whole.

In a scale-free network, if the central nodes are attacked, large-scale paralysis will result.