Neighbor groups based on cluster assignment is slow

Question

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!

can you provide sample g http://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example — Bulat, May 08 '16 at 21:18
still bits missing `Error: could not find function "graph_from_adjacency_matrix"` — Bulat, May 08 '16 at 21:30
Which bit you want to optimise? just focus on that and provide sample for specific transformation — Bulat, May 08 '16 at 21:32
Those are both function in iGraph. I thought it was pretty obvious you would need to load that library since the question specifically mentions it, but I'll throw the relevant line at the top of the code. — araspion, May 08 '16 at 22:47

digEmAll · Accepted Answer · 2016-05-08T21:44:29.183

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

Neighbor groups based on cluster assignment is slow

1 Answers1