how to find out the common neighbors of two nodes in a graph?

I have a matrix in which column 1 and 2 represents the nodes which are connected with each-other. For example, A=[1 2; 1 3; 1 4; 2 1; 3 1; 3 4; 4 1; 4 3].

(in this example, node 1,3, and 4 are connected with each-other hence each of them has one common neighbor).

Now my question is that how do I extract B=[1 3; 1 4; 3 1; 3 4; 4 1; 4 3].

Thanks in advance!

Answer 1

[Christine Tobler]

You can use the graph class for something like this. First, make a graph from the connection inputs you had:

>> A=[1 2; 1 3; 1 4; 2 1; 3 1; 3 4; 4 1; 4 3];
>> g = simplify(graph(A(:, 1), A(:, 2)));
>> plot(g)

Now, compute the adjacency matrix of that graph: ad(i, j) == 1 if there is a connection between nodes i and j, otherwise it is zero.

>> ad = adjacency(g); full(ad)

ans =

     0     1     1     1
     1     0     0     0
     1     0     0     1
     1     0     1     0

If you use matrix multiplication with that adjacency matrix, you get a matrix where adCommon(i, j) ~= 0 if there is at least one common node between nodes i and j.

>> adCommon = ad'*ad; full(adCommon)

ans =

     3     0     1     1
     0     1     1     1
     1     1     2     1
     1     1     1     2

Construct a graph from this new adjacency matrix (ignoring its diagonal entries which would otherwise be seen as self-loops), and plot it.

>> gCommon = graph(adCommon, 'omitselfloops');
>> figure
>> plot(gCommon)

As you said, nodes, 3, 4 and 1 each shared a common node because they're part of a cycle. Additionally, nodes 2 and 4 have a common neighbor, which is node 1, and the same is true for nodes 2 and 3.

[Christine Tobler]

Just FYI, I'm about to go on vacation so won't be able to have any additional discussion this year.

[ST]

I need the indices of common nodes, not what you have answered. I guess my question can be answered using simple vector/matrix operations which I am not able to think of as of now. Thanks for the efforts though. Happy vacation.