Localization of eigenvector centrality in networks with a cut vertex

We show that eigenvector centrality exhibits localization phenomena on networks that can be easily partitioned by the removal of a vertex cut set, the most extreme example being networks with a cut vertex. Three distinct types of localization are identified in these structures. One is related to the well-established hub node localization phenomenon and the other two are introduced and characterized here. We gain insights into these problems by deriving the relationship between eigenvector centrality and Katz centrality. This leads to an interpretation of the principal eigenvector as an approximation to more robust centrality measures which exist in the full span of an eigenbasis of the adjacency matrix.

Figure 1

The classic karate club network [13] is duplicated. Node 2 in the left network is connected to node 13 in the network on the right via an additional node (CV) which is a cut vertex. The size of the nodes increases with their eigenvector centrality and the color from white through to green is also changing with increasing eigenvector centrality.

Figure 2

A network formed by connecting two different fifty-node Erdős-Rényi random graphs together with a cut vertex. The bottom graph has average degree 5.84 and the top has average degree 6.32. The cut vertex connects to five nodes in the bottom subgraph and to three nodes in the top subgraph. The size of nodes increases with their eigenvector centrality and their color also changes from white through to green.

Figure 3

(a) For the network in Fig. 1, the right subgraph remains connected via node 13 whereas the left subgraph is increasingly connected to the cut vertex, starting with node 1, and then nodes 1 and 2, continuing until all 34 nodes are connected. The impact on the ratio of the average eigenvector centrality (blue circles) as well as on the approximation $\rho$ (red crosses) is shown. (b) For the network in Fig. 2, the connectivity of the lower subgraph to the cut vertex remains as before, but the connectivity to the upper subgraph increases by sequentially connecting a new node chosen uniformly at random from the remaining unconnected nodes, except that the first three nodes are chosen to be the same as in Fig. 2. The ratio of the average eigenvector centrality (blue circles) and the approximation $\rho$ (red crosses) is shown as well as the contributions of the second (black solid line) and third (black dashed line) factors in Eq. (9).

Figure 4

Modification of the double karate network in Fig. 1 to have a vertex cut set of three nodes {a, b, c}. The size of the nodes increases with their eigenvector centrality and the color from white through to green is also changing with increasing eigenvector centrality.