All-subgraphs Centrality
Definition
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$.
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$.
References
- Riveros C., Salas J., 2020. A family of centrality measures for graph data based on subgraphs. Leibniz International Proceedings in Informatics, LIPIcs, 155.
DOI: 10.4230/LIPIcs.ICDT.2020.23
