Overview

Eigenvector Centrality algorithm measures the transfer of node influence. Relationships from high-scoring nodes contribute more to the node score than relationships from low-scoring nodes, and a node with a high score means it is connected to many high-scoring nodes. The eigenvector centrality emphasizes the surrounding environment of the node. For example, in the spread of disease, the node with higher eigenvector centrality is more likely to be closer to the source of infection, which needs special precautions.

A variant of eigenvector centrality is Google’s well-known PageRank algorithm, which they use to rank web pages.

The range of values of eigenvector centrality is [0,1]; the larger the value, the closer the node is to the center.

Basic Concept

Eigenvalue and Eigenvector

Eigenvalues and eigenvectors are one of the important concepts of matrix theory. Given A is a square matrix of order n x n, λ is a constant and x is an non-zero column vector of order n x 1, if the equation Ax = λx is true, then λ is called the eigenvalue of A, and x is called the eigenvector of A that corresponds to the eigenvalue λ.

The eigenvalues of A can be calculated by the characteristic equation |A - λE| = 0, where E is the identity matrix of the same order as A; the n roots of the equation (possibly includes repeated roots) are the n eigenvalues λ1, λ2, ..., λn. For each eigenvalue, the corresponding eigenvectors can be obtained by solving the equation (A – λE)x = 0, and the number of eigenvectors is infinite. Among these eigenvalues, the eigenvalue with the largest absolute value is called the dominate eigenvalue, and the eigenvector corresponding to the dominate eigenvalue is the dominate eigenvector, which contains the most information about the matrix.

In the example above, matrix A has 5 eigenvalues, x1 which corresponds to λ1 with the largest absolute value is the dominate eigenvector.

Eigenvector Centrality

The transitive influence of nodes in the graph can be represented in a matrix, the centrality which is measured by the eigenvector of the matrix is the eigenvector centrality.

Power Iteration

The common method for solving matrix eigenvalues and eigenvectors is the eigen polynomial calculation, however in practice, this calculation is quite resource intensive and cannot compute large matrix. Ultipa's Eigenvector Centrality algorithm uses the power iteration method to solve the dominate eigenvector of the matrix, which greatly improves the computation efficiency while ensuring accuracy.

The calculation process of the power iteration is simple. For A the square matrix of order n x n, arbitrarily select v⁽⁰⁾ an non-zero initial vector of order n x 1, and iterate according to the following rule to continue producing new vectors:

• v⁽¹⁾ = Av⁽⁰⁾
• v⁽²⁾ = Av⁽¹⁾ = A²v⁽⁰⁾
• ...
• v^(k) = Av^(k-1) = A^kv⁽⁰⁾

As long as k is large enough, v^(k) is equivalent to the eigenvector of A. The convergence of the power iteration method can be proved theoretically, which is omitted here.

The problem with this method is that the non-zero elements in v^(k) increase significantly as k increases. To avoid data overflow during the calculation, the algorithm makes the elements in v^(k) L2-normalized at each step.

Ultipa's Eigenvector Centrality algorithm states that the convergence bias of the iteration tolerance is the change in the sum of change of all elements of the normalized vector. The iteration ends when the value of this change is less than the specified convergence bias, or the number of iterations reaches the limit.

Special Case

Lonely Node, Disconnected Graph

Lonely node is not connected with any other node, so its eigenvector centrality only depends on its self-loop edge.

Self-loop Edge

The weight of self-loop edge is only counted once.

Directed Edge

For each node, eigenvector centrality only considers its inbound edges, i.e. the way it receives influence from its neighbors. The eigenvector centrality score of node with no inbound edge converges to 0.

Results and Statistics

Take the 7-node web page reference graph below as an example, run the Eigenvector Centrality algorithm, iterate 20 rounds the maximum, tolerance is 0.01, weights of all edges are 1：

Algorithm results: Calculate eigenvector centrality for each node, return _id, rank or _uuid, rank according to the execution method

Algorithm statistics: N/A

Command and Configuration

• Command: algo(eigenvector_centrality)
• Configurations for the parameter params():

Example: Calculate eigenvector centrality of all nodes, iterate 20 rounds the maximum, tolerance is 0.01

algo(eigenvector_centrality).params({
  max_loop_num: 20,
  tolerance: 0.01
  }) as centrality
return centrality

Algorithm Execution

Task Writeback

1. File Writeback

Example: Calculate eigenvector centrality of all nodes, iterate 20 rounds the maximum, tolerance is 0.01, write the algorithm results back to file named rank

algo(eigenvector_centrality).params({
  max_loop_num: 20,
  tolerance: 0.01
  }).write({
    file: {
      filename: "rank"
    }
})

2. Property Writeback

Example: Calculate eigenvector centrality of all nodes, iterate 20 rounds the maximum, tolerance is 0.01, write the rank score back to node property named ec

algo(eigenvector_centrality).params({
  max_loop_num: 20,
  tolerance: 0.01
  }).write({
    db: {
      property: "ec"
    }
})

3. Statistics Writeback

This algorithm has no statistics.

Direct Return

Example: Calculate eigenvector centrality of all nodes, iterate 20 rounds the maximum, tolerance is 0.01, edge weight locates on property @link.score, define algorithm results as alias named ec, and return the results

algo(eigenvector_centrality).params({
  max_loop_num: 20,
  tolerance: 0.01,
  edge_weight_propery: @link.score
  }) as ec 
return ec

Streaming Return

Example: Calculate eigenvector centrality of all nodes, iterate 20 rounds the maximum, tolerance is 0.01, and count the number of nodes with score above 0.5 or otherwise respectively

algo(eigenvector_centrality).params({
  max_loop_num: 20,
  tolerance: 0.01
  }).stream() as results
WITH CASE
when results.rank > 0.5 then "attention"
when results.rank <= 0.5 then "normal"
END as cat
group by cat
return table(cat, count(cat))

Real-time Statistics

This algorithm has no statistics.