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

Abstract

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.

Keywords

• Hexagonal model
• Laplacian polynomial
• decomposition theorem
• GMFPT