What is it about?
This work introduce the setting of subgraph-based centrality measures to find the most important nodes in a graph. The subgraph-based framework allows for a wide variety of new measures with an unprecedented set of properties. We include a complexity analysis for the most iconic subgraph-based measures plus an experimental analysis to compare such measures with commonly used ones like PageRank, Closeness, Betweenness and others.
Featured Image
Photo by JJ Ying on Unsplash
Why is it important?
We propose All-subgraphs and All-trees centrality measures which satisfy several centrality axioms proposed during the last decade. Since no other measure is known to satisfy all these properties at the same time, the subgraph-based measures can be a keystone on understanding centrality in a deeper way.
Perspectives
The idea of using subgraphs to create new centrality measures can lead to important implications in the network science field. In particular, subgraph counting is a commonly explored problem, having strong complexity barriers. However, given the relevant information they gather from the graph, it is possible that subgraphs can give a new perspective on node centrality.
Jorge Salas
University of Edinburgh
Read the Original
This page is a summary of: A family of centrality measures for graph data based on subgraphs, ACM Transactions on Database Systems, February 2024, ACM (Association for Computing Machinery),
DOI: 10.1145/3649134.
You can read the full text:
Resources
Contributors
The following have contributed to this page
