Finding a node in graph with most mutually adjacent nodes

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. 

Answer 1

[Christine Tobler]

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

Answer 2

[Steven Lord]

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')

Answer 3

[Askic V]

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.