# Finding a node in graph with most mutually adjacent nodes

조회 수: 16(최근 30일)
답변: Askic V 2022년 4월 30일
Hello Matlab experts,
I'm learning a graph theory and trying to write some code in Matlab that solves some of the graph problems. One problem I'm trying to solve is the following task: Find node that has maximum number of nodes that also follow that same node. By solving this task I have found some code examples of finding max clique, but I'm pretty sure max clique is somethig different.
I have tried to visualise this to myself and to solve this task first on paper and then to write code.
Please, if you have time, examine this and gice me the following feedback:
1. Is my solution correct?
2. Is there a better way to write the code?
function max_follow_nodes(graph)
clique = {};
%for loop goes to every node in the graph
for i = 1:length(graph)
clique{i} = []; % init empty clique array for each node
node = graph{i}; % this is the node we're examine
%j iterates through elements of the analysed node
for j = 1: length(node)
element = node(j);
if any(ismember(graph{element},i))
k = length(clique{i});
clique{i}(k+1) = element;
end
end
end
max_clq = [];
ind = 0;
for i = 1:length(clique)
if length(max_clq) < length(clique{i})
max_clq = clique{i};
ind = i;
end
end
fprintf('Node with ID: %d has the max follwing nodes: [',ind)
fprintf(' %g ', max_clq);
fprintf(']\n');
end
% graph{1} = [2 4 5 7 9];
% graph{2} = [3 5 7 10];
% graph{3} = [1 2 4 8 9];
% graph{4} = [5 7 9 10];
% graph{5} = [1 4 7];
% graph{6} = [1 2 4 8 9 10];
% graph{7} = [2 4 5 8 10];
% graph{8} = [1 2 4];
% graph{9} = [1 3 4 7];
% graph{10} = [1 2 5 7 9];
1. 댓글을 달려면 로그인하십시오.

### 채택된 답변

Christine Tobler 2022년 4월 29일
Thanks for adding the tag, Steve!
Here's another idea for how to do this. So you want to find all pairs of edges that go a->b and b->a, and then find which node is connected to the largest number of such pairs of edges, right?
G = digraph(false(10));
G = addedge(G, 1, [2 4 5 7 9]);
G = addedge(G, 2, [3 5 7 10]);
G = addedge(G, 3, [1 2 4 8 9]);
G = addedge(G, 4, [5 7 9 10]);
G = addedge(G, 5, [1 4 7]);
G = addedge(G, 6, [1 2 4 8 9 10]);
G = addedge(G, 7, [2 4 5 8 10]);
G = addedge(G, 8, [1 2 4]);
G = addedge(G, 9, [1 3 4 7]);
G = addedge(G, 10, [1 2 5 7 9]);
pG = plot(G); % Get the adjacency matrix of G, for which A(i, j) == 1 only if there is an
% edge i->j
% Now compute a matrix S for which S(i, j) == 1 only if there are edges
% i->j and j->i
S = A & A';
% Turn this adjacency matrix into an undirected graph, where each of its
% edges represents a pair of directed edges in G
SG = graph(S);
% Plot SG, with same node placements as the plot of G so it's easy to
% compare
pSG = plot(SG, XData=pG.XData, YData=pG.YData); % Now it's easy to see that node 7 has the most pairs connected, but we can
% also compute it by getting the maximum degree of the nodes in SG
degree(SG)
ans = 10×1
2 3 2 3 3 0 4 0 3 2

댓글을 달려면 로그인하십시오.

### 추가 답변(2개)

Steven Lord 2022년 4월 29일
G = digraph(false(10));
G = addedge(G, 1, [2 4 5 7 9]);
G = addedge(G, 2, [3 5 7 10]);
G = addedge(G, 3, [1 2 4 8 9]);
G = addedge(G, 4, [5 7 9 10]);
G = addedge(G, 5, [1 4 7]);
G = addedge(G, 6, [1 2 4 8 9 10]);
G = addedge(G, 7, [2 4 5 8 10]);
G = addedge(G, 8, [1 2 4]);
G = addedge(G, 9, [1 3 4 7]);
G = addedge(G, 10, [1 2 5 7 9]);
plot(G) So for each node in the digraph you want the nodes that are both its predecessor and its successor? Let's look at node 7 as a sample:
C = intersect(successors(G, 7), predecessors(G, 7));
C = 4×1
2 4 5 10
Let's plot the digraph again and highlight those nodes.
figure
h = plot(G);
highlight(h, [C; 7], 'NodeColor', 'r') ##### 댓글 수: 0표시숨기기 이전 댓글 수: -1

댓글을 달려면 로그인하십시오.

Christine and Steven, thank you very much for your valuable answers. Now, I have much more efficient way to learn and visualize graphs.
Thank you once again.

댓글을 달려면 로그인하십시오.

### 범주

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!