Как получить второе наименьшее собственное значение матрицы Лапласа сложной сети с питоном?

Question

Я пытаюсь вычислить второе наименьшее собственное значение матрицы Лапласа сложной сети (с 10000 узлами) с помощью Python, используя режим инверсии сдвига, вот код:

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]; наименьшее собственное значение равно нулю в точности станка, а второе наименьшее - нет.