CODEWITHSUNDEEP
networkxgraph-theorycomputational-geometry
user5994810
user5994810

Reputation:

Unrealistic Eigenvalues in networkx

Good afternoon, A relatively well known mathematical theorem in graph theory (see the Introduction of "Bipartite and Neighborhood Graphs and the Spectrum of the Normalized Graph Laplace Operator" by Bauer and Jost) states that the spectrum of the normalized Laplace operator is always bounded from above by 2 and the upper bound is attained if and only if the graph is bipartite. I'm working with Networkx and the Laplacian spectrum (an array generated by Networkx utilities) is returning values far greater than 2. For the below example, the largest eigenvalue I am getting is 18.137. The graph is not bipartite so the largest eigenvalue should be strictly less than 2. Here is a sample of the code:

import networkx as nx

Graph=nx.karate_club_graph() 

print nx.laplacian_spectrum(Graph)

1.137978592311377107e-15,
4.685252267013915728e-01,
9.092476638033122338e-01,
1.125010718244666030e+00,
1.259404110121709719e+00,
1.599283075429581258e+00,
1.761898621144031507e+00,
1.826055209825464098e+00,
1.955050447337369102e+00,
1.999999999999998446e+00,
1.999999999999999556e+00,
2.000000000000000000e+00,
2.000000000000000444e+00,
2.000000000000001332e+00,
2.487091734464515369e+00,
2.749157175276658815e+00,
3.013962966251617193e+00,
3.242067477421745725e+00,
3.376154092871075374e+00,
3.381966011250106874e+00,
3.472187399726446522e+00,
4.275876820141818691e+00,
4.480007671029976102e+00,
4.580792668029516790e+00,
5.378595077669420910e+00,
5.618033988749897567e+00,
6.331592223669625596e+00,
6.515544628031584296e+00,
6.996197033107128149e+00,
9.777240952801486529e+00,
1.092106753013355558e+01,
1.330612231276679225e+01,
1.705517119099513224e+01,
1.813669597300440017e+01

I understand this Networkx function is most likely using the Laplacian spectrum and not the normalized Laplacian spectrum. However, since they are "Similar" (in the mathematical sense) matrices they should have the same eigenvalues. Where am I going wrong? I am may be doing something silly, I just don't see it.

Upvotes: 0

Views: 430

Answers (2)

Joel
Joel

Reputation: 23827

I think this is an issue of different people having different definitions for the Laplacian.

In Bauer and Jost:

the Laplace operator ∆ can be considered as ∆ =: I − P, where I denotes the identity and P is transition probability operator of a random walk (or sometimes called the Markov operator), respectively. We should point our here that the normalized graph Laplace operator ∆ is not exactly the one studied by Fan Chung [10]. However, both Laplace operators are unitarily equivalent and therefore have the same spectrum

In Chung's work,

L(u, v) = 1 if u = v, and 1/sqrt(d_u d_v) if u and v have an edge and 0 otherwise.

In Networkx,

The graph Laplacian is the matrix L = D - A, where A is the adjacency matrix and D is the diagonal matrix of node degrees.

I'll take Bauer and Jost's word that theirs is equivalent to what Fan Chung did (which I confess is not obvious to me at first glance). But I'm not at all convinced that what she did would have the same eigenvalues as D-A.

edit Aric's answer makes clear that this is the issue and networkx also has the normalized matrix you are looking for.

Upvotes: 1

Aric
Aric

Reputation: 25289

In networkx the Laplacian you are looking for is called "normalized_laplacian". The two definitions give matrices that don't have the same eigenvalues. The wikipedia page https://en.wikipedia.org/wiki/Laplacian_matrix has a decent discussion.

In [1]: import networkx as nx

In [2]: G = nx.karate_club_graph()

In [3]: from scipy.linalg import eigvalsh 

In [4]: eigvalsh(nx.laplacian_matrix(G).todense())
Out[4]: 
array([ -5.97438766e-15,   4.68525227e-01,   9.09247664e-01,
         1.12501072e+00,   1.25940411e+00,   1.59928308e+00,
         1.76189862e+00,   1.82605521e+00,   1.95505045e+00,
         2.00000000e+00,   2.00000000e+00,   2.00000000e+00,
         2.00000000e+00,   2.00000000e+00,   2.48709173e+00,
         2.74915718e+00,   3.01396297e+00,   3.24206748e+00,
         3.37615409e+00,   3.38196601e+00,   3.47218740e+00,
         4.27587682e+00,   4.48000767e+00,   4.58079267e+00,
         5.37859508e+00,   5.61803399e+00,   6.33159222e+00,
         6.51554463e+00,   6.99619703e+00,   9.77724095e+00,
         1.09210675e+01,   1.33061223e+01,   1.70551712e+01,
         1.81366960e+01])

In [5]: eigvalsh(nx.normalized_laplacian_matrix(G).todense())
Out[5]: 
array([  6.28463560e-16,   1.32272329e-01,   2.87048985e-01,
         3.87313233e-01,   6.12230540e-01,   6.48992947e-01,
         7.07208202e-01,   7.39957989e-01,   7.70910617e-01,
         8.22942852e-01,   8.64832945e-01,   9.06816002e-01,
         1.00000000e+00,   1.00000000e+00,   1.00000000e+00,
         1.00000000e+00,   1.00000000e+00,   1.00000000e+00,
         1.00000000e+00,   1.00000000e+00,   1.00000000e+00,
         1.00000000e+00,   1.10538084e+00,   1.15929996e+00,
         1.26802355e+00,   1.35177826e+00,   1.39310454e+00,
         1.41691585e+00,   1.44857938e+00,   1.49703011e+00,
         1.56950660e+00,   1.58333333e+00,   1.61190959e+00,
         1.71461135e+00])

Upvotes: 2

Related Questions