K-th order neighbors in graph

4 次查看（过去 30 天）
Rub Ron
Rub Ron 2020-7-24
编辑： Bruno Luong 2020-7-31
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

请先登录，再回答此问题。

采纳的回答

Matt J
Matt J 2020-7-24
编辑：Matt J 2020-7-25
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 个评论
显示 13更早的评论
Bruno Luong
Bruno Luong 2020-7-29
编辑：Bruno Luong 2020-7-29
"A drawback of Bruno's approach that I see is that its use of distances() will compute all distances, even those greater than the particular k of interest."
I just did some benchmark, and Matlab graph distances seems to be pretty fast and beat all even for small k and large n. Let alone the case where k is large.
If that is matter at all.
Bruno Luong
Bruno Luong 2020-7-29
编辑：Bruno Luong 2020-7-31
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);

请先登录，再进行评论。

更多回答（3 个）

Bruno Luong
Bruno Luong 2020-7-25
编辑：Bruno Luong 2020-7-28
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 个评论
Bruno Luong
Bruno Luong 2020-7-28
编辑：Bruno Luong 2020-7-30
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
Bruno Luong 2020-7-24
编辑：Bruno Luong 2020-7-24
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 个评论
显示 5更早的评论
Bruno Luong
Bruno Luong 2020-7-24
编辑：Bruno Luong 2020-7-24
When you allow to go from s to t, and forbid to go in the opposite direction from t to s, it's called digraph
s = [1 1 1 1 2 2 2 2 2 8 8 12];
t = [3 5 4 2 6 10 7 9 8 11 12 13];
G = digraph(s,t);
plot(G)
A = adjacency(G).';
n = size(A,1);
x = zeros(n,1);
x(1) = 1;
for k=1:5
x = A*x;
i = find(x)';
fprintf('k = %d: i = %s\n', k, mat2str(i));
end
Output match your expectation
k = 1: i = [2 3 4 5]
k = 2: i = [6 7 8 9 10]
k = 3: i = [11 12]
k = 4: i = 13
k = 5: i = zeros(1,0)
Rub Ron
Rub Ron 2020-7-24
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
Bruno Luong 2020-7-31
编辑：Bruno Luong 2020-7-31
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

类别

在 Help Center 和 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