Abstract:In case of sparse graphs, relation between the real eigenvalues of the non-backtracking matrix and those of the non-backtracking transition probability matrix is considered with respect to vertex clustering. For this purpose, the random walk along the non-backtracking graph is considered, the vertices of which are the bioriented edges, and the adjacency relation depends on whether the random walk goes through the oriented edges with the rule of ``not going back in the next step''. This is encoded in the non-backtracking matrix that is the adjacency matrix of the non-backtracking graph. The structural real eigenvalues of the transition probability matrix are related to the constant multiples of the non-backtracking one, the concordance of which indicates the existence of a sparse stochastic block model behind the graph. ``Inflation--deflation'' techniques are also developed for clustering the vertices of the original graph together with real world applications.
From: Marianna Bolla DSc [view email]
[v1]
Tue, 30 Dec 2025 19:38:49 UTC (19 KB)
[v2]
Wed, 28 Jan 2026 19:00:28 UTC (20 KB)
[v3]
Sun, 15 Feb 2026 18:08:26 UTC (25 KB)
[v4]
Sun, 24 May 2026 09:05:42 UTC (59 KB)
[v5]
Mon, 24 Aug 2026 09:58:40 UTC (61 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。