On the Stability of Network Indices Defined by Means of Matrix Functions

Stefano Pozza, Francesco Tudisco

Abstract

In network science, matrix functions such as the exponential and the resolvent of the adjacency matrix are widely used to quantify node centrality and communicability. However, the computational cost and sensitivity of these measures to network perturbations remain significant challenges. This paper establishes a theoretical framework using Faber polynomials to prove that the impact of edge perturbations on matrix-function-based indices decays exponentially with the shortest-path distance from the site of the change. We further propose a modified Lanczos method that simultaneously computes centrality scores and approximates shortest-path distances, providing a robust and efficient approach for analyzing large-scale, dynamic networks.

Introduction

Ranking nodes by their importance is a fundamental task in network analysis. While local measures like degree centrality are computationally trivial, they fail to capture the global structural properties of a network. To address this, researchers employ matrix functions $f(A)$, where $A$ is the adjacency matrix. These functions account for paths of all lengths, offering a more nuanced view of connectivity.

Despite their utility, these global measures face two primary hurdles: the high computational overhead for massive graphs and the inherent noise or dynamism in real-world data. If a single edge is added or removed in a remote part of a network, it is often unclear whether the entire ranking must be recomputed. This research provides a rigorous mathematical guarantee that such global measures are, in fact, locally stable.

Theoretical Framework: Faber Polynomials and Decay Bounds

The core of the paper's theoretical contribution lies in bridging graph theory with numerical linear algebra through the use of Faber polynomials. Unlike standard power series, which are typically restricted to disks, Faber polynomials allow for the expansion of matrix functions over the field of values of the adjacency matrix. This is particularly useful for complex graph structures where the eigenvalues do not neatly fit into simple geometric shapes.

By leveraging this expansion, the authors derive explicit upper bounds for the variation in centrality scores following a perturbation. The primary result (Theorem 5.3) demonstrates that the change in a node's score is bounded by a term that shrinks exponentially as the shortest-path distance from the perturbed edges increases. This "locality of global measures" suggests that the ripple effect of a network change dies out rapidly, preserving the relative rankings of distant nodes.

Algorithmic Innovation: The Modified Lanczos Method

To translate these theoretical bounds into practical tools, the authors propose an enhancement to the standard Lanczos algorithm, a common Krylov subspace method for computing matrix functions.

The "Modified Lanczos Method" exploits the way the algorithm explores the graph. As the Lanczos process iterates, it effectively traverses the graph one step at a time. The authors observed that the iteration count at which a node first appears with a non-zero component in a Lanczos vector corresponds exactly to its shortest-path distance from the starting node. By monitoring the sparsity patterns of these vectors, the algorithm can compute all-pairs shortest-path distances "for free" while simultaneously calculating the centrality scores. This dual-purpose routine significantly reduces the total computational burden for dynamic network analysis.

Experimental Validation

The theoretical bounds and the efficiency of the modified Lanczos method were validated across several synthetic and real-world datasets:

  • Synthetic Models: A "Bridge" graph was used to verify basic perturbation logic, while a logistic preferential attachment model demonstrated the stability of the "elite" nodes.
  • Real-World Networks: The authors tested the approach on the London Transportation Network (369 stations), the Gnutella peer-to-peer network (6,300 nodes), and the Facebook "friends circles" dataset (4,038 nodes).
  • Collaboration Networks: The GRQC (General Relativity) and Erdős networks were used to represent co-authorship structures.

In experiments on the London and Gnutella networks, the observed decay in ranking changes closely followed the predicted exponential bounds. Furthermore, the Lanczos-based distance approximation proved highly effective, identifying the majority of shortest-path distances within 11 to 17 iterations, even in networks with thousands of nodes.

Discussion and Key Insights

The research highlights a critical phenomenon: the Stability of the Elite. In many real-world networks, noise and frequent edge changes occur among marginal, low-importance nodes. Because these nodes are typically distant from the network's core "hubs," the top of the centrality leaderboard remains remarkably stable. This justifies the use of global matrix functions even in highly volatile environments.

However, some limitations remain. While the derived bounds correctly capture the rate of exponential decay, the absolute values of these bounds are often several orders of magnitude larger than the actual observed variations. Future work is needed to find tighter constants. Additionally, while the current framework applies to general directed networks, specialized scores like HITS (Hubs and Authorities) involve symmetric block matrices that require further specific analysis.

Conclusion

This paper provides the mathematical foundation for understanding why global network indices are resilient to local changes. By proving exponential decay through Faber polynomials and providing an efficient computational path via the Lanczos method, the authors offer a robust framework for the stable analysis of large-scale, evolving networks.

Summary updated

Abstract

Identifying important components in a network is one of the major goals of network analysis. Popular and effective measures of importance of a node or a set of nodes are defined in terms of suitable entries of functions of matrices $f(A)$. These kinds of measures are particularly relevant as they are able to capture the global structure of connections involving a node. However, computing the entries of $f(A)$ requires a significant computational effort. In this work we address the problem of estimating the changes in the entries of $f(A)$ with respect to changes in the edge structure. Intuition suggests that, if the topology, or the overall weight, of the connections in the new graph $\tilde G$ is not significantly distorted, relevant components in $G$ maintain their leading role in $\tilde G$. We propose several bounds giving mathematical reasoning to such intuition and showing, in particular, that the magnitude of the variation of the entry $f(A)_{k\ell}$ decays exponentially with the shortest-path distance in $G$ that separates either $k$ or $\ell$ from the set of nodes touched by the edges that are perturbed. Moreover, we propose a simple method that exploits the computation of $f(A)$ to simultaneously compute the all-pairs shortest-path distances of $G$, with essentially no additional cost. The proposed bounds are particularly relevant when the nodes whose edge connection tends to change more often or tends to be more often affected by noise have a marginal role in the graph and are distant from the most central nodes.
BibTeX
@article{pozza2018stability,
  author = {Stefano Pozza and Francesco Tudisco},
  title = {{On the Stability of Network Indices Defined by Means of Matrix Functions}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2018},
  doi = {10.1137/17m1133920},
}
Figure