10
$\begingroup$

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:
enter image description here

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.

$\endgroup$
  • 2
    $\begingroup$ Please be aware that asking for (R) packages or code are off-topic here. You may want to make the "find" portion more prominent & the "get" portion less so. $\endgroup$ – gung Feb 26 '15 at 21:03
  • 3
    $\begingroup$ I will attempt to make a full answer sometime when I get a chance @gung. But for a quick answer here is the community detection applied to the example graph of EngrStudent using the R igraph package. $\endgroup$ – Andy W Feb 26 '15 at 21:22
  • 1
    $\begingroup$ IMHO there is only one cluster in this graph. There are, however, three overlapping cliques. I don't know why your plan is to destroy the middle clique - unless you can formalize this, you'll have a hard time finding an algorithm. $\endgroup$ – Anony-Mousse Feb 27 '15 at 7:30
  • 2
    $\begingroup$ For what it's worth, mcl (micans.org/mcl) finds the two clusters (I don't really agree with Anony-Mousse's assessment, and I don't find the clique-modeling approach to graph clustering particularly fruitful). This is with its single parameter (controlling granularity) set to default. This algorithm (mcl - I published it) is used quite widely in bioinformatics, and (highly scalable) source code is available. Interfacing with R is easily done using text interfaces. $\endgroup$ – micans Feb 27 '15 at 15:57
  • 2
    $\begingroup$ Asking for code & packages has essentially always been off-topic here. Asking for help w/ existing code (ie you have a reproducible example) is on-topic on Stack Overflow. If you didn't know this, it's time to learn it. The idea that the users answering R Qs on SO don't have statistical expertise is weird to me, but many people seem to assume that; at any rate it is not true. That your Q was answered by a SO post should say something here. OTOH, saying 'what kind of analysis is this, can someone point me to resources' is definitely on-topic here. $\endgroup$ – gung Feb 27 '15 at 16:51
9
$\begingroup$

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)

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ Also given the previous comments about using a graph database, you do not need to have the graph represented as an adjacency matrix. A table for the nodes and a row for each edge is a more typical/efficient format, and you can turn that into an igraph network. $\endgroup$ – Andy W Mar 3 '15 at 14:34
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I did not know such a thing existed. Neat! Is this a decent example of the material? nicolewhite.github.io/RNeo4j/examples $\endgroup$ – EngrStudent Feb 27 '15 at 20:31
  • $\begingroup$ How would one go from data in neo4j to graph-clustering? Would mcl or igraph work with it? $\endgroup$ – EngrStudent Mar 2 '15 at 16:38
  • 2
    $\begingroup$ Once you have pulled your data from neo4j into R, you can use any other R package (e.g., AndyW suggests igraph) against the data. Alternatively - the Rneo4j package includes commands for retrieving data, and also allows you to run the Cypher query language (analogous to SQL, but custom-built for the neo4j graph db). In Cypher, you can do sophisticated queries and run some predefined algorithms (Shortest paths, all paths, all simple paths, Dijkstra, etc.). I'm at my limit here in both characters and content - If you want to go down this path (sorry!), the neo4j site might be your next stop. $\endgroup$ – user3123116 Mar 3 '15 at 20:24
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Although this may be related to the question it does not seem to be an answer. $\endgroup$ – Michael Chernick Mar 22 '18 at 16:35
  • 1
    $\begingroup$ i answered the two questions : Is there an 'R' package that will properly cluster the nodes on the network? Could you point me to example code to do this? But yes, It does not answer the whole set of questions. $\endgroup$ – Omar Jaafor Mar 22 '18 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.