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

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.


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:




The following have contributed to this page