MATLAB: How to find out the common neighbors of two nodes in a graph

common neighborsgraphgraph theory

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!

Best Answer

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.
Related Question