0

下午好，图论中一个相对知名的数学定理（参见 Bauer 和 Jost 的“Bipartite and Neighborhood Graphs and the Spectrum of the Normalized Graph Laplace Operator”）指出，归一化拉普拉斯算子的谱总是有界当且仅当图是二分图时，才能达到上界。我正在使用 Networkx 并且拉普拉斯谱（由 Networkx 实用程序生成的数组）返回的值远大于 2。对于下面的示例，我得到的最大特征值是 18.137。该图不是二分图，因此最大特征值应严格小于 2。这是代码示例：

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

我知道这个 Networkx 函数很可能使用拉普拉斯谱而不是归一化拉普拉斯谱。但是，由于它们是“相似”（在数学意义上）矩阵，它们应该具有相同的特征值。我哪里错了？我可能正在做一些愚蠢的事情，我只是没有看到。

4

2 回答 2

2

在networkx中，您正在寻找的拉普拉斯算子称为“normalized_laplacian”。这两个定义给出了不具有相同特征值的矩阵。维基百科页面https://en.wikipedia.org/wiki/Laplacian_matrix有一个不错的讨论。

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])
于 2016-02-29T03:11:27.617 回答
1
于 2016-02-28T23:55:05.850 回答