Abstract:

With the development of the study of complex networks, random graphs become an important model in complex networks. On the basis of spanned subgraphs of complete graphs, a new algorithm of generating random graphs is proposed by means of removing the edges of a complete graph. It is verified by numerical experiments that the statistical properties (maximum degree, minimum degree, clustering coefficient, average shortest path and the average degree) of the random graphs generated by increasing or removing the edges are similar to each other. The degree distribution of these graphs obtained by removing edges reaches the peak at the average degree and then turns to decay exponentially. This is the same as the degree distribution of random graphs. In order to get the sparse connective random graphs, an approximate random graph generation algorithm without removing cutting edge is proposed. And it is theoretically explained that the generated graphs are connected ones. Meanwhile, numerical experiments are carried out to verify that the generated graphs are connected, and the comparison of statistical properties is made with the random graphs generated by increasing the edges.

Key words: random graph;complete graph;spanned subgraph;complex networks;connectivity;algorithm