Summary
International Conference on Emerging Technologies for Communications
2020
Session Number:O2
Session:
Number:O2-6
A Study on Estimating Effective Graph Resistance with Random Walk
Yuhei Nishi, Ryota Sakaguchi, Hiroyuki Ohsaki,
pp.-
Publication Date:2020/12/2
Online ISSN:2188-5079
PDF download
Summary:
In recent years, spectral properties of a network topology have been actively studied as means for analyzing the characteristics of a communication network as well as estimating its internal properties. Among several popular spectral measures (e.g., spectral radius, algebraic connectivity, and spectral gap), it has been known that effective graph resistance (EGR) is effective for estimating the robustness of a communication network against random failures. Although spectral measures are generally obtained from the adjacency matrix and the Laplacian matrix of the network topology, a few techniques for estimating spectral measures of a network topology from the trajectory of a random walk on the network have been proposed. Since EGR is given by the sum of reciprocals of all non-zero eigenvalues of the Laplacian matrix, conventional estimation techniques cannot be utilized to infer the EGR from the trajectory of a random walk. In this paper, we therefore propose a novel technique for estimating the EGR of a network topology from the trajectory (i.e., the sequence of visited nodes) of a random walk.