Multiplicative path weights reveal new network connectivity measures
Multiplicative Path Weights in Networks: From Katz Connectivity to Mean First-Passage Times
Social and Information Networks
Summary
Many systems like how diseases spread or how banks affect each other can be understood by looking at networks where the connections multiply along paths instead of just adding up. The authors study ways to measure how connected parts of these networks are using these multiplying connections. They extend known methods like Katz centrality to work in more cases and find formulas to understand how long it takes to reach one point from another in these networks. Their work also covers random connections and connects to well-known Markov chain results, giving new tools to analyze complex interactions.
What this means in practice
- •For financial risk managers: Assess the propagation of stress through interbank systems using new multiplicative connectivity measures to quantify systemic risks more accurately.
- •For epidemic modelers: Calculate transmission probabilities over networks by analyzing first-hit paths and multiplicative weights, aiding disease spread predictions.
Authors
Robbert van der Burg, Bernd Heidergott, Thao Le, Alessandro Zocca
Abstract
Signal dispersion, stress propagation in interbank systems, and transmission probabilities in epidemic and reliability models are all captured by studying paths on directed graphs where the path weight is defined as the product of its edge weights. Connectivity in such networks is naturally quantified by aggregating these multiplicative path weights across nodes. This paper provides a comprehensive treatise on connectivity and ranking measures based on multiplicative path weights. We demonstrate how standard all-path connectivity, such as the standard Katz centrality, can be extended beyond its classical spectral threshold. In addition, we derive closed-form expressions for connectivity based on first-hit paths and introduce a new version of Katz centrality. Furthermore, for random edge weights, we derive resolvent-based expressions for the first and second moments, alongside variance bounds, under a path-indexed coupling framework. Finite irreducible Markov chains are a subclass of the models studied, and we show that the scaled matrix of first-hit path probabilities is the probability-generating function for first-passage and return times, and that differentiation yields the classical first-passage times. Numerical examples illustrate the application of our results in a variety of settings.