# How to find the laplacian matrix of a weighted directed graph

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

edit retag close merge delete

Sort by » oldest newest most voted
sage: G = DiGraph(3, weighted=True)
sage: G.laplacian_matrix()

[ 0 -2 -4]
[ 0  2 -6]
[ 0  0 10]

more

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]

[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

[ 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.

more

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

( 2017-11-02 00:13:02 -0600 )edit