# 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?

## Answers

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 )

Finally:

all( lhs <= rhs ) [1] TRUE