Algebraic Centrality


This centrality measure the absolute and relative changes in the algebraic connectivity of a graph $G$ upon deletion of a vertex $v$.
If $G$ be a connected graph, suppose that $v$ is a vertex of $G$, and denote the subgraph formed from $G$ by deleting vertex $v$ by $G\backslash v$. Denote the algebraic connectivities of $G$ and $G\backslash v$ by $\alpha(G)$ and $\alpha( G\backslash v)$, respectively.

$$\Phi(v)=\alpha(G)- \alpha(G\backslash v)$$
$$k(v)= {\alpha (G\backslash v)\over\alpha(G)}$$
$\alpha(G)$ provides an algebraic measure of how connected the graph $G$ is.The function yields a measure of vertex centrality, and apply that measure to analyse certain graphs arising from food webs.
$G\backslash v$ denote the subgraph formed from $G$ by deleting $v$ and all edges incident with it.
$\phi(v)$ and $k(v)$provide attainable upper and lower bounds on both functions, and characterise the equality cases in those bounds


  • Kirkland S., 2010. Algebraic connectivity for vertex-deleted subgraphs, and a notion of vertex centrality. Discrete Mathematics, 310(4), pp.911-921. DOI: 10.1016/j.disc.2009.10.011 Publisher web site


There are no comment yet.

Add your comment

Sum of    and  

The rendering mode: