Finding a node in graph with most mutually adjacent nodes

3 views (last 30 days)
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];

Accepted Answer

Christine Tobler
Christine Tobler on 29 Apr 2022
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
A = adjacency(G);
% 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

More Answers (2)

Steven Lord
Steven Lord on 29 Apr 2022
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')

Askic V
Askic V on 30 Apr 2022
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.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by