6
$\begingroup$

Using adjacency matrix to represent a connection between node i and node j, 1 means connected and 0 means not connected.

Using eigenvector to represent the centrality means the more nodes with high centrality values a node is connected to, the higher that node's centrality value is.

Eigenvector itself is just a vector after applying a transformation, the result vector has the same direction or totally opposite direction as the original one.

I really can't see the relationship between those two properties.

$\endgroup$
6
$\begingroup$

Let the adjacency matrix of our network be $A∈\{0,1\}^{n×n}$ with an empty diagonal ($A_{ii} = 0 ∀i$).

Direct approach

Let’s start with the approach that a node’s centrality ($C_i$) shall be proportional to the sum of the centralities of its neighbours with a proportionality constant $\frac{1}{λ}$ (chosen thusly with some foresight):

$$ C_i = \frac{1}{λ} \sum_{j=1}^{n} A_{ij} C_j.$$

This is nothing but a line-wise formulation of the matrix–vector multiplication:

$$ λ \vec{C} = A·\vec{C},$$

which is exactly the definition of an eigenvector. Now, to see why the largest eigenvector is chosen, we can turn to the Perron–Frobenius theorem, which tells us that for this eigenvalue (and in case of a connected network only for this eigenvalue), we can find an eigenvector all of whose components, i.e., the eigenvector centralities are positive.

Iterative approach

Alternatively, we can interpret the above ansatz iteratively:

  1. Assign random positive values to the components of $\vec{C}$.
  2. Update these values according to:

    $$\vec{C} ← \frac{A·\vec{C}}{\left| A·\vec{C} \right|}.$$

    This means that each component is updated according to:

    $$C_i ← \frac{1}{\left| A·\vec{C} \right|} \sum_{j=1}^{n} A_{ij} C_j,$$

    i.e., you say the new centrality of a node is the sum of the centralities of its neighbours – times some normalisation to avoid values getting very big.

  3. Repeat Step 2 until the centralities converge. The idea is that if this converges to a unique result, this result does not only fulfil $C_i \propto \sum_{j=1}^{n} A_{ij} C_j$ but is also robust in that respect.

For almost all initial choices of $\vec{C}$, this will converge to the positive, length-1 eigenvector to the largest eigenvalue (which exists and is unique for a connected network, see above). The reason for this is that components along the eigenvector to the largest eigenvalue will be most enlarged by the multiplication and thus dominate the others over the iterations. (Having no components along the eigenvector to the largest eigenvalue does not happen in reality and is the reason why it’s almost all above.)

Note that such an iteration can also be used to numerically determine the largest eigenvalue.

| improve this answer | |
$\endgroup$
3
$\begingroup$

Let's define the centrality of a vertex as proportional to the sum of its neighbors' centralities. If you write it out and incorporate the adjacency matrix, the eigendecomposition emerges immediately with the proportional constant as the reciprocal of the eigenvalue. The relevance of the eigenvector is that the centrality is defined through it: the score of a vertex is the corresponding entry on the first eigenvector. We had to choose the first eigenvector because the adjacency matrix is non-negative and we want the centralities to be so too, due to the Perron-Frobenius theorem (see these lectures notes for details). So if our centralities are intrinsically related to the transition matrix' eigenvectors, how do we find them? By using the power method, which relies on their fixed point nature! If you transform an eigenvector, you get a collinear vector (the property you wanted to relate), so why not do this with a random estimate of it until convergence, normalizing as we go along? Furthermore, if we slightly reformulate the problem to use stochastic matrices, the scores are directly interpretable as probabilities of random walks terminating at the corresponding vertex!

If you're really curious, there's a monograph: Google's PageRank and Beyond. Welcome to the site.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.