Matrix Analysis of Hexagonal Model and Its Applications in Global Mean-First-Passage Time of Random Walks

Recent advances in graph-structured learning have demonstrated promising results on the graph classification task. However, making them scalable on huge graphs with millions of nodes and edges remains challenging due to their high temporal complexity. In this paper, by the decomposition theorem of Laplacian polynomial and characteristic polynomial we established an explicit closed-form formula of the global mean-first-passage time (GMFPT) for hexagonal model. Our method is based on the concept of GMFPT, which represents the expected values when the walk begins at the vertex. GMFPT is a crucial metric for estimating transport speed for random walks on complex networks. Through extensive matrix analysis, we show that, obtaining GMFPT via spectrums provides an easy calculation in terms of large networks.

Automated summary

Recent advances in graph-structured learning have shown promising results in graph classification, but scaling them on large graphs with millions of nodes and edges remains a challenge due to their high temporal complexity. This paper establishes an explicit closed-form formula for the global mean-first-passage time (GMFPT) in hexagonal models through the decomposition theorem of Laplacian polynomial and characteristic polynomial. Our method uses GMFPT to estimate transport speed for random walks on complex networks, and through matrix analysis, we demonstrate that obtaining GMFPT via spectrums allows for easy calculation in large networks.