Single-pass top-N subgraph centrality of graphs via subspace projections

Subgraph centrality is a widely used centrality measure to rank the the importance of vertices in graphs. Due to the cubic cost of matrix diagonalization, subgraph centrality scores are typically approximated via projection onto an invariant subspace computed by a Krylov subspace eigenvalue solver. However, for dynamically evolving graphs or graphs whose corresponding adjacency matrix does not fit in the system memory, the application of memory-bound Krylov subspace eigenvalue solvers can be expensive. In this paper, we propose an algorithm to approximately identify the most influential nodes of networks under the constraint that each entry of the corresponding adjacency matrix is loaded only once. To achieve this, the algorithm parses the graph one subgraph at a time and accumulates previously processed graph information via updating a partial spectral factorization through a Rayleigh–Ritz projection. Several options to set the Rayleigh–Ritz subspace are discussed while numerical experiments performed on real-world graph datasets verify the effectiveness of the proposed algorithm. In particular, one of the approaches discussed in this paper incurs only linear complexity with respect to the update size.