Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to identify fully connected node clusters with igraph?

Tags:

r

igraph

I'm trying to calculate the clusters of a network using igraph in R, where all nodes are connected. The plot seems to work OK, but then I'm not able to return the correct groupings from my clusters.

In this example, the plot shows 4 main clusters, but in the largest cluster, not all nodes are connected:

enter image description here

I would like to be able to return the following list of clusters from this graph object:

[[1]]
[1] 8 9

[[2]]
[1]  7 10

[[3]]
[1]  4  6 11

[[4]]
[1] 2 3 5

[[5]]
[1]  1  3  5 12

Example code:

library(igraph)

topology <- structure(list(N1 = c(1, 3, 5, 12, 2, 3, 5, 1, 2, 3, 5, 12, 4, 
6, 11, 1, 2, 3, 5, 12, 4, 6, 11, 7, 10, 8, 9, 8, 9, 7, 10, 4, 
6, 11, 1, 3, 5, 12), N2 = c(1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 
3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 
11, 11, 11, 12, 12, 12, 12)), .Names = c("N1", "N2"), row.names = c(NA, 
-38L), class = "data.frame")

g2 <- graph.data.frame(topology, directed=FALSE)
g3 <- simplify(g2)
plot(g3)

The cliques function gets me part of the way there:

tmp <- cliques(g3)
tmp

but, this list also gives groupings where not all nodes connect. For example, this clique includes the nodes 1,2,3,5 but 1 only connects to 3, and 2 only connects to 3 and 5, and 5 only connects to 2 :

topology[tmp[[31]],]
#  N1 N2
#6  3  2
#7  5  2
#8  1  3

Thanks in advance for any help.

like image 884
Marc in the box Avatar asked May 15 '14 19:05

Marc in the box


Video Answer


1 Answers

You could use maximal.cliques in the igraph package. See below.

# Load package
library(igraph)

# Load data
topology <- structure(list(N1 = c(1, 3, 5, 12, 2, 3, 5, 1, 2, 3, 5, 12, 4, 
6, 11, 1, 2, 3, 5, 12, 4, 6, 11, 7, 10, 8, 9, 8, 9, 7, 10, 4, 
6, 11, 1, 3, 5, 12), N2 = c(1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 
3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 
11, 11, 11, 12, 12, 12, 12)), .Names = c("N1", "N2"), row.names = c(NA, 
-38L), class = "data.frame")

# Get rid of loops and ensure right naming of vertices
g3 <- simplify(graph.data.frame(topology[order(topology[[1]]),],directed = FALSE))

# Plot graph
plot(g3)

# Calcuate the maximal cliques
maximal.cliques(g3)

# > maximal.cliques(g3)
# [[1]]
# [1] 9 8
# 
# [[2]]
# [1] 10  7
# 
# [[3]]
# [1] 2 3 5
# 
# [[4]]
# [1]  6  4 11
# 
# [[5]]
# [1] 12  1  5  3
like image 134
majom Avatar answered Sep 22 '22 16:09

majom