python - 如何用python获得复杂网络的拉普拉斯矩阵的第二小特征值？

Question

我正在尝试使用移位反转模式使用python计算复杂网络（具有10000个节点）的拉普拉斯矩阵的第二小的特征值，这里是代码：

import numpy as np
import networkx as nx
from scipy import sparse
G = nx.watts_strogatz_graph(10000,4,0.1)
degree_dict = nx.degree(G)
degree_list = []
for i in degree_dict:
    degree_list.append(degree_dict[i])
lap_matrix = sparse.diags(degree_list, 0)-nx.adjacency_matrix(G)
eigval, eigvec = sparse.linalg.eigsh(lap_matrix, 2, sigma=0, which='LM')
second_eigval = eigval[1]

运行上面的代码时，我得到：

RuntimeError: Factor is exactly singular

错误是否意味着拉普拉斯矩阵是奇异的？关于我应该如何进行的任何想法？有没有其他方法来计算这个第二小的特征值（使用 Matlab 或任何其他编程语言）？

Answer 1

你的代码对我有用（SciPy 1.0.0）几乎和写的一样，除了我简化了degree_list（在你的版本中抛出了 KeyError ）

import numpy as np
import networkx as nx
from scipy import sparse

G = nx.watts_strogatz_graph(10000,4,0.1)
degree_dict = nx.degree(G)
degree_list = [x[1] for x in degree_dict]
lap_matrix = sparse.diags(degree_list, 0)-nx.adjacency_matrix(G)
eigval, eigvec = sparse.linalg.eigsh(lap_matrix, 2, sigma=0, which='LM')

现在 eigval 是[1.48814294e-16, 4.88863211e-02]; 在机器精度内最小的特征值为零，但第二小的不是。