Hamming Graph Metrics: A Multi-Scale Framework for Structural Redundancy and Uniqueness in Graphs
Authors
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$ reachability tensor $\mathcal{B}G\in{0,1}^{N\times N\times D}$ with slices $(\mathcal{B}G){:,:,1}=A$ and, for $k\ge 2$, $(\mathcal{B}G){:,:,k}=\mathbf{1}!\left[\sum{t=1}^{k} A^t>0\right]-\mathbf{1}!\left[\sum_{t=1}^{k-1} A^t>0\right]$ (shortest-path distance exactly $k$). Guarantees. (i) Permutation invariance: $d_{\mathrm{HGM}}(π(G),π(H))=d_{\mathrm{HGM}}(G,H)$ for all vertex relabelings $π$; (ii) the tensor Hamming distance $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" $\to$ "Tensor Hamming metric"; "Stability to edge perturbations"; Appendix A). We develop: (1) per-scale spectral analysis via classical MDS on double-centered Hamming matrices $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.
