# K-th order neighbors in graph

19 views (last 30 days)
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

k=5
empthy

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

### More Answers (3)

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 = 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 CommentShowHide None
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

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.
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);

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