vendredi 27 octobre 2023

How to generate a random directed cyclic graph with a defined "average" number of edges for each node? (in R language)

I want to generate random directed cyclic graphs while defining the number of nodes and the average number of edges for each node. By "average number of edges" i mean that the degree of each node is usually the one i define with lower chances of being lower or higher.

For example i want a DCG with 3 edges per node i will have 80% nodes with degree 3, 15% nodes with degree 2, 5% nodes with degree 1 (note: all nodes should have edges, no disconnected nodes)

I would also like to define the number of cycles in the generated DCG.

I don't know if there is something that is already implemented that does this.

I tried with igraph with the erdos.renyi.game

library(igraph)  
nodes = 20  
edges = 40  
g <- erdos.renyi.game(nodes, edges, type = "gnm",  
          directed = TRUE, loops = FALSE)  
is.dag(g) ##FALSE --> it's a Directed Cyclic Graph  
x = degree(g)  
mean(x)  
table(x)  
names(sort(-table(x)))[1]  
hist(x)  
plot(g)   

with 20 nodes and 40 edges, directed edges and no self loops, i obtain a DCG but i have 2 problems:

First, i cannot define the number of edges per node, here i tried to have a number of edges that is two times the number of nodes in hope to get an average of 2 edges per node but i end up with random degrees ranging up to nodes with degree of 8

Second, i cannot define the number of cycles or the number of nodes that define the cycle, so if i have two nodes pointing at eachother it counts as DCG. It would be better if i could define cycles that involve more than 2 nodes for the tests.




Aucun commentaire:

Enregistrer un commentaire