What are the generating methods and characteristics of machine learning Erdos Renyi random graph?

Most people do not understand the knowledge points of this article "Machine Learning Erdos Renyi random graph generation methods and characteristics", so the editor summarizes the following contents, detailed contents, clear steps, and has a certain reference value. I hope you can get something after reading this article. Let's take a look at this "Machine Learning Erdos Renyi random graph generation methods and characteristics are what" article.

1 Random Graph Generation introduction 1.1Gnp and Gnm

1.2 Generation method

1.3 comparison of the two methods

2 Gnp Random figure 2.1 is n and p enough?

N and p do not completely determine a graph. We find that even given n and p, graphs have many implementations. For example, when nasty 10 is paired 1apace 6, the following picture may be produced:

2.2 Graph properties of Gnp

The discrete distribution image of the binomial distribution is shown in the following figure:

When n is large enough, the binomial distribution can be approximated by normal distribution.

Clustering coefficient

We set up

Connected component

The graph structure of the figure Gnp changes with p, as shown in the following figure:

According to the simulation experiment, in Gnp, when the average degree is greater than 1, the huge connected component happens to appear.

Average shortest path length

Even if the Erdos-Renyi random graph is extended to a large size, it can still guarantee a distance of only a few hops (hops) between nodes. The following is a graph showing the variation of the average shortest path length h "h" with the number of nodes.

It can be seen that the average shortest path length h increases with the number of nodes n and satisfies the growth order of O (logn).

2.3 comparison between real network and Gnp

Similarity: there are large connectivity components, average shortest path length

Differences: clustering coefficient, degree distribution

In practical application, the random graph model may have the following problems:

The degree distribution may be different from the real network, which is not random after all.

The occurrence of large connected components in real networks may not be regular.

There may be no local clustering structure, so the clustering coefficient is too small.

3 code base

NetworkX has built-in functions for generating Erdos-Renyi random graphs, including Gnp and Gnm. It is important to note that Gnp's API [6] is

Erdos_renyi_graph (n, p, seed=None, directed=False)

The function of this API is the same as that of nx.binomial_graph and nx.gnp_random_graph.

And GnmGnm's API [7] is

Nm_random_graph (n, m, seed=seed, directed=False)

Therefore, we should pay attention to the distinction in practical use.

The above is about the content of this article on "what are the methods and characteristics of generating random graphs in machine learning Erdos Renyi". I believe we all have a certain understanding. I hope the content shared by the editor will be helpful to you. If you want to know more related knowledge, please pay attention to the industry information channel.