Absolute Expressiveness of Subgraph Motif Centrality Measures

In graph-based applications, a common task is to pinpoint the most important or ``central'' vertex in a (directed or undirected) graph, or rank the vertices of a graph according to their importance. To this end, a plethora of so-called centrality measures have been proposed in the literature. Such measures assess which vertices in a graph are the most important ones by analyzing the structure of the underlying graph. A family of centrality measures that are suited for graph databases has been recently proposed by relying on the following simple principle: the importance of a vertex in a graph is relative to the number of ``relevant'' connected subgraphs, known as subgraph motifs, surrounding it; we refer to the members of this family as subgraph motif centrality measures. Although it has been shown that such measures enjoy several favourable properties, their absolute expressiveness remains largely unexplored. The goal of this work is to precisely characterize the absolute expressiveness of the family of subgraph motif centrality measures by considering both directed and undirected graphs. To this end, we characterize when an arbitrary centrality measure is a subgraph motif one, or a subgraph motif measure relative to the induced ranking. These characterizations provide us with technical tools that allows us to determine whether well-established centrality measures are subgraph motif. Such a classification, apart from being interesting in its own right, gives useful insights on the structural similarities and differences among existing centrality measures.