zweiter Ordnung Nachbarn von Graph Knoten in R

Question

Ich bin auf der Suche nach einem effizienten Weg, um die Nachbarschaften der genauen Grad aller Knoten in einem großen Graphen zu finden. Auch wenn es Graphen als schwach besetzte Matrizen, igraph::ego explodiert speichert:

require(Matrix) 
require(igraph) 
require(ggplot2) 

N <- 10^(1:5) 
runtimes <- function(N) { 
    g <- erdos.renyi.game(N, 1/N) 
    system.time(ego(g, 2, mindist = 2))[3] 
} 
runtime <- sapply(N, runtimes) 
qplot(log10(N), runtime, geom = "line") 

Gibt es eine effizientere Art und Weise?

Answer 1

Die direkte Verwendung von Adjazenzmatrizen bietet eine signifikante Verbesserung.

# sparse adjacency-matrix calculation of indirect neighbors ------------------- 

diff_sparse_mat <- function(A, B) { 
    # Difference between sparse matrices. 
    # Input: sparse matrices A and B 
    # Output: C = (A & !B), using element-wise diffing, treating B as logical 
    stopifnot(identical(dim(A), dim(B))) 
    A <- as(A, "generalMatrix") 
    AT <- as.data.table(summary(as(A, "TsparseMatrix"))) 
    setkeyv(AT, c("i", "j")) 
    B <- drop0(B) 
    B <- as(B, "generalMatrix") 
    BT <- as.data.table(summary(as(B, "TsparseMatrix"))) 
    setkeyv(BT, c("i", "j")) 
    C <- AT[!BT] 
    if (length(C) == 2) { 
    return(sparseMatrix(i = C$i, j = C$j, dims = dim(A))) 
    } else { 
    return(sparseMatrix(i = C$i, j = C$j, x = C$x, dims = dim(A))) 
    } 
} 

distance2_peers <- function(adj_mat) { 
    # Returns a matrix of indirect neighbors, excluding the diagonal 
    # Input: adjacency matrix A (assumed symmetric) 
    # Output: (A %*% A & !A) with zero diagonal 
    indirect <- forceSymmetric(adj_mat %*% adj_mat) 
    indirect <- diff_sparse_mat(indirect, adj_mat) # excl. direct neighbors 
    indirect <- diff_sparse_mat(indirect, Diagonal(n = dim(indirect)[1])) # excl. diag. 
    return(indirect) 
}  

für die Erdos RENYI Beispiel in einer halben Minute nun ein Netz von 10^7, nicht mehr als 10^5 analysiert werden:

N <- 10^(1:7) 
runtimes <- function(N) { 
    g <- erdos.renyi.game(N, 1/N, directed = FALSE) 
    system.time(distance2_peers(as_adjacency_matrix(g)))[3] 
} 
runtime <- sapply(N, runtimes) 
qplot(log10(N), runtime, geom = "line") 

Die resultierenden Matrix containst bei (i, j) die Anzahl der Pfade von i nach j der Länge 2 (ohne Pfade, die i selbst enthalten).