Generating undirected network with pre-specified degree distribution without any self loops
I would like to generate an undirected network with 100 nodes, where half of the nodes have a degree of 10 and the other half has a degree of 3. Is such a network possible to construct without self loops?
Using the code specified below:
library(graph) degrees=c(rep(3,50),rep(10,50)) names(degrees)=paste("node",seq_along(degrees)) #nodes must be names x=randomNodeGraph(degrees)
I can obtain such a graph, but there are self-loops included.
Is there any way to get a graph without self loops?
It is easy to do with the graph package from Bioconductor (see here)
#install graph from Bioconductor source("http://bioconductor.org/biocLite.R") biocLite("graph") #load graph and make the specified graph library(graph) degrees=c(rep(3,50),rep(10,50)) names(degrees)=paste("node",seq_along(degrees)) #nodes must be names x=randomNodeGraph(degrees) #verify graph edges=edgeMatrix(x) edgecount=table(as.vector(edges)) table(edgecount) #edgecount # 3 10 #50 50
The Erdős–Gallai theorem answers the question if such a graph is possible to construct.
It is based on the non-decreasing degree sequence of your graph which is in your case
ds <- c( rep( 10, 50 ), rep(3,50) )
You can calculate the right-hand side of the inequality by
rhs <- (1:100 * 0:99) + c( rev(cumsum(rev(apply( data.frame(ds, 1:100) , 1, min ))))[-1], 0 )
And the left-hand side by
lhs <- cumsum( ds )
all( lhs <= rhs )  TRUE