All-subgraphs Centrality


The main principle of this approach is very simple: the more relevant subgraphs around a vertex, the more central it is in the network. The notion of “relevant subgraphs” formalized by choosing a family of subgraphs that, give a graph $G$ and a vertex $v$ in $G$, which assigns a subset of connected subgraphs of $G$ that contains $v$. Any of such families defines a measure of centrality by counting the number of subgraphs assigned to the vertex. This centrality measure takes every subgraph into account.

The all-subgraphs centrality of $v$ in $G$ is defined as:

$$C_A(v,G):=log (|A(v,G)|)$$

Considering a graph $G$ and a vertex $v \in V(G)$. $A(v,G)$ denotes by the set of all connected subgraphs of $G$ that contains $v$, formally, $A(v) = {G'\subseteq G|G' is connected $\wedge v\in V(G')}$.

The function $C_A$ naturally induces a ranking between nodes: the higher the centrality $C_A(v,G)$, the more important is $v$ in $G$.


  • Riveros, C. and Salas, J., 2020. A Family of Centrality Measures for Graph Data Based on Subgraphs. In 23rd International Conference on Database Theory (ICDT 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.ICDT.2020.23 Publisher web site


There are no comment yet.

Add your comment

Sum of    and  

The rendering mode: