Structural Sensitivity in Graphs: An Entropy-Based $k$-Hop Metric and its Applications
Csaba Bíró · 2025
Graph analysis has long relied on classical metrics such as degree distribution, centrality measures, and clustering coefficients. However, these traditional metrics often fail to capture the structural variability in local and global connectivity patterns. In this paper, we introduce the$k$-hop entropy metric (KHEM), a structure-sensitive measure that quantifies the complexity of a node's$k$-hop neighborhood. Unlike degreebased measures, KHEM incorporates the entropy of node degree distributions within a given neighborhood radius, providing deeper insight into network heterogeneity. An analysis of KHEM has been conducted across various network models, including Erdős-Rényi random graphs, Barabási-Albert scale-free networks, Watts-Strogatz small-world graphs, and quantum computing topologies such as D-Wave's architectures. The findings indicate that KHEM provides a more nuanced representation of local structural complexity by distinguishing nodes according to neighborhood entropy rather than mere connectivity. This leads to enhanced node ranking and a more refined structural characterization across diverse types of networks.