Skip to content

Instantly share code, notes, and snippets.

@ngopal
Last active February 24, 2016 00:45
Show Gist options
  • Save ngopal/2c7add2c60326911b011 to your computer and use it in GitHub Desktop.
Save ngopal/2c7add2c60326911b011 to your computer and use it in GitHub Desktop.
A playground where I was implementing the algorithm detailed in the "Centrality Based Visualization of Small World Graphs"
library(igraph)
g <- watts.strogatz.game(1, 100, 5, 0.05)
#g <- erdos.renyi.game(100, 3/100)
plot(g, vertex.size=2, vertex.label=NA)
# Calculate edge betweenness
eb <- cbind(E(g),edge_betweenness(g))
ebt <- eb[order(eb[,2], decreasing = T),]
head(ebt)
plot(ebt[,2], main="distribution of edge betweenness", ylab="Edge Between Score")
abline(h=35, col="red")
abline(v=100, col="red")
el <- get.edgelist(g)[as.vector(tail(ebt, 500-50)[,1]),] #edges as edgelist
elg <- graph_from_edgelist(el, directed=FALSE)
plot(elg, vertex.size=2, vertex.label=NA)
# Use low edge between scores to make minimum span tree
mst <- minimum.spanning.tree(elg)
layout.fruchterman.reingold(mst)
plot(mst, vertex.size=2, vertex.label=NA)
# FD layout
layout.fruchterman.reingold(mst)
# reinsert high edge between graph one at a time, starting with the highest
for (i in 1:dim(ebt)[1]) {
new_el <- get.edgelist(g)[as.vector(ebt[i,1]),]
el <- rbind(new_el,el) # note this will recalculate layout everytime, rather than just adding edges
elg <- graph_from_edgelist(el, directed=FALSE)
plot(elg, vertex.size=2, vertex.label=NA)
readline(prompt="Press [ENTER] to continue")
}
# Everything below is unfinished an experimental
entropy.binary <- function(line) {
p <- mean(line)
return(-p*log2(p) - (1 - p)*log2((1 - p)))
}
binary_entropy <- function(graphObject) {
# this is node entropy. I want edge entropy!
# perhaps:
# 1. Calculate all paths
# 2. See how many edges make up each path. If an edge is part of pat, then 1, else 0
# 3.
matrixObject <- as.matrix(get.adjacency(graphObject, type="both"))
t <- cbind(dim(matrixObject)[1],apply(matrixObject, MARGIN=c(1), FUN=entropy.binary))
t <- t[order(t[,2]),]
return(t)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment