Walks and eccentricity, graph theory

Hi, i have an adjacency matrix where Aij denotes the number of edges from vi to vj, edges going out from the vi gives the elements in the first row and now of the matrix and now i want to:

• first, write a function exwalk(A) compute a matrix containing the number of walks between vi and vj in exactly k steps.
• use exwalk(A) to create a function maxwalk(A, k) compute the number of walks in at most k steps.
• write a function eccentricities(A) compute a list of ecc(v) eccentricities for all vertices.

Answer 1

[Jaynik]

Hi,

1. To calculate the number of walks of exactly k steps, you just need to multiply the Adj matrix k times.
2. Once you have the exwalk, you can define the maxwalk function as follows:

function W = maxwalk(Adj, k)
    n = size(Adj, 1);
    W = zeros(n);
    for i = 1:k
        W = W + exwalk(Adj, i);
    end
end

3. For the eccentricity calculation, you can use the Floyd Warshall algorithm to find the shortest path between all the nodes and get the max distance for each.

function ecc = eccentricities(A)
    % Compute the shortest path lengths using the Floyd-Warshall algorithm
    D = floydWarshall(A);
    ecc = max(D, [], 2);
end

You will need to define the floydWarshall function on your own.

Hope this helps!