A family of centrality measures for graph data based on subgraphs

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

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.

”