Approach and example of graph clustering in "R"

Question

I am looking to group/merge nodes in a graph using graph clustering in 'r'.

Here is a stunningly toy variation of my problem.

• There are two "clusters"
• There is a "bridge" connecting the clusters

Here is a candidate network:

When I look at the connection distance, the "hopcount", if you will, then I can get the following matrix :

 mymatrix <- rbind(
     c(1,1,2,3,3,3,2,1,1,1),
     c(1,1,1,2,2,2,1,1,1,1),
     c(2,1,1,1,1,1,1,1,2,2),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,2,2),
     c(2,1,1,1,1,1,1,1,2,2),
     c(1,1,1,2,2,2,1,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1))

Thoughts here:

• By luck or due to the simplicity of the toy the matrix has obvious patches this is not going to be the case in the (very large) matrix. If I randomized the relationship between point and row then it would not be so clean.
• I might have got one wrong - so if I have a typo, let me know.
• Hop-count here is shortest number of hops to connect point on row i with point on column j. A self-hop is still a hop, so the diagonal is all ones.

So in this matrix larger distance (hops) has a higher number. If I wanted a matrix showing "connectivity" instead of distance, then I could do a dot-inverse, where each cell of the matrix is replaced with its multiplicative inverse.

Questions:

To help me find my own way:

• What are the terms for reducing the number of nodes on a graph by combining them? Is it clustering, merging, munging - what are the words that I should use?
• What are the proven techniques? Is there a textbook on the topic? Can you point to papers or websites?
• Now I tried to look here first - it is a great "first check" spot. I didn't find what I was looking for. If I missed it (not unlikely) can you point me to an answered question or two on the topic here at CV?

To get me where I am going:

• Is there an 'R' package that will properly cluster the nodes on the network?
• Could you point me to example code to do this?
• Is there an 'R' package that will graphically present the resulting reduced network?
• Could you point me to example code to do this?

Thanks in advance.

Answer 1

Your particular example suggests finding communities within the network that have more connections between nodes in the community and relatively few edges between nodes in different communities. This is distinct from finding isolated communities, in which there are subgraphs that are completely disconnected.

Here is an example of community detection in R using the igraph package and an algorithm described in Clauset et al. (2004). To use this algorithm I turn your "hop count" into a binary adjacency matrix with no self loops. The algorithm needs an undirected matrix, which is consistent with your hand written diagram and the data you provided (the edges are symmetric).

library(igraph)
mymatrix <- rbind(
     c(1,1,2,3,3,3,2,1,1,1),
     c(1,1,1,2,2,2,1,1,1,1),
     c(2,1,1,1,1,1,1,1,2,2),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,2,2),
     c(2,1,1,1,1,1,1,1,2,2),
     c(1,1,1,2,2,2,1,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1))

#turn this into an adjacency matrix
adjMat <- mymatrix == 1
diag(adjMat) <- 0 #no self loops

g  <- graph.adjacency(adjMat)
plot(g)

#only works for undirected graphs, which this example is fine since symetric
fc <- fastgreedy.community(as.undirected(g))

#make colors for different communities
V(g)$color <- ifelse(membership(fc)==1,"red","blue")
plot(g)

I can not comment on the appropriateness of collapsing such nodes for further analysis, but such community detection is definitely useful for exploring the network. There are plenty of other community detection algorithms as well (as well as other libraries for network analysis in R). This is just one example that happens to produce your desired output for this toy problem.

Answer 2

For future readers,

Here is a set of functions from the igraph packages and the last one is from MCL:

print("LABEL PROPAGATION")
w<-cluster_label_prop(g)

print("Leading Eigen")
w<-cluster_leading_eigen(g)

print("SpinGlass")
w<-cluster_spinglass(g, stop.temp = 0.05)

print("walktrap")
w<-cluster_walktrap(g, steps=4)

print("MCL")
adj<-get.adjacency(g)
w<-mcl(adj,addLoops=TRUE)

You can find the documentation here http://igraph.org/r/doc/ and here https://cran.r-project.org/web/packages/MCL/MCL.pdf

I find walktrap particularly useful

Answer 3

If you are not already wedded to a repository for your node and connection data, you might look at the Rneo4j package. But this implies use of the neo4j (a graph database, not a RDBMS) to store your data. I'm no expert here, but I do think this approach might be especially effective if a) as suggested by Anony-Mousse, you cannot formalize this, or b) the number of nodes and connections is especially large, or c) you wind up having additional questions regarding your network.