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:
- Is my solution correct?
- 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];
采纳的回答
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)
更多回答（2 个）
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));
Let's plot the digraph again and highlight those nodes.
figure
h = plot(G);
highlight(h, [C; 7], 'NodeColor', 'r')
类别
在 帮助中心 和 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!
Translated by 
