Как я могу получить эксцентриситет только связанных компонентов разреженного графа, несмотря на правило бесконечности?

Question

У меня есть скудная матрица Compressed Sparse Row (CSR), из которой я пытаюсь извлечь эксцентриситет, чтобы увидеть среднее расстояние, которое проходит информация.К сожалению, я продолжаю получать бесконечность при использовании networkx после преобразования его в график networkx с помощью: networkx.convert_matrix.from_scipy_sparse_matrix (https://networkx.github.io/documentation/latest/reference/generated/networkx.convert_matrix.from_scipy_sparse_matrix.html)

Есть ли способ, которым я могу преобразовать набор меток, который создается из подключенных компонентоввернуться к исходным значениям, а затем выполнить для них индивидуальные формулы эксцентриситета?

Answer 1

Поскольку эксцентриситет графа является максимальным кратчайшим расстоянием, вероятно, проще и быстрее использовать операции с разреженными разреженными матрицами:

import numpy as np
from scipy.sparse.csgraph import connected_components, shortest_path
from scipy.sparse import csr_matrix

def sparse_component_eccentricity(graph, directed=False):

    n_components, labels = connected_components(csgraph=graph, directed=directed, return_labels=True)

    component_eccentricity = np.zeros(graph.shape[0])

    for icomp in range(n_components):
        subgraph_indices = np.where(labels == icomp)[0]
        subgraph = graph[subgraph_indices][:,subgraph_indices]
        dist_matrix = shortest_path(subgraph, directed=directed)
        component_eccentricity[subgraph_indices] = np.nanmax(dist_matrix, axis=1)
    return component_eccentricity