Быстрое вычисление центральности собственного вектора занимает слишком много времени в сети x

Question

Я использую networkx для вычисления центральности собственного вектора. Проблема в том, что это занимает слишком много времени (уже работает около 6 часов). Есть ли более быстрый способ получить результаты?

На графике около 200 000 узлов и 60 000 000 ребер.

Answer 1

Глядя на исходный код, networkx.algorithms.centrality.eigenvector использует метод мощности для поиска ведущего собственного вектора.

Если вы придерживаетесь networkx, используйте это, как заметил Джоэл:

eigenvector_centrality_numpy

centrality = nx.eigenvector_centrality_numpy(G)

В качестве альтернативы:

Вы можете использовать scipy.sparse.linalg.eigs, который использует ARPACK, и запросить только 1 собственный вектор длябыть возвращен.

Пример игрушки:

import scipy.sparse as sparse

X = np.array() # dimensions 200000 by 200000 as the adjacency
# Note: k=1 and you request the Largest real.
vals, vecs = sparse.linalg.eigs(X, k=1, which='LR')

В любом случае, 2000000 на 200000 велики, и в зависимости от разреженности и природы матрицы алгоритм может занять много времени.Вам также понадобится много процессора и оперативной памяти.

Дополнительный совет для networkx.algorithms.centrality.eigenvector:

Если вы придерживаетесь networkx, попробуйте ослабить допуск:

eigenvector_centrality(G, max_iter=100, tol=1e-06, nstart=None, weight=None)

Попробуйте установить tol=1e-04 или даже tol=1e-03

Answer 2

Попробуйте использовать eigenvector_centrality_numpy .Из документации:

Этот алгоритм использует метод разреженного собственного значения SciPy (ARPACK) для нахождения наибольшей пары собственных значений / собственных векторов.

Таким образом, будет выполняться расчет serafeim счуть-чуть дополнительной обработки.