Search code examples
rcluster-analysisigraph

Eliminate clique clusters with igraph

I have a network with several components, I would like:

  1. To drop any cluster that is fully connected

Toy example:

g <- graph(c("a","b","b","c","c","a","f","g","h","g"))
result_g <- graph(c("f", "g","h","g"))
  1. To be able to label only vertex of a component only when (among other conditions) these do not belong to a fully connected component.
Solution

  • To do this, you can first split the graph into connected components using the components function. Then you can test each component to see whether or not it is a full subgraph. A graph is full if and only if the number of edges is equal to n(n-1)/2 where n is the number of nodes. So, using your example:

    CompList = components(g)
NotFull = c()
for(i in 1:CompList$no) {
    COMP = induced_subgraph(g, which(CompList$membership==i))
    VC = vcount(COMP)
    if(ecount(COMP) != VC*(VC-1)/2) {
        NotFull = c(NotFull, which(CompList$membership==i)) }
}
result_g = induced_subgraph(g, NotFull)
result_g
IGRAPH 5d61ea5 DN-- 3 2 -- 
+ attr: name (v/c)
+ edges from 5d61ea5 (vertex names):
[1] f->g h->g