Hi, I am trying to generate a graph which the maximum degree of each nodes is four. Is there any function in ‘igraph R package’ to do this? My problem is generating a random graph which the max degree of each nodes is 4 [as in appendix image] ,and then, interpret the graph to the adjacency matrix.
Thanks you all!
Do you want to want some random graph with a maximum degree of four, or do you want the process given in the image? The image is way more specific.
For example sample_k_regular will give you a specific degree, which means it can also give you a maximum degree, but that’s only a solution if you don’t have other restrictions on the distribution of the edges in your graph.
1 Like
Thank’s. I want the process given in the image, but the max degree of each vertex must be 4 (not the max degree of whole graph).
I try the R codes as follow:
library(MASS)
library(Matrix)
library(philentropy)
library(igraph)
d=10
tmp = matrix(runif(2d, 0, 0.5), d, 2)
tmp = 2 * tmp
L = distance(tmp,method=“euclidean”)
s=0.125
prob = (1/sqrt(2pi))exp(-(L^2)/2s)
g=graph.adjacency(prob,mode=“undirected” , diag = FALSE)
theta=as_adjacency_matrix(g,type=“both”)
for(j in 1:d){
for(i in 1:d){
if(theta[i,j]==0)
omega[i,j]=0
else
omega[i,j]=0.245
}
}
diag(omega) = 1
The problem is the graph ‘g’ will be empty and the adjacency matrix ‘theta’ is always 0.
I don’t know if I can answer your question, but can you fix your formatting? That makes it easier for others to read. Now your code has no indentation and there are some <em> tags that I think shouldn’t be there. That’s why some parts are cursive. It’s probably because *'s are translated to <em>'s or something.
I’m a new user of this website, however, I’ve tried to.
Best,
Well, if you hadn’t included the image I’d say it is simple: generate a random sequence from 1:4 (or 0:4) of the desired number of vertices, and call sample_degseq, for example:
degs <- sample(1:4, 100, replace=TRUE)
head(degs)
[1] 1 3 4 3 1 3
g <- sample_degseq(degs)
summary(g)
IGRAPH 5267986 U--- 100 119 -- Degree sequence random graph
+ attr: name (g/c), method (g/c)
degree_distribution(g)
[1] 0.00 0.31 0.21 0.27 0.21
or
degs2 <- sample(0:4, 100, replace=TRUE)
g2 <- sample_degseq(degs2)
summary(g2)
IGRAPH 5249ae5 U--- 100 116 -- Degree sequence random graph
+ attr: name (g/c), method (g/c)
degree_distribution(g2)
[1] 0.17 0.13 0.22 0.17 0.31
but I’m sorry I can’t delve into the formula in the image tonight …
After some thought, a simpler solution.
require(igraph)
## HIGH-DIMENSIONAL GRAPHS AND VARIABLE SELECTION WITH THE LASSO.
## Nicolai Meinshausen, Peter Bühlmann
## https://arxiv.org/abs/math/0608017v1.
## probability function in 6.1 Neighborhood Graphs.
d <- 10L # X = (X1 .. Xd), number of vertices.
s <- 0.125 # controls sparsity level.
max_deg <- 4L # max number of parallel edges.
magic <- 0.245
## Build the square of euclidean distance matrix.
## Euclidian norm squared == Pythagoras.
set.seed(d)
Y1 <- runif(d, min=0, max=1)
Y2 <- runif(d, min=0, max=1)
Edist2 <- outer(Y1, Y1, "-")^2 + outer(Y2, Y2, "-")^2
mean(Edist2)
## Apply Lasso probability formula and
## clear lower triangle + diag.
lasso_prob <- exp(-Edist2 / (2*s)) / sqrt(2*pi)
lasso_prob[upper.tri(lasso_prob, diag = TRUE)] <- NA
mean(lasso_prob, na.rm=TRUE)
## Add edges with probability lasso_prob.
g_adj <- (lasso_prob > runif(d*d))
g_adj <- (g_adj | t(g_adj)) * 1L
g <- graph_from_adjacency_matrix(g_adj, mode = "undirected", diag = FALSE)
## Achieve the desired sparsity of the graph.
## From vertices with degree > 4, remove any incident edge,
## until no vertex left with degree > 4.
g2 <- g
while (max(degree(g2)) > max_deg) {
vvv <- V(g2)[which(degree(g2) > max_deg)]
g2 <- g2 - sample(incident(g2, vvv), 1)
}
degree(g2)
dev.new(); plot(g2, layout=layout_in_circle)
## Build inverse covariant matrix.
Omega_0 <- matrix(0, nrow=d, ncol=d)
Omega_0[which(g_adj > 0)] <- 1/max_deg
diag(Omega_0) <- 1
print.table(Omega_0, zero.print = ".")
Cross posted at Stackoverflow, Generate an undirected graph by probability on edges in R.