Necesito generar una matriz binaria aleatoria $(n, n)$ cuyas sumas de filas y columnas son $4$ .
No consigo encontrar un algoritmo bastante eficiente para hacer esto. ¿Tienes alguna idea, por favor?
NB : La distribución debe ser uniforme.
Respuestas
¿Demasiados anuncios?
No soy un experto en teoría de grafos y he probado un método directo. Primero, genero una matriz con el número correcto de unos en las filas; luego, arreglo las columnas.
bin <- function(n=6,k=4){ # creates a matrix w 4 ones in every row and col
A <- matrix(0,n,n) # 0 matrix
for(i in 1:n){
pos <- sample(1:n,k) # sample k positions in i-th row
A[i,pos] <- 1 # and set them to 1
}
# sumrows is now ok
sumcol <- apply(A,2,sum)
missing <- pmax(0,k-sumcol) # vector of n component, how many ones miss for each col
excess <- pmax(0,sumcol-k) # vector of n component, how many ones miss for each col
cat(sum(missing)," ",sum(excess),"\n")
#
# main idea
# pick a random column with a missing one (r) and a random row with an excess one (s)
# swap randomly a one in s-th columns with a zero in r-th column
# till matrix is ok (i.e., no columns has less than k ones)
while(sum(missing)>0){
rr <- which(excess>0)
ss <- which(missing>0)
r <- if(length(rr)==1) rr else sample(rr,1)
s <- if(length(ss)==1) ss else sample(ss,1)
ex <- which(A[,r]==1 & A[,s]==0)
j <- if(length(ex)==1) ex else sample(ex,1)
A[j,s] <- 1;A[j,r] <-0
sumcol <- apply(A,2,sum)
missing <- pmax(0,k-sumcol)
excess <- pmax(0,sumcol-k)
}
# sumcolumns is now ok
A
}rr (ss) son vectores con los índices de las columnas con unos perdidos (exceso). r y s son extracciones aleatorias de rr y ss. debe haber al menos una forma de intercambiar aleatoriamente un uno con un cero en las columnas r y s. Las sentencias if se deben al comportamiento de sample en R: sample(3,1) muestrea 1 elemento de 1:3, y no proporciona 3. De ahí que compruebe su longitud.
10 matrices con n=200 y k=100 se generan en unos 10 segundos en mi AirBook y cada matriz requiere una media de 110 correcciones (de 100*100=10000 entradas).
Todavía no estoy familiarizado con el editor, pula mi texto si lo desea. Espero que esto ayude.
Brian Rushton
Puntos
10407
Ampliando la respuesta de Joriki, puedes usar el algoritmo enhttp://www.columbia.edu/~mo2291/Publications/DirectedRandomGraphs_29Jan13.pdf en la página 7 u 8 para crear un grafo dirigido con grado fuera 4 y grado I 4 en cada vértice, con posibles auto-bucles y aristas múltiples. Luego se pueden excluir los que tienen aristas múltiples. La matriz de adyacencia dirigida (un uno en la posición i,j significa que hay una arista del vértice i al j) te da lo que necesitas.
El algoritmo se reduce básicamente a sumar cuatro matrices de permutación aleatorias y cambiar las matrices si se obtiene un 2 o más en alguna entrada. Esto es más eficiente cuanto más grande $n$ es.
