Analytical study of resistance distance and Kirchhoff index under edge perturbations in weighted graphs

Muhammad Shoaib Sardar

Chaos, Solitons & Fractals, 2025, vol. 199, issue P3

Abstract: Let G=(V,E) be a connected, undirected graph with unit edge weights. Let G̃ be the graph obtained by perturbing the weight of a single edge [u,v]∈E by an amount Δwuv, so that its new weight becomes 1+Δwuv, while all other edge weights remain unchanged. In this paper, we analyze the effect of such localized edge perturbations on the resistance distance and Kirchhoff index of G̃, using matrix perturbation theory and the Woodbury identity. We derive closed-form expressions for the perturbed resistance distance r̃ij and perturbed Kirchhoff index Kf(G̃), providing analytical insight into the global impact of local structural changes. Through extremal analysis on complete and path graphs, we establish tight bounds for Kf(G̃) under single-edge perturbations and derive first-order sensitivity approximations to quantify the influence of individual edge weights. Building on this foundation, we propose the Max-Kirchhoff Impact Edge Detection (MKIED) technique to locate edges that have the greatest influence on the Kirchhoff index. Experiments on real-world networks, including Facebook, the Karate Club, and Les Miserables, illustrate the method’s efficacy in identifying structurally significant edges, frequently correlating to bridges or hub-hub connections. The results underscore the Kirchhoff index as an effective instrument for assessing structural vulnerability in complex networks.

Keywords: Weighted graphs; Resistance distance; Generalized inverse; Kirchhoff index; Graph perturbation; Edge sensitivity; Network robustness (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0960077925009105
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:chsofr:v:199:y:2025:i:p3:s0960077925009105

DOI: 10.1016/j.chaos.2025.116897

Access Statistics for this article

Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros

More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().