CODEWITHSUNDEEP
matlabgraph
Tom Kealy
Tom Kealy

Reputation: 2669

Creating a weight adjacency matrix

I need to assign weights to edges of a graph, from the following papers:

"Fast linear iterations for distributed averaging" by L. Xiao and S. Boyd "Convex Optimization of Graph Laplacian Eigenvalues" by S. Boyd

I have the adjacency matrix for my graph (a 50 by 50 matrix), with 512 non-zero values.

I also have a 256 by 1 vector with the optimal weights.

For the software I'm using, I need a 50 by 50 matrix with the weight of edge (i,j) in the relevant position of the adjacency matrix (and with the opposite sign for edge (j,i)).

My attempt is below, but I can't get it working.

function weights = construct_weight_mtx(weight_list, Adj)

weights = zeros(size(Adj));
positions = find(Adj);

for i=1:length(positions)/2
    if Adj(i) == 1
        weights(i) = weight_list(i);
    end
end

weights = weights - weights';

find(Adj) == find(weights);

end

Upvotes: 0

Views: 848

Answers (1)

beaker
beaker

Reputation: 16801

You're finding the nonzero positions in the original adjacency matrix, but you're finding all of them. To get around this, you then take only the first half of those positions. 

for i=1:length(positions)/2 ...

Unfortunately, this takes the indices from complete columns rather than just the positions below the diagonal. So if your matrix was all 1's, you'd be taking:

1 1 1 0 0 ...
1 1 1 0 0 ...
1 1 1 0 0 ...
...

instead of:

1 0 0 0 0 ...
1 1 0 0 0 ...
1 1 1 0 0 ...
...

To take the correct values, we just take the lower triangular portion of Adj and then find the nonzero positions of that:

positions = find(tril(Adj));

Now we have only the 256 positions below the diagonal and we can loop over all of the positions. Next, we need to fix the assignment in the loop:

for i=1:length(positions)
    if Adj(i) == 1   %// we already know Adj(i) == 1 for all indices in positions
        weights(i) = weight_list(i);   %// we need to update weights(positions(i))
    end
end

So this becomes:

for i=1:length(positions)
    weights(positions(i)) = weight_list(i);
end

But if all we're doing is assigning 256 values to 256 positions, we can do that without a for loop:

weights(position) = weight_list;

Note that the elements of weight_list must be in the proper order with the nonzero elements of the lower-triangular portion ordered by columns.

Completed code:

function weights = construct_weight_mtx(weight_list, Adj)

weights = zeros(size(Adj));
positions = find(tril(Adj));

weights(positions) = weight_list;

weights = weights - weights.';   %// ' is complex conjugate; not a big deal here, but something to know

find(Adj) == find(weights);   %// Not sure what this is meant to do; maybe an assert?

end

Upvotes: 1

Related Questions