how to find out the common neighbors of two nodes in a graph?
29 views (last 30 days)
Show older comments
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!
0 Comments
Accepted Answer
Christine Tobler
on 11 Dec 2020
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.
2 Comments
Christine Tobler
on 11 Dec 2020
Just FYI, I'm about to go on vacation so won't be able to have any additional discussion this year.
More Answers (0)
See Also
Categories
Find more on Graph and Network Algorithms in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!