Eigenvector Centrality

Overview

Eigenvector centrality measures the power or influence of a node. In a directed network, the power of a node comes from its incoming neighbors. Thus, the eigenvector centrality score of a node depends not only on how many in-links it has, but also on how powerful its incoming neighbors are. Connections from high-scoring nodes contribute more to the score of the node than connections from low-scoring nodes. In the disease spreading scenario, a node with higher eigenvector centrality is more likely to be close to the source of infection, which needs special precautions.

The well-known PageRank is a variant of eigenvector centrality.

Eigenvector centrality takes on values between 0 to 1, nodes with higher scores are more influential in the network.

Concepts

Eigenvector Centrality

The power (score) of each node can be computed in a recursive way. Take the graph below as as example, adjacent matrix A reflects the in-links of each node. Initialzing that each node has score of 1 and it is represented by vector s⁽⁰⁾.

In each round of power transition, update the score of each node by the sum of scores of all its incoming neighbors. After one round, vector s⁽¹⁾ = As⁽⁰⁾ is as follows, L2-normalization is applied to rescale:

After k iterations, s^(k) = As^(k-1) = A^ks⁽⁰⁾. As k grows, s^(k) stabilizes. In this example, the stablization is reached after ~20 rounds.

In fact, s^(k) converges to the eigenvector of matrix A that corresponds to the largest absolute eigenvalue, hence elements in s^(k) is referred to as eigenvector centrality.

Eigenvalue and Eigenvector

Given A is an n x n square matrix, λ is a constant, x is an non-zero n x 1 vector. If the equation Ax = λx is true, then λ is called the eigenvalue of A, and x is the eigenvector of A that corresponds to the eigenvalue λ.

The above matrix A has 4 eigenvalues λ₁, λ₂, λ₃ and λ₄ that correspond to eigenvectors x₁, x₂, x₃ and x₄ respectively. x₁ is the eigenvector corresponding to the dominate eigenvalue λ₁ that has the largtest absolute value.

According to the Perron-Forbenius theorem, if matrix A has eigenvalues |λ₁| > |λ₂| ≥ |λ₃| ≥ ... ≥ |λ_n|, as k → ∞, the direction of s^(k) = A^ks⁽⁰⁾ converges to x₁, and s⁽⁰⁾ can be any nonzero vector.

Power Iteration

For the best computation efficiency and accuracy, this algorithm adopts the power iteration approach to compute the dominate eigenvector (x₁) of matrix A：

• s⁽¹⁾ = As⁽⁰⁾
• s⁽²⁾ = As⁽¹⁾ = A²s⁽⁰⁾
• ...
• s^(k) = As^(k-1) = A^ks⁽⁰⁾

The algorithm continues until s^(k) converges to within some tolerance, or the maximum iteration rounds is met.

Considerations

• The algorithm uses the sum of adjacency matrix and unit matrix (i.e., A = A + I) rather than the adjacency matrix only in order to guarantee the covergence.
• The eigenvector centrality score of nodes with no in-link converges to 0.
• Self-loop is counted as one in-link, its weight counted only once (weighted graph).

Syntax

• Command: algo(eigenvector_centrality)
• Parameters:

Examples

The example is a web network, edge property @link.value can be used as weights:

File Writeback

UQL
algo(eigenvector_centrality).params({
  max_loop_num: 15,
  tolerance: 0.01,
  direction: "in"
}).write({
    file: {
      filename: 'rank'
    }
})

Results: File rank

File
web7,4.63007e-06
web6,0.0198426
web5,0.255212
web3,0.459901
web4,0.255214
web2,0.573512
web1,0.573511

Property Writeback

UQL
algo(eigenvector_centrality).params({
  edge_weight_property: 'value'  
}).write({
    db: {
      property: 'ec'
    }
})

Results: Centrality score for each node is written to a new property named ec

Direct Return

UQL
algo(eigenvector_centrality).params({
  max_loop_num: 20,
  tolerance: 0.01,
  edge_weight_property: '@link.value',
  direction: "in",
  order: 'desc'
}) as ec 
return ec

Results: ec

Stream Return

Example: Calculate weighted eigenvector centrality for all nodes, count the number of nodes with score above 0.4 or otherwise respectively

UQL
algo(eigenvector_centrality).params({
  edge_weight_property: '@link.value',
  direction: "in"
}).stream() as ec
with case
when ec.rank > 0.4 then 'attention'
when ec.rank <= 0.4 then 'normal'
END as r
group by r
return table(r, count(r))

Results: table(r, count(r))