Eigenvalues for a 400x400 normalized laplacian of a graph

In summary, a 400x400 normalized laplacian of a graph is a matrix representation of a graph with 400 nodes, capturing its structure and connectivity. Eigenvalues are specific values that satisfy an equation involving this matrix and represent the importance of each node in the graph. They can be calculated using mathematical algorithms and provide information about the graph's properties and can be used for identifying clusters or communities within the graph. Eigenvalues can also be applied to other types of graphs, not just those with a 400x400 normalized laplacian representation.
  • #1
kosmos
11
0
This is related to spectral graph theory. I am getting the following eigenvalues for a 400x400 matrix which is a normalized laplacian matrix of a graph. The graph is not connected. So why am i getting a> a negative eigenvalue. b> why is not second eigenvalue 0? ... I used colt(java) and octave to generate the eigenvalues and get the same eigenvalues from both.

-96.40542543750111
0.9999999999996338
0.9999999999999974
0.9999999999999979
0.9999999999999981
0.9999999999999983
0.9999999999999984
0.9999999999999984
0.9999999999999984
0.9999999999999986
0.9999999999999987
0.9999999999999988
0.9999999999999988
0.9999999999999988
0.9999999999999988
0.9999999999999988
0.9999999999999988
0.9999999999999988
0.9999999999999989
0.999999999999999
0.999999999999999
0.999999999999999
0.999999999999999
0.999999999999999
0.999999999999999
0.9999999999999991
0.9999999999999991
0.9999999999999991
0.9999999999999991
0.9999999999999991
0.9999999999999992
0.9999999999999992
0.9999999999999992
0.9999999999999992
0.9999999999999992
0.9999999999999992
0.9999999999999993
0.9999999999999993
0.9999999999999993
0.9999999999999993
0.9999999999999993
0.9999999999999993
0.9999999999999993
0.9999999999999993
0.9999999999999994
0.9999999999999994
0.9999999999999994
0.9999999999999994
0.9999999999999994
0.9999999999999994
0.9999999999999994
0.9999999999999994
0.9999999999999994
0.9999999999999996
0.9999999999999996
0.9999999999999996
0.9999999999999996
0.9999999999999996
0.9999999999999996
0.9999999999999996
0.9999999999999997
0.9999999999999997
0.9999999999999997
0.9999999999999997
0.9999999999999997
0.9999999999999997
0.9999999999999997
0.9999999999999997
0.9999999999999997
0.9999999999999998
0.9999999999999998
0.9999999999999998
0.9999999999999998
0.9999999999999999
0.9999999999999999
0.9999999999999999
0.9999999999999999
0.9999999999999999
0.9999999999999999
0.9999999999999999
0.9999999999999999
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000002
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000004
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000007
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.0000000000000009
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.000000000000001
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000013
1.0000000000000016
1.0000000000000016
1.0000000000000016
1.0000000000000016
1.0000000000000016
1.0000000000000016
1.0000000000000016
1.0000000000000016
1.0000000000000018
1.0000000000000018
1.0000000000000018
1.0000000000000018
1.0000000000000018
1.0000000000000018
1.000000000000002
1.000000000000002
1.000000000000002
1.000000000000002
1.000000000000002
1.0000000000000022
1.0000000000000022
1.0000000000000022
1.0000000000000022
1.0000000000000022
1.0000000000000022
1.0000000000000022
1.0000000000000024
1.0000000000000024
1.0000000000000027
1.0000000000000027
1.0000000000000027
1.0000000000000027
1.000000000000003
1.3333333333333321
1.3333333333333324
1.3333333333333328
1.3333333333333333
1.333333333333334
1.3333333333333344
1.345014696576227
1.4999999999999982
1.4999999999999982
1.4999999999999984
1.4999999999999991
1.4999999999999991
1.4999999999999993
1.4999999999999996
1.5
1.5
1.5000000000000002
1.5000000000000004
1.5000000000000004
1.5000000000000004
1.5000000000000007
1.500000000000001
1.5000000000000013
1.5000000000000018
1.5000000000000024
1.5000000000000027
1.5000000000000029
1.500000000000003
1.5604107409249577
1.9999999999999971
1.9999999999999978
1.9999999999999982
1.9999999999999984
1.9999999999999987
1.999999999999999
1.9999999999999991
1.9999999999999998
2.0
2.0
2.0
2.0000000000000004
2.0000000000000004
2.0000000000000004
2.0000000000000004
2.0000000000000004
2.0000000000000004
2.0000000000000004
2.000000000000001
2.000000000000001
2.000000000000001
2.000000000000001
2.000000000000001
2.0000000000000013
2.0000000000000013
2.0000000000000013
2.0000000000000013
2.0000000000000013
2.0000000000000018
2.0000000000000018
2.0000000000000018
2.0000000000000018
2.0000000000000018
2.0000000000000018
2.0000000000000018
2.0000000000000018
2.0000000000000018
2.0000000000000018
2.000000000000002
2.000000000000002
2.000000000000002
2.000000000000002
2.000000000000002
2.000000000000002
2.000000000000002
2.0000000000000027
2.0000000000000027
2.0000000000000027
2.0000000000000027
2.0000000000000027
2.0000000000000027
2.0000000000000027
2.000000000000003
2.000000000000003
2.000000000000003
2.000000000000003
2.0000000000000036
2.0000000000000036
2.0000000000000036
2.0000000000000036
2.0000000000000036
2.000000000000004
2.000000000000004
2.000000000000004
2.000000000000004
2.000000000000004
2.0000000000000044
2.0000000000000044
2.0000000000000044
2.0000000000000044
2.000000000000005
2.000000000000005
2.000000000000005
2.0000000000000058
2.0000000000000058
2.0000000000000058
2.000000000000006
2.000000000000007
2.000000000000007
2.000000000000008
2.000000000000008
2.000000000000008
2.0000000000000084
2.0000000000000107
 
Physics news on Phys.org
  • #2
Looks like a problem with the lowest index of a matrix or array.

In java 0 is the lowest index.
That is v[0] is the first element of an array v.

Did you perchance fill your matrix starting at index 1?
(Or did you use a math package that expects 1 as the lowest index?)
 
  • #3
Hi ... I used 0 as the index. Also exported my 400x400 matrix to a csv file and got the same
result using Octave too. So I guess there is nothing wrong with implementation. Something wrong with my matrix. But its symmetric ... I checked in the excel sheet.
 
  • #4
A property of the matrix is that all columns (or rows) should add to zero.
This is also the reason that zero should be an eigenvalue.

Do they?
 
  • #5
No they do not. But why should that be the case, because the diagonals of a normalized laplacian are all 1s. And rest of the cells are filled by -1/sqrt(degree_u*degree_v). So they need not add to -1. I am using this source for reference. www.math.ucla.edu/~butler/PDF/spectral1.pdf
 
Last edited by a moderator:
  • #6
Sorry, I was looking at the Laplacian matrix instead of the normalized Laplacian matrix.

Still, you should have the eigenvalue 0 with the eigenvector ##D^{-\frac 1 2}\textbf{1}##.
This is something you can verify by multiplying your matrix with this vector.
 
  • #7
Oh yes... that will crosscheck my implementation to generate normLaplacian of the graph. Thanks! ... Let me try that and come back!
 
  • #8
The problem was with the reference I was using. It defined that entry is 1 whenever i==j and missed out the consition deg(i)!=0 ... thanks for your help!

But though I do get the 0 as eigenvalues but the first eigenvalue is still coming out to be negative. That is supposed to be a zero as I counted from the number of zero eigenvalues needed from the configuration of my graph. It comes zero when the number of nodes i s less but becomes negative when it raises.
 
  • #9
Perhaps you can reduce the matrix to a manageable size?
Say you select a few entries including an isolated vertex?
Check you still get a negative eigenvalue.

You could post the matrix then if you don't already see the problem yourself...
 

Related to Eigenvalues for a 400x400 normalized laplacian of a graph

1. What is a 400x400 normalized laplacian of a graph?

A 400x400 normalized laplacian of a graph is a mathematical representation of a graph with 400 nodes. It is a matrix that captures the structure and connectivity of the graph.

2. What are eigenvalues in relation to a 400x400 normalized laplacian of a graph?

Eigenvalues are the special values that satisfy a specific equation involving the normalized laplacian matrix. They represent the importance of each node in the graph and can be used to analyze the properties of the graph.

3. How are eigenvalues calculated for a 400x400 normalized laplacian of a graph?

Eigenvalues for a 400x400 normalized laplacian of a graph can be calculated using mathematical algorithms such as the power method or the QR algorithm. These algorithms find the characteristic polynomial of the matrix and then solve for its roots, which are the eigenvalues.

4. What information can be obtained from the eigenvalues of a 400x400 normalized laplacian of a graph?

The eigenvalues of a 400x400 normalized laplacian of a graph can provide information about the connectivity, structure, and properties of the graph. They can also be used to identify clusters or communities within the graph.

5. Can eigenvalues be used for graph analysis other than for a 400x400 normalized laplacian?

Yes, eigenvalues can be used for graph analysis in general. They are a powerful tool for understanding the structure and behavior of a graph, and can be applied to various types of graphs, not just those with a 400x400 normalized laplacian representation.

Hot Threads

Recent Insights

Back
Top