Return a list of mutual nodes between every pair of nodes in R

Question

I want to obtain a list of mutually connected nodes between every pair of nodes in my graph:

library(igraph)
G <- graph(c(1,2,1,3,1,4,2,4, 2,3,2,5,3,5,4,5,5,6,5,7,7,8,7,9), directed=F)
 
plot(G)

Click here for the Graph

the edge is undirected.

In this graph, for instance, node 1 and 2 share common nodes 3 and 4. And node 1 and 3 share common node 2. I would like to get a list of this or as a format of a data frame..

Is there a command for getting something like either one of these:

(1)

 node1   node2     mutual
   1      2          3, 4
   1      3          2
   1      4          2
   2      3          1, 5

or (2)

 node1   node2     mutual
   1      2          3
   1      2          4
   1      3          2
   1      4          2
   2      3          1
   2      3          5

I was able to get the number of mutual nodes between two nodes using this code:

# function to count the number of mutual friends between every pair of nodes
mutual_friends <- function(G) {
  # initialize an emptry matrix to store number of mutual friends between pairs of nodes
  num_nodes <- vcount(G)
  mutual_friends <- matrix(0, nrow=num_nodes, ncol=num_nodes)

  # loop over each node
  for (node in 1:num_nodes) {
    # get this node's list of friends
    friends <- neighbors(G, node)
    
    # add a count of 1 between all pairs of the node's friends
    for (i in friends)
      for (j in friends)
        mutual_friends[i, j] = mutual_friends[i, j] + 1
  }
  
  # make the output readable with column names
  dimnames(mutual_friends) <- list(row=V(G)$name, col=V(G)$name)
  diag(mutual_friends) <- NA
  mutual_friends
}

(coding credit to: https://rstudio-pubs-static.s3.amazonaws.com/72599_65ecae185590432cb2373df4825d2ef9.html#connected-components

But I'm struggling with getting a list of the mutual nodes between every pair of nodes. I appreciate any kind of advice and help. Thanks!

user_2372064 · Answer

This is not exactly efficient, it's a brute force double loop, but you can do

get_mutuals <- function(g) {
  do.call("rbind", lapply(seq.int(1, vcount(g)-1), function(i) {
    do.call("rbind", lapply(seq.int(i+1, vcount(g)), function(j) {
      ni <- neighbors(g, i)
      nj <- neighbors(g, j)
      overlap <- intersect(ni, nj)
      if (length(overlap) & i %in% nj) {
        data.frame(i=i, j=j, m=overlap)
      } else {
        NULL
      }
    }))
  }))
}
get_mutuals(G)

Which will give you output that looks like your version 2.

If you wanted something more like one you could swap to data.frame(i=i, j=j, m=toString(overlap)) to paste all the values together in the column.

Another possibility is to iterate the edges like this

get_mutuals <- function(g) {
  do.call("rbind", lapply(seq.int(1, gsize(g)), function(i) {
    edge <- ends(g, i)
    i <- edge[1, 1]
    j <- edge[1, 2]
    ni <- neighbors(g, i)
    nj <- neighbors(g, j)
    overlap <- intersect(ni, nj)
    if (length(overlap)) {
      data.frame(i=i, j=j, m=overlap)
    } else {
      NULL
    }
  }))
}
get_mutuals(G)

user_12148402 · Answer

Note that if two adjacent nodes share a common neighbor they form a triangle. Function igraph::triangles gives you all triangles in graph.

library(dplyr)

triangle_matrix <- matrix(igraph::triangles(G), ncol = 3, byrow = TRUE) 

gtools::permutations(3, 3) %>%
  apply(1, function(x) list(triangle_matrix[, x])) %>%
  unlist(recursive = FALSE) %>%
  Reduce(rbind, .) %>%
  as.data.frame() %>%
  filter(V1 < V2) %>%
  arrange(V1, V2, V3)

You can get (1) by continuing the pipe with:

... %>% group_by(V1, V2) %>% summarise(mutual = list(V3))

user_12158757 · Answer

Update

If you want to find out all directly connected nodes with a mutual node, you can try triangles in igraph like below

do.call(
  rbind,
  apply(
    matrix(triangles(G), nrow = 3),
    2,
    function(v) {
      u <- t(sapply(seq_along(v), function(k) t(v[-k])))
      setNames(data.frame(cbind(v, rbind(u, u[, 2:1]))), c("node1", "node2", "mutual"))
    }
  )
)

which gives

   node1 node2 mutual
1      5     2      3
2      2     5      3
3      3     5      2
4      5     3      2
5      2     3      5
6      3     2      5
7      5     2      4
8      2     5      4
9      4     5      2
10     5     4      2
11     2     4      5
12     4     2      5
13     2     1      4
14     1     2      4
15     4     2      1
16     2     4      1
17     1     4      2
18     4     1      2
19     2     1      3
20     1     2      3
21     3     2      1
22     2     3      1
23     1     3      2
24     3     1      2

Perhaps you can try ego like below

setNames(
  data.frame(do.call(
    rbind,
    lapply(
      Filter(
        function(x) length(x) > 2,
        ego(G)
      ),
      function(v) {
        cbind(t(combn(v[-1], 2)), v[1])
      }
    )
  )),
  c("node1", "node2", "mutual")
)

which gives

   node1 node2 mutual
1      2     3      1
2      2     4      1
3      3     4      1
4      1     3      2
5      1     4      2
6      1     5      2
7      3     4      2
8      3     5      2
9      4     5      2
10     1     2      3
11     1     5      3
12     2     5      3
13     1     2      4
14     1     5      4
15     2     5      4
16     2     3      5
17     2     4      5
18     2     6      5
19     2     7      5
20     3     4      5
21     3     6      5
22     3     7      5
23     4     6      5
24     4     7      5
25     6     7      5
26     5     8      7
27     5     9      7
28     8     9      7

Return a list of mutual nodes between every pair of nodes in R

3 Answers

Update