Intuition behind eigenvector centrality and computation procedure

3.1k Views Asked by At

There are various metrics that are used in social network analysis to estimate/find the influence of a node. Among them are various "centralities" - betweenness centrality, closeness centrality and eigenvector centrality (Learning agent influence in MAS with complex social networks, 2013 by H. Franks, H. Griffith and S.S. Anand).

Betweenness centrality measures the number of shortest paths in a network that pass through $v_i \in V$, where $V$ is a set of nodes in $G(E,V)$. Intuitively it allows us to see how much information is likely to flow through $v_i$.

Closeness centrality measures how quickly information can spread from a given agent and its mathematical definition is straightforward.

Eigenvector centrality is calculated using the principle eigenvector given by the adjacency matrix of the graph under consideration. If $EC(v_i)$ is the eigenvector centrality of $v_i$, then:

$EC(v_i) = \dfrac{1}{\lambda} \sum_{v_j\in N(v_i)} a_{v_i,v_j} \times EC(v_j)$

where $a_{i,j}$ stands for the entry in the adjacency matrix $A$ and $N(v_i)$ denotes the set of neighbours of $v_i$.

The paper given above says:

An agent is central if it is connected to other agents that are central, and the measure takes into account both direct and indirect connections between agents

How does this follow from the definition given above?

What is the intuition?

How do we compute $EC(v_i)$ in practice (definition given above looks recursive)?

1

There are 1 best solutions below

0
On BEST ANSWER

An agent is central if it is connected to other agents that are central $\dots$

The eigenvector centrality $EC\left(v_{i}\right)$ of the vertex $v_{i}$ may be described as a measure of the structural importance of $v_{i}$, proportional to the structural importances of their connected neighbourhood; the eigenvector centralities $EC\left(v_{j}\right)$) of each vertex $v_{j}\in N\left(v_{i}\right)$.

In your definition, the required proportionality is obtained by summing over the neighbourhood set $v_{j}\in N\left(v_{i}\right)$ of the principle vertex $v_{i}$. However, in any simplex network, the entries of the adjacency matrix $a_{v_{i}v_{j}}$ are non-zero whenever the vertex $v_{j}$ is incident to $v_{i}$, and thus, each term $a_{v_{i}v_{j}}EC\left(v_{j}\right)$ is non-zero only if $e_{ij}\in E$.

With this in mind, we may extend the neighbourhood summation to that of a summation over all vertices present in the network, as only the connected vertices will contribute to the eigenvector centrality sum of $v_{i}$. Hence

\begin{equation} EC\left(v_{i}\right) := \frac{1}{\lambda}\sum_{v_{j}\in N\left(v_{i}\right)} a_{v_{i}v_{j}}EC\left(v_{j}\right) = \frac{1}{\lambda}\sum_{v_{j}\in V} a_{v_{i}v_{j}}EC\left(v_{j}\right) \end{equation}

By adopting the vector notation $EC := \left(EC\left(v_{i}\right)\right)_{v_{i}\in V} \in \mathbb{R}^{|V|}$, the eigenvector centrality definition can now be expressed in terms of the full adjacency matrix A: \begin{equation} EC = \frac{1}{\lambda}A.EC \end{equation} Here, each entry $EC\left(v_{i}\right)$ of the $EC$ vector is proportionally equal to the $i$-th of $A$ multiplied by the whole vector $EC$. Lastly, we obtain the eigenvector equation $\lambda EC = A.EC$, which gives the centrality its name.

$\dots$ and the measure takes into account both direct and indirect connections between agents

Despite not being widely accepted terminology, the eigenvector centrality is frequently classified as a radial centrality, which is the class of centrality metrics that measures structural importance in terms of network walks originating/terminating at a particular desired vertex.

Given the expression $\lambda EC = A.EC$, it is possible to recursively imagine that the eigenvector centrality of $v_{i}$ is proportional to the importance of its neighbours $N\left(v_{i}\right)$, whose importance is proportional to their neighbours, whose importance is proportional on their neighbours, etc$\dots$ I would thus argue that eigenvector centralities do in fact take into "account both direct and indirect connections between agents" as your statement suggests.

How do we compute $EC\left(v_{i}\right)$ in practice (definition given above looks recursive)?

There are a whole host of computational methods for computing eigenvectors, and thus eigenvector centralities. Arguably the most common of which is a recursively implemented algorithm called the power iteration method.