Hamming Graph Metrics: A Multi-Scale Framework for Structural Redundancy and Uniqueness in Graphs
R. Scott Johnson · 2025
Read Hamming Graph Metrics: A Multi-Scale Framework for Structural Redundancy and Uniqueness in Graphs by R. Scott Johnson (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-2510-23646.txt.
Introduction
R. Scott Johnson introduces Hamming Graph Metrics, a way to compare graphs by their connection patterns at every distance at once. Classic centrality scores rank how important single nodes are, but they miss whether a network's multi-scale wiring is unusual or redundant. That structural fingerprint matters for judging resilience and function, yet tools for it have been thin.
The framework encodes a graph as a stack of tables recording which node pairs sit exactly k steps apart, for every k. The distance between two graphs is then a Hamming-style count of mismatches across that stack. Johnson proves the measure ignores relabeling, behaves as a true metric, and stays stable when edges change, with explicit bounds. Around it he builds per-scale spectral summaries, node and graph-level dissimilarity scores, and extremal results. The package gives network scientists a principled ruler for structural difference.
Catalog record
| CREATOR | R. Scott Johnson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-23646
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hamming Graph Metrics: A Multi-Scale Framework for Structural Redundancy and Uniqueness in Graphs R. Scott Johnson Abstract Traditional graph centrality measures effectively quantify node importance but fail to capture the structural uniqueness of multi-scale connectivity patterns—critical for understanding network resilience and function. This paper introduces Hamming Graph Metrics (HGM) , a framework that represents a graph by its exact- k k reachability tensor ℬ G ∈ { 0 , 1 } N × N × D \mathcal{B}_{G}\in\{0,1\}^{N\times N\times D} with slices ( ℬ G ) : , : , 1 = A (\mathcal{B}_{G})_{:,:,1}=A and, for k ≥ 2 k\geq 2 , ( ℬ G ) : , : , k = 𝟏 [ ∑ t = 1 k A t > 0 ] − 𝟏 [ ∑ t = 1 k − 1 A t > 0 ] (\mathcal{B}_{G})_{:,:,k}=\mathbf{1}[\sum_{t=1}^{k}A^{t}>0]-\mathbf{1}[\sum_{t=1}^{k-1}A^{t}>0] (shortest-path distance exactly k k ). Guarantees. (i) Permutation invariance : d HGM ( π ( G ) , π ( H ) ) = d HGM ( G , H ) d_{\mathrm{HGM}}(\pi(G),\pi(H))=d_{\mathrm{HGM}}(G,H) for all vertex relabelings π \pi ;(ii) the tensor Hamming distance d HGM ( G , H ) := ∥ ℬ G − ℬ H ∥ 1 = ∑ i , j , k [ ( ℬ G ) i j k ≠ ( ℬ H ) i j k ] d_{\mathrm{HGM}}(G,H):=\|\mathcal{B}_{G}-\mathcal{B}_{H}\|_{1}=\sum_{i,j,k}\mathbf{1}\!\big[(\mathcal{B}_{G})_{ijk}\neq(\mathcal{B}_{H})_{ijk}\big] is a true metric on labeled graphs; and (iii) Lipschitz stability to edge perturbations with explicit degree-dependent constants (see “Graph-to-Graph Comparison” → \rightarrow “Tensor Hamming metric”; “Stability to edge perturbations”; Appendix A). For unlabeled graph comparison, one can apply HGM after graph canonization, or use an alignment-based variant (exponential worst-case cost). We develop: (1) per-scale spectral analysis via classical MDS on double-centered Hamming matrices D ( k ) D^{(k)} , yielding spectral coordinates and explained variances; (2) summary statistics for node-wise and graph-level structural dissimilarity; (3) graph-to-graph comparison via the metric above; and (4) analytic properties including extremal characterizations, multi-scale limits, and stability bounds. 1 Introduction 1.1 The Research Gap Graph centrality measures are fundamental tools for understanding network structure and identifying influential nodes across numerous domains including social networks, biological pathways, transportation infrastructure, and communication systems [ 5 ] . Traditional measures such as degree centrality, closeness centrality, and betweenness centrality have been extensively studied and applied for decades [ 1 , 2 ] . These classical metrics typically emphasize frequency, reachability, and efficiency of traversal within a network. Specifically, betweenness centrality quantifies how often a node participates in shortest paths between other nodes [ 3 ] , closeness centrality measures how quickly a node can reach other nodes [ 4 ] , and degree centrality simply counts how many direct connections a node possesses [ 5 ] . However, these conventional measures fail to capture an important aspect of network structure: the structural diversity or redundancy of connectivity patterns. This limitation is particularly significant when analyzing complex networks where understanding the uniqueness of connection patterns is crucial. Local measures like degree centrality provide valuable information about immediate connections but offer limited insight into how these connections contribute to global structural patterns. Even path-based measures like betweenness centrality, while considering global connectivity, primarily quantify path frequency rather than structural uniqueness. The structural uniqueness of connectivity patterns represents a fundamental property of networks that has remained largely unexplored. Two nodes with identical betweenness or closeness centrality values may differ substantially in how their connections are structured. One node might connect disparate regions of the network through unique paths that, if removed, would significantly alter the network’s topology. In contrast, another node with the same centrality values might have highly redundant paths that could be easily substituted if the node were removed. Traditional centrality measures cannot distinguish between these scenarios despite their differing implications for network resilience, information flow, and functional organization. Many practical applications require a more nuanced structural fingerprint that can distinguish between nodes whose paths are structurally redundant and those whose paths offer unique connectivity patterns. For instance, in resilience analysis, nodes with structurally unique connectivity patterns may represent critical failure points [ 6 , 7 ] , while in anomaly detection [ 8 ] , unusual path structures might signal deviations from expected network behavior [ 7 ] . In communication networks, identifying nodes with diverse connectivity patterns can enhance routing strategies and improve network robustness [ 7 ] . These applications highlight the need for centrality measures that specifically quantify structural uniqueness and redundancy. 1.2 Contributions This paper develops a rigorous mathematical framework for analyzing structural uniqueness in graphs, grounded in binary reachability patterns and their pairwise dissimilarities. Our key theoretical contributions are as follows: 1. Hamming Graph Metrics Framework : We define a comprehensive framework based on the distribution of Hamming distances between binary reachability vectors across all node pairs, capturing the complete spectrum of structural diversity within a graph. 2. Multi-Scale Structural Profiles : The framework decomposes connectivity into a spectrum of exact path lengths, with each scale k analyzed independently to reveal patterns invisible when distances are aggregated. 3. Tensor Formulation and Properties : We develop a family of convex functionals on binary dissimilarity distributions, including entropies, \ell_{1} /total-variation divergences, and spectral descriptors, enabling rich geometric analysis without transport distances. 4. Graph-Level Aggregates : We define dispersion via deviation from the mean profile (TV/ \ell_{1} ) and entropy-based summaries, enabling structural comparisons across graphs. 5. Theoretical Guarantees : New theorems are proved for extremal bounds, monotonicity, and structural separation in canonical graph classes (complete, star, ring, regular, Erdős–Rényi, scale-free). 6. Comparative Geometry of Graphs : Hamming distributions offer a basis for comparing graphs structurally, independent of scale or density. 7. Finite Sample Models : We derive limiting behavior and finite-size approximations under synthetic conditions. While the emphasis throughout is theoretical, we include a brief discussion of algorithmic strategies to compute Hamming Graph Metrics efficiently in Appendix B, and we show that the proposed measures can scale to real-world networks with tens of thousands of nodes when implemented with bit-parallel operations. These observations indicate practical scalability and suggest future work in scalable approximation. 1.3 Preliminaries 1.3.1 Notational Conventions We use superscript (k) to denote exact path length k , not cumulative distance. Thus B^{(k)} indicates paths of length exactly k , and \mathbf{b}_{v}^{(k)} is node v ’s reachability vector at this specific distance. Let G=(V,E) be a finite, simple, undirected graph with vertex set V and edge set E , where |V|=N . Let A\in\{0,1\}^{N\times N} be the adjacency matrix of G , with entries [ 3 ] : A_{ij}=\begin{cases}1&\text{if }(i,j)\in E\\ 0&\text{otherwise}\end{cases} For any positive integer k , the matrix power A^{k} counts the number of walks of length k between nodes. Exact vs. cumulative reachability. Let A be the adjacency matrix and B_{\leq k}:=\mathbf{1}\!\big[\sum_{t=1}^{k}A^{t}>0\big] the cumulative reachability within k steps (element-wise). We use the exact- k convention throughout: B^{(1)}=A,\qquad B^{(k)}:=B_{\leq k}-B_{\leq k-1}\ \ (k\geq 2). Thus the exact- k reachability tensor is B^{(k)} for k=1,\dots,D , with \operatorname{diag}(B^{(k)})=0 for all k ; equivalently, B^{(k)}_{ij}=\mathbf{1}\{\operatorname{dist}(i,j)=k\} . We henceforth identify the k –slice of the tensor with its matrix: B^{(k)}\equiv B^{(k)} . 1.3.2 Tensor Formulation and Cross-Scale Structure We follow Kolda–Bader’s tensor