尽管有无穷大规则，但如何仅获得稀疏图的连通分量的偏心率？

Question

我有一个 scipy 压缩稀疏行 (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

由于图形偏心率是最大的最短路径距离，因此使用它可能更容易和更快 scipy 稀疏矩阵运算：

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

尽管有无穷大规则，但如何仅获得稀疏图的连通分量的偏心率？

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

python

graph-theory

data-analysis

networkx

connected-components