Introduction
Centrality measures are fundamental tools in network analysis, used to identify influential nodes across diverse domains, from social media influencers to essential biological proteins. Recently, "subgraph-based" centrality measures have gained prominence, particularly within graph database applications. These measures rank node importance based on the local patterns—such as triangles, paths, or cliques—in which a node participates. Despite their intuitive appeal and computational efficiency, the formal boundaries of this family of measures remained poorly defined. This research provides the first rigorous characterization of subgraph-based centrality, determining which mathematical properties a measure must possess to be classified as such.
Defining the Boundaries: Methods and Characterizations
The study employs discrete mathematics and formal logic to establish the "absolute expressiveness" of subgraph-based measures. The authors introduce two primary frameworks to evaluate these measures:
1. The Bounded Value Property
To assess whether a measure is subgraph-based in an absolute sense (where the specific numerical score is significant), the authors propose the Bounded Value Property. This property examines the relationship between the number of distinct values a measure can assign and the complexity of the surrounding subgraphs. If a measure generates an "explosion" of distinct values for nodes within relatively simple local structures, it fails to be strictly subgraph-based. This highlights a fundamental "pigeonhole" constraint: because a node in a finite graph can only participate in a finite number of connected subgraphs, a measure based solely on counting these patterns cannot produce an infinite variety of scores for simple configurations.
2. C-Colorability and Ranking
For many applications, the relative ranking of nodes is more important than their absolute scores. To address this, the authors introduce "C-Colorability," a graph-coloring approach supported by Rado’s Selection Principle from set theory. This framework proves that if a ranking can be consistently represented by subgraph counts for any finite set of nodes, that representation holds across the entire universe of possible graphs.
Key Insights: Scoring vs. Ranking
A critical finding of the research is the distinction between absolute scoring and relative ranking. Many well-known centrality measures, such as Closeness Centrality and PageRank, fail the strict subgraph-based test when looking at raw scores. These measures often depend on global graph structures in ways that simple local subgraph counting cannot capture.
However, the research reveals a significant "exception" for connected graphs. Theorem 19 demonstrates that on connected graphs, nearly every possible centrality measure induces a ranking that can be represented as a subgraph-based measure. This suggests that the subgraph-based framework serves as a "universal language" for node rankings in the types of connected networks most commonly encountered in practice.
Classification of Centrality Measures
The authors validated their theoretical findings by classifying several established centrality measures:
- Strictly Subgraph-based: This category includes Stress Centrality, All-Subgraphs, Degree Centrality, and Cross-Clique Centrality.
- Not Subgraph-based (Absolute): Closeness, Harmonic, PageRank, and Eigenvector Centrality fall here because their absolute values are influenced by global properties.
- Ranking-Equivalent (Connected Graphs): When restricted to connected graphs and focused solely on ranking, Closeness, Harmonic, and PageRank can be represented as subgraph-based.
- Inconclusive: Betweenness and Eigenvector centrality remain complex, with their relationship to subgraph-based measures requiring further structural analysis.
Conclusion and Future Work
This work provides a definitive map of the landscape of subgraph-based centrality. By proving that most rankings in connected graphs are fundamentally subgraph-based, the authors bridge the gap between local pattern counting and global network importance.
Future research may extend these findings to directed graphs, where measures like Eigenvector centrality behave differently. Additionally, there is room to explore the impact of restricting the "language" of subgraphs—for instance, determining the expressiveness of measures that only consider specific patterns like paths of a certain length. Finally, the nuanced behavior of Betweenness centrality remains an open area for deeper theoretical investigation.
Summary updated