Ask Your Question
0

How to find the laplacian matrix of a weighted directed graph

asked 2017-10-31 08:16:30 +0100

anonymous user

Anonymous

How to find the laplacian matrix of a weighted directed graph? Please explain with an example

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
1

answered 2017-11-01 10:00:14 +0100

B r u n o gravatar image
sage: G = DiGraph(3, weighted=True)
sage: G.add_edges([(0,2,4), (1,2,6),(0,1,2)])
sage: G.laplacian_matrix()

[ 0 -2 -4]
[ 0  2 -6]
[ 0  0 10]
edit flag offensive delete link more
0

answered 2017-11-01 23:37:51 +0100

dan_fulea gravatar image

This is an alternative longer answer...

One problem may be, depending on the situation, to initialize and/or declare the "weight data" for the di(rected )graph. The following assumes that the weights are given in a matrix A, then it constructs in one line the corresponding digraph. The method laplacian_matrix, applied on it gives the result. Sample code follows. Instead of typing myself the entries of a matrix, there will be a random generation.

import random
random.seed( 20171101 )

def myrandomizer():
    if random.uniform( 0,1 ) < 0.7:
        return 0
    return random.choice( [ 1..10 ] )

N = 8
A = matrix( QQ, N, N, [ myrandomizer() for _ in range(N^2) ] )
print A

D = DiGraph( A, format='weighted_adjacency_matrix' )
# D.show()    # decomment to show...

The only important line above, given A is the one with D = DiGraph( A, format='weighted_adjacency_matrix' ) . (Without specifying the format, sage is trying to guess the format, and it rather generates multiple edges between two vertices for a (weight) entry $\ge 2$.)

The print A line gives the reproducible random matrix

[ 7  0  0  0  0  3  2  0]
[ 0  0  0  0  7 10  0  0]
[ 0  0  0  0  0  6  3  0]
[10  0  6  0  0  0  0  0]
[ 8  7  9  3  0  3  0  9]
[ 0  0  5  0  0  0  0  0]
[ 0  5  0  0  0  0  0  2]
[ 0  0  0  0  3  6  0  0]
sage:

In the given situation we can apply the following related methods:

sage: D.laplacian_matrix()
[ 18   0   0   0   0  -3  -2   0]
[  0  12   0   0  -7 -10   0   0]
[  0   0  20   0   0  -6  -3   0]
[-10   0  -6   3   0   0   0   0]
[ -8  -7  -9  -3  10  -3   0  -9]
[  0   0  -5   0   0  28   0   0]
[  0  -5   0   0   0   0   5  -2]
[  0   0   0   0  -3  -6   0  11]

sage: D.adjacency_matrix()
[1 0 0 0 0 1 1 0]
[0 0 0 0 1 1 0 0]
[0 0 0 0 0 1 1 0]
[1 0 1 0 0 0 0 0]
[1 1 1 1 0 1 0 1]
[0 0 1 0 0 0 0 0]
[0 1 0 0 0 0 0 1]
[0 0 0 0 1 1 0 0]

sage: D.weighted()
True

sage: D.weighted_adjacency_matrix()
[ 7  0  0  0  0  3  2  0]
[ 0  0  0  0  7 10  0  0]
[ 0  0  0  0  0  6  3  0]
[10  0  6  0  0  0  0  0]
[ 8  7  9  3  0  3  0  9]
[ 0  0  5  0  0  0  0  0]
[ 0  5  0  0  0  0  0  2]
[ 0  0  0  0  3  6  0  0]
sage:

Note that the laplacian matrix differs from minus the weighted adjacency matrix only on the diagonal. The diagonal entries are adjusted, so that all sums of the columns vanish. Some books define the laplacian so that the sums on the rows vanish.

edit flag offensive delete link more

Comments

Thanks for you answer. I have got the idea now.thanks

rewi gravatar imagerewi ( 2017-11-02 06:13:02 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-10-31 08:16:30 +0100

Seen: 1,280 times

Last updated: Nov 01 '17