Complex non-backtracking matrix for directed graphs
Keishi Sando, Hideitsu Hino · 2025
Read Complex non-backtracking matrix for directed graphs by Keishi Sando, Hideitsu Hino (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-12503.txt.
Introduction
Keishi Sando and Hideitsu Hino put forward a new matrix for maps where links run one way, such as follows or citations. A matrix turns a map into a grid of numbers that tools can read for clusters. Two older grids each miss part of the tale: one keeps link sense but allows steps that double back, and one bars back-steps but drops link sense. The new grid joins the strengths of both.
The pair show how their grid ties to the older sense-keeping grid. They also show it shares key traits with the back-step-free grid for two-way maps. Most of all, the grid holds cluster clues for sparse one-way maps, where links are few. Such maps are the hard case in real data. The work gives map analysts a sharper lens for thin, one-way webs.
Catalog record
| CREATOR | Keishi Sando, Hideitsu Hino |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-12503
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Complex non-backtracking matrix for directed graphs Keishi Sando, Hideitsu Hino Abstract Graph representation matrices are essential tools in graph data analysis. Recently, Hermitian adjacency matrices have been proposed to investigate directed graph structures. Previous studies have demonstrated that these matrices can extract valuable information for clustering. In this paper, we propose the complex non-backtracking matrix that integrates the properties of the Hermitian adjacency matrix and the non-backtracking matrix. The proposed matrix has similar properties with the non-backtracking matrix of undirected graphs. We reveal relationships between the complex non-backtracking matrix and the Hermitian adjacency matrix. Also, we provide intriguing insights that this matrix representation holds cluster information, particularly for sparse directed graphs. directed graphs; Hermitian adjacency matrix; non-backtracking matrix; spectral clustering. 1 Introduction In network analysis, various matrix representations have been developed to investigate the structural properties of the corresponding network, among which the non-backtracking (NBT) matrix is one such representation. The NBT matrix is well-known for its relationship with the Ihara zeta function [ 15 ] defined as an infinite product over equivalence classes of primitive cycles. It was shown in [ 15 , 36 ] that, for regular graphs, the reciprocal of the Ihara zeta function can be expressed as a polynomial related to the adjacency matrix. The relation between the zeta function and the determinant of the NBT matrix was elucidated in [ 12 ] , extended to irregular graphs in [ 3 ] , and an elementary proof was provided in [ 35 ] . The connection between the polynomial and the determinant of the NBT matrix, via the Ihara zeta function, is known as the Ihara’s formula. Not limited to undirected graphs, variants of Ihara’s formula have been studied in various contexts such as directed [ 37 ] , weighted [ 18 , 19 ] settings. The NBT matrix and matrices derived from the NBT matrix can reveal graph structures through their spectra [ 16 , 27 ] and are also utilized for graph clustering problem [ 20 , 28 , 32 , 4 , 10 ] , node centrality computation [ 24 , 9 , 39 , 38 ] and graph isomorphism problem [ 27 ] . Methods developed for these problems have also found applications in other fields, such as the analysis of epidemic dynamics [ 34 , 29 ] . To investigate graph structures, research on the spectra of undirected graphs has been conducted for a long time. Several characteristics of undirected graphs, including the number of connected components, bipartite structure, and diameter, have well-established relationships with eigenvalues of matrices [ 5 ] . In contrast, the study of eigenvalues in directed graphs remains relatively underexplored. One of the reasons is that the adjacency matrix of directed graphs, being asymmetric, typically yields complex eigenvalues, complicating the analysis. To address this challenge while preserving the intrinsic information of directed graphs, the Hermitian adjacency matrices have been introduced in [ 11 , 22 ] . Basic properties of the Hermitian adjacency matrices are discussed in [ 11 ] , and Hermitian energies, defined as the absolute sum of eigenvalues, were studied in [ 22 ] . Hermitian adjacency matrices have been used in clustering problems, especially for spectral clustering. For undirected graphs, the traditional objective is to identify clusters that are densely connected internally and sparsely connected between clusters. Although these methodologies can be applied to directed graphs by symmetrization [ 33 ] , these may fail to capture valuable structures derived from directed information. To address this, spectral clustering methods for directed graphs based on a Hermitian adjacency matrix have recently been proposed. In [ 6 ] , their proposed algorithm was evaluated using the directed stochastic block model. The directional relationships between clusters were formulated as a graph cut problem in [ 21 ] . In [ 13 ] , they derived an efficient algorithm by utilizing the property that the employed Hermitian matrix is both Hermitian and skew-symmetric, and evaluated the flow imbalance in directed graphs. In contrast to the previously mentioned Hermitian adjacency matrices, where complex values are determined by the edge connections between vertex pairs, a variant of the Hermitian adjacency matrix that incorporates the cluster structure into its definition is proposed in [ 23 ] , along with an iterative algorithm designed for cluster estimation using this variant. In certain conditions involving undirected graphs, it has been observed that methods derived from the adjacency matrix yields unreliable outcomes. For instance, in node clustering on sparse graphs, these methods often result in misidentified clusters. Moreover, in node centrality, the presence of hub vertices causes the importance to concentrate on a few vertices, making it difficult to distinguish between the remaining vertices. It has been reported that the NBT walks and the NBT matrix can mitigate these issues [ 20 , 28 , 24 , 2 ] , whereas few studies have aimed at elucidating its properties for both undirected and directed graphs, and its relationship with the Hermitian adjacency matrix has not yet been established. The issue arising from methods derived from the adjacency matrix under specific conditions, as previously mentioned, is likely to also occur with the Hermitian adjacency matrix for directed graphs as well. We demonstrate this in Section 4 through a numerical experiment. In this work, as a step toward developing a method that can be robustly applied across various situations, we introduce a complex non-backtracking (CNBT) matrix for directed graphs that incorporates characteristics of both the Hermitian adjacency matrix and the NBT matrix. Our matrix representation exhibits favorable properties, analogous to the relationship between the adjacency matrix and the NBT matrix in undirected graphs. Additionally, we show through experiments that in the node clustering problem, spectral clustering based on our matrix performs effectively in scenarios where methods based on the Hermitian adjacency matrix lead to misclassification. The rest of this paper is organized as follows. In Section 2 , we fix notations and give basic properties on NBT walks. Section 3 is dedicated to the main results, which corroborate the validity of the proposed non-backtracking matrix. Additionally, in Section 4 , we demonstrate that our clustering algorithm outperforms an existing method when the underlying graph is sparse. This result further supports the usefulness of our definition. In Section 5 , we give a conclusion on this paper. 2 Preliminaries 2.1 Notations Throughout this paper, let G=(V,E) denotes a directed simple graph without self-loops. We assume that the vertices of G are indexed, and we use each vertex and its corresponding index interchangeably. For an arbitrary directed edge e\in E , let i_{e},t_{e}\in V be the initial and terminal vertex of e , respectively. In this paper, the symbol i is used in the following ways: i_{e} denotes the initial vertex of a directed edge e . When used alone or as a subscript, i serves as an index. The imaginary unit is represented as \sqrt{-1} . When a directed edge e is oriented from u\in V to v\in V , we use e=\overrightarrow{uv} . Its inverse, the directed edge from v to u , is denoted by e^{-1}=\overrightarrow{vu} . An undirected edge between u and v is represented as uv~(=vu) . For any digraph G ,