How can I get the eccentricity of only the connected components of a sparse graph despite the infinity rule?

Question

I have a scipy Compressed Sparse Row (CSR) matrix from which I am trying to extract the eccentricity to see the average distance the information travels. Unfortunately I keep getting infinity when using networkx after transforming it into a networkx graph using : networkx.convert_matrix.from_scipy_sparse_matrix (https://networkx.github.io/documentation/latest/reference/generated/networkx.convert_matrix.from_scipy_sparse_matrix.html)

Is there a way I can convert the set of labels that is produced from the connected components back to their original values and then perform individual eccentricity formulae on them?

Answer 1

Since graph eccentricity is the maximum shortest path distance, its probably just easier and faster to use scipy sparse matrix operations:

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