CODEWITHSUNDEEP
rperformanceigraph
araspion
araspion

Reputation: 713

Neighbor groups based on cluster assignment is slow

I am doing some analysis using iGraph in R, and I am currently doing a calculation that is very expensive. I need to do it across all of the nodes in my graph, so if someone knows a more efficient way to do it, I would appreciate it.

I start out with a graph, g. I first do some community detection on the graph

library(igraph)
adj_matrix <- matrix(rbinom(10 * 5, 1, 0.5), ncol = 8000, nrow = 8000)
g <- graph_from_adjacency_matrix(adj_matrix, mode = 'undirected', diag = FALSE)
c <- cluster_louvain(g)

Then, I basically assign each cluster to 1 of 2 groups 

nc <- length(c)
assignments <- rbinom(nc, 1, .5)

Now, for each node, I want to find out what percentage of its neighbors are in a given group (as defined by the cluster assignments). I currently do this in the current way:

pct_neighbors_1 <- function(g, vertex, c, assignments) { 
  sum(
    ifelse(
      assignments[membership(c)[neighbors(g, vertex)]] == 1, 1, 0)
    )/length(neighbors(g, vertex))
}

And then, given that I have a dataframe with each row corresponding to one vertex in the graph, I do this for all vertices with

  data$pct_neighbors_1 <- sapply(1:nrow(data), 
                                 pct_neighbors_1, 
                                 graph = g, community = c,
                                 assignments = assignments)

Is there somewhere in here that I can make things more efficient? Thanks!

Upvotes: 0

Views: 127

Answers (1)

digEmAll
digEmAll

Reputation: 57210

This should be faster :

library(igraph)

# for reproducibility's sake
set.seed(1234)

# create a random 1000 vertices graph
nverts <- 1000
g <- igraph::random.graph.game(nverts,0.1,type='gnp',directed=FALSE)

# clustering
c <- cluster_louvain(g)

# assignments
nc <- length(c)
assignments <- rbinom(nc, 1, .5)

# precalculate if a vertex belongs to the assigned communities
vertsInAssignments <- membership(c) %in% which(assignments==1)

# compute probabilities
probs <- sapply(1:vcount(g),FUN=function(i){
      neigh <- neighbors(g,i)
      sum(vertsInAssignments[neigh]) / length(neigh)
})

Upvotes: 2

Related Questions