Community detection algorithm with igraph and R – (2)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
Iterators in igraph
“A note about the performance of theV
andE
functions, and the selection of edges and vertices. Since all selectors are evaluated as logical vectors on all vertices/edges, their performance is bad on large graphs. (Time complexity is proportional to the total number of vertices/edges.) We suggest using theneighbors
,incident
functions and simple R vector operations for manipulating vertex/edge sequences in large graphs.”
Iteratorless LPA
LargeScaleCommunityFast <- function(g, mode="all") {
cat(“Assigning initial communities…\n”)
vgroups <- V(g)$name
# random order in which vertices will be processed
cat(“Generating random order…\n”)
order <- sample(vcount(g), vcount(g))
t <- 0
done <- FALSE
while (!done) {
t <- t + 1
cat(“round: “, t, “\n”)
## change to FALSE whenever a node changes groups
done <- TRUE
for(i in order) {
## get the neighbor group frequencies:
group.freq <- table(vgroups[neighbors(g, i, mode = mode)])
## pick one of the most frequent:
new.group <- sample(names(group.freq)[group.freq == max(group.freq)], 1)
if (done) {
## we are only done if new group is the same as old group
done <- (new.group == vgroups[i])
}
vgroups[i] <- new.group
}
}
cat(“Creating community-object…\n”)
comms <- list(membership = as.numeric(vgroups),
vcount = vcount(g),
algorithm = “LPA”,
names = V(g)$name)
class(comms) <- "communities"
return(comms)
}
Executing the algorithm
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.