how to find out the common neighbors of two nodes in a graph?
조회 수: 29 (최근 30일)
이전 댓글 표시
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
채택된 답변
Christine Tobler
2020년 12월 11일
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
Christine Tobler
2020년 12월 11일
Just FYI, I'm about to go on vacation so won't be able to have any additional discussion this year.
추가 답변 (0개)
참고 항목
카테고리
Help Center 및 File Exchange에서 Graph and Network Algorithms에 대해 자세히 알아보기
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!