K-th order neighbors in graph

14 views (last 30 days)
Rub Ron
Rub Ron on 24 Jul 2020
Edited: Bruno Luong on 31 Jul 2020
I would like to do this, but in Matlab with a graph (it is not a directed graph): https://stackoverflow.com/questions/18393842/k-th-order-neighbors-in-graph-python-networkx
I have a graph in which I want to efficiently find a list of all K-th order neighbors of a node (j). K-th order neighbors are defined as all nodes which can be reached from the node in question in exactly K hops.
For example,
s = [1 1 1 1 2 2 2 2 2 8 8 12 6];
t = [3 5 4 2 6 10 7 9 8 11 12 13 7];
G = graph(s,t);
plot(G)
If j=1, I want to get :
for k=1
[2 3 4 5]
for k=2
[6 7 8 9 10]
for k=3
[11 12]
k=4
[13]
k=5
empthy

Accepted Answer

Matt J
Matt J on 24 Jul 2020
Edited: Matt J on 25 Jul 2020
function result=distk(G,i,k)
% G -graph
% i - start node
% k - number of steps
A=adjacency(G);
v=A(i,:);
prior=false(size(v)); prior(i)=true;
for n=1:k-1
prior=prior|v;
v=v*A;
end
result = find(v&~prior);
end
  15 Comments
Bruno Luong
Bruno Luong on 29 Jul 2020
Edited: Bruno Luong on 31 Jul 2020
Here is my benchmark code, feel free to play with it.
function BenchGNeighbor
start = 1; % starting node
% Graph corresponds to the 2D square grid of size 1000 x 1000
[X,Y] = ndgrid(1:1000);
n = numel(X);
I = sub2ind(size(X),X(1:end-1,:),Y(1:end-1,:));
J = I+1;
A = sparse(I,J,1,n,n);
I = sub2ind(size(X),X(:,1:end-1),Y(:,1:end-1));
J = I+size(X,1);
A = A + sparse(I,J,1,n,n);
A = A + A';
G = graph(A);
k = 100; %size(X,1);
% clean memory
clear X Y I J
k = min(k,size(A,1));
%% Matlab graph distances method
tic
d = distances(G, start);
rMatlab = find(d==k);
tMatlab = toc;
%% Bruno's algorithm
tic
n = size(A,1);
% initialize distance matrix
notdone = true(n,1);
i = start;
for q=1:k
notdone(i) = false;
[i,~] = find(A(:,i));
if isempty(i)
break
end
i = unique(i);
i = i(notdone(i));
end
rBruno = reshape(i,1,[]);
tBruno = toc;
%% Matt method
tic
i = start; % start node
v = A(i,:);
prior = false(size(v));
prior(i) = true;
for j=1:k-1
prior = prior|v;
v = v*A;
end
rMatt = find(v & ~prior);
tMatt = toc;
% Check matching results
if ~isequal(rBruno, rMatlab) || ~isequal(rMatt, rMatlab)
fprintf('Bug detected!!!\n');
end
fprintf('Timings for 2D-grid graph with number of nodes = %d, k=%d\n', n, k);
fprintf('\ttMatlab = %f [second]\n', tMatlab);
fprintf('\ttBruno = %f [second]\n', tBruno);
fprintf('\ttMatt = %f [second]\n', tMatt);

Sign in to comment.

More Answers (3)

Bruno Luong
Bruno Luong on 25 Jul 2020
Edited: Bruno Luong on 28 Jul 2020
It sounds like you look at graph-distance and NOT what you described "K-th order neighbors are defined as all nodes which can be reached from the node in question in exactly K hops." The later problem is solved by my other answer.
If it is is the first case (graph distance) one can do by shortest path algorithms such as Bellman-Ford (BF) algorithm.
Graph example (yours):
s = [1 1 1 1 2 2 2 2 2 8 8 12 14 14 1 14];
t = [3 5 4 2 6 10 7 9 8 11 12 13 7 6 8 15];
G = graph(s,t);
plot(G)
BF algo (note: the bellow is not optimal implemented, since using full matrix with Inf).
start = 1; % starting node
B = adjacency(G);
B = full(B);
B(B==0) = Inf;
n = size(B,1);
d = inf(n,1);
d(start) = 0;
while any(isinf(d)) % careful graph must be connected, otherwise loop forever
d = min(d,min(d+B,[],1).');
end
Or simply using MATLAB stock function
d = distances(G,start);
% neighhbor for any specific k, e.g. k=2; neightbors i are
% i = find(d==k)
Display result
n = size(G.Nodes,1);
nodes = setdiff(1:n,start)';
d = d(:);
dcell = accumarray(d(nodes), nodes, [], @(x) {x.'});
K = (1:length(dcell))';
for k=1:length(dcell)
i = dcell{k};
fprintf('k = %d: i = %s\n', k, mat2str(i));
end
Result
k = 1: i = [2 3 4 5 8]
k = 2: i = [6 7 9 10 11 12]
k = 3: i = [13 14]
k = 4: i = 15
  1 Comment
Bruno Luong
Bruno Luong on 28 Jul 2020
Edited: Bruno Luong on 30 Jul 2020
In the above I code Bellman-Ford algorithm like this single-line while loop for illustration purpose:
% ...
% Initialization of d and B
while any(isinf(d)) % careful graph must be connected, otherwise loop forever
d = min(d,min(d+B,[],1).');
end
A better implementation of Bellman-Ford algorithm that exploits the sparsity of ajadcent matrix to compute the shortest distance is
start = 1; % starting node
A = adjacency(G); % eventually with non-unit and non-negative weight
n = size(A,1);
% initialize distance matrix
d = inf(n,1);
du = 0;
i = start;
while true
d(i) = du;
[i,j,dij] = find(A(:,i));
if isempty(i)
break
end
[du, p] = sort(du(j)+dij);
[i, p] = sort(i(p)); % here we requires stable sorting, which is the case with MATLAB
b = [true; diff(i,1,1)>0];
i = i(b);
du = du(p(b));
b = du < d(i);
i = i(b);
du = du(b);
end
% Exit the while-loop d contains distance vector from start-node to all nodes

Sign in to comment.


Bruno Luong
Bruno Luong on 24 Jul 2020
Edited: Bruno Luong on 24 Jul 2020
Assuming A is the transposed of the adjacent matrix (n x n).
j in (1:n) is the source node number.
This method should be faster than computing A^k proposed by Matt
x = zeros(n,1);
x(j) = 1;
for i=1:k
x = A*x;
end
i = find(x)';
fprintf('%d-neighbor of %d is %s\n', k, j, mat2str(i))
If sparse form of the adjadcent matrix is readily available, it could be preferable to use it.
  7 Comments
Rub Ron
Rub Ron on 24 Jul 2020
You might be focusing only in the example rather than in a general case. In my case the graphs are not directed, I cannot make them "nicely" directed. For intance, by changing the example graph to this one, the outputs are not the desired ones
s = [3 5 4 2 6 10 7 9 8 11 12 13];
t = [1 1 1 1 2 2 2 2 2 8 8 12];
G = digraph(s,t);

Sign in to comment.


Bruno Luong
Bruno Luong on 31 Jul 2020
Edited: Bruno Luong on 31 Jul 2020
Given A an (n x n) symmetric ajadcent matrix (undirected graph), and k the order (integer scalar), I propose this algorithm to find index of all k-neigbor of node #start
n = size(A,1);
k = min(k,n);
notdone = true(n,1);
i = start;
for q=1:k
notdone(i) = false;
[i,~] = find(A(:,i));
if isempty(i)
break
end
i = unique(i);
i = i(notdone(i));
end
neighbouridx = i; % column vector

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Products

Community Treasure Hunt

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

Start Hunting!