그래프 노드의 이차 이웃들 R

Question

큰 그래프에서 모든 노드의 정확한 정도의 이웃을 찾는 효율적인 방법을 찾고 있습니다. 보다 효율적인 방법이 있나요

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") 

: 심지어는 최대 스파 스 매트릭스 같은 그래프, igraph::ego 불면를 저장하지만?

Answer 1

인접 행렬을 사용하면 직접적인 개선이 가능합니다. 10^5 분석 될 수 없다 10^(7)의 에르 도스 RENYI의 예

# 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) 
}  

절반 분의 현재 네트워크 :

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") 

얻어진 매트릭스 containst에서 (i, j) i에서 길이 2의 j까지의 경로 수 (i 자체를 포함하는 경로는 제외).