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

Need Your Help

Cannot install RealVNC viewer on RHEL 6

64-bit vnc viewer rhel6

I am trying to install RealVNC viewer on my RHEL6 server (kernel 2.6.32-71.el6.x86_64). When I ran the RPM, I got the error

Does Java allow nullable types?

java syntax null

In C# I can a variable to allow nulls with the question mark. I want to have a true/false/null result. I want to have it set to null by default. The boolean will be set to true/false by a test resu...