Graph eigenvectors, fundamental weights and centrality metrics for nodes in networks

Abstract

Several expressions for the $j$-th component ${\left(x_k\right)}_j$ of the $k$-th eigenvector $x_k$ of a symmetric matrix $A$ belonging to eigenvalue ${\lambda }_k$ and normalized as $x_k^T{x}_k=1$ are presented. In particular, the expression \[ \left( x_{k}\right)_{j}^{2}=-\frac{1}{c_{A}^{\prime}\left( λ_{k}\right) }\det\left( A_{\backslash\left\{ j\right\} }-λ_{k}I\right) \] where $c_A\left(\lambda \right)=\det \left(A-\lambda I\right)$ is the characteristic polynomial of $A$, $c_A^{\prime }\left(\lambda \right)=\frac{d{c}_A\left(\lambda \right)}{d\lambda }$ and $A_{\backslash \left\{j\right\}}$ is obtained from $A$ by removal of row $j$ and column $j$, suggests us to consider the square eigenvector component as a graph centrality metric for node $j$ that reflects the impact of the removal of node $j$ from the graph at an eigenfrequency/eigenvalue ${\lambda }_k$ of a graph related matrix (such as the adjacency or Laplacian matrix). Removal of nodes in a graph relates to the robustness of a graph. The set of such nodal centrality metrics, the squared eigenvector components ${\left(x_k\right)}_j^2$ of the adjacency matrix over all eigenvalue ${\lambda }_k$ for each node $j$, is 'ideal' in the sense of being complete, \emph{almost} uncorrelated and mathematically precisely defined and computable. Fundamental weights (column sum of $X$) and dual fundamental weights (row sum of $X$) are introduced as spectral metrics that condense information embedded in the orthogonal eigenvector matrix $X$, with elements $X_{ij}={\left(x_j\right)}_i$. In addition to the criterion {\em If the algebraic connectivity is positive, then the graph is connected}, we found an alternative condition: {\em If ${\min }_{1\le k\le N}\left({\lambda }_k^2(A)\right)=d_{\min }$, then the graph is disconnected.}

New results are included. The appendices contain supplementary material. All comments are welcome!

References in corpus (4)

• Epidemic processes in complex networks
• Consistency of spectral clustering
• Decay towards the overall-healthy state in SIS epidemics on networks
• Spectral Perturbation and Reconstructability of Complex Networks

Cited by in corpus (3)

• Universality of the SIS prevalence in networks
• Recovery of eigenvectors from eigenvalues in systems of coupled harmonic oscillators
• New bounds on the spectral radius of graphs based on the moment problem