Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

To resolve issues starting MATLAB on Mac OS X 10.10 (Yosemite) visit: http://www.mathworks.com/matlabcentral/answers/159016

Finding all edges (and nodes) within X steps from a chosen line in an adjacency matrix

Asked by John Doe on 2 May 2013

I have a nx2 matrix of to-from nodes for a large network structure. I have used this to create a sparse adjacency matrix which I can plot using BIOGRAPH. My systems varies in size, the largest ones having more than 3000 nodes (obviously not suitable for plotting).

If I choose a line, I want to be able to create a list of all lines and nodes that are within X "steps" from the original line (two nodes), for a given X (typically 3). It's clearly not too difficult using brute-force. However, I need to do this as quick as possible.

adj_mat = sparse(from_nodes, to_nodes, 1, s, s); 

Is there a way I can to this using the adjacency matrix? Can I do it more efficiently using the to/from list?

What I do now is finding the indices for the nodes connected to the chosen line, then search through the entire list of to-from nodes and finding all lines where either the to/from element is equal to one of the nodes of the chosen line. Then I use the new list of nodes and search through the entire to/from list, searching for these nodes again.

The code I use now looks something like this:

% tempBranch = the branches connected to the list of the current branches
k = 1;
for i = 1:nnz(nodeList)   % number of after step X-1 (for X=0 this is 
                          % equal to the nodes connected to the chosen line
    for j = 1:n           % n = number of lines
        if branchList(j,1) == nodeList(i) || branchList(j,2) == nodeList(i)
            tempBranch(k) = j;
            k = k + 1;
        end
    end
end

Thank you!

0 Comments

John Doe

Products

No products are associated with this question.

1 Answer

Answer by John Doe on 2 May 2013
Accepted answer

I have found a good answer to my question above (Thanks to Dr_Sam!).

1: Add 1 on the diagonal of the matrix A.

2: Build a vector v of all 0, excepted on the components i and j, where you put 1.

3: Compute A^k*v. All the nodes for which the entry is non-zero are within k edges from the two starting points (remark that the value of the entry is the number of k-paths!).

1 Comment

John Doe on 2 May 2013

I know I posted an answer to my own question. As I found a good solution, I believe it's the right thing to do. If I should not do this, please let me know, and I will remove it!

John Doe

Contact us