A family of centrality measures for graph data based on subgraphs

Graph structured data are stored in specialized databases called graph databases. These systems let us efficiently compute queries over the graph such as looking for paths or patterns in it. Conjunctive queries are one kind of commonly used queries for graph databases where you look for patterns as connected subgraphs. Therefore, it seems natural to assign relevance as the amount of subgraphs surrounding a node in the graph. This is the main idea behind all subgraphs centrality, a node will be more central the more connected subgraphs are containing it. Then, we generalize this idea by admitting families of relevant subgraphs depending on each application. Finally, we exploit these families to study which axioms are satisfied by the centrality measure defined from each of them and which families can be computed in reasonable time. This work was published at the international conference for database theory in 2020 (ICDT2020) available at https://drops.dagstuhl.de/opus/volltexte/2020/11947/pdf/LIPIcs-ICDT-2020-23.pdf