  # Change Nickname

Current Nickname:

Certifications

Certificate Issued at Valid until Serial No. File
Serial No. Valid until

Not having one? Apply now! >>>

Invoice

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

# Eigenvector Centrality

## 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(0) an non-zero initial vector of order n x 1, and iterate according to the following rule to continue producing new vectors:

• v(1) = Av(0)
• v(2) = Av(1) = A2v(0)
• ...
• v(k) = Av(k-1) = Akv(0)

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

_uuid _id rank
1 web1 0.57355899
2 web2 0.57355601
3 web3 0.45988801
5 web5 0.25517300
4 web4 0.25516701
6 web6 0.018536000
7 web7 0.0000060000002

Algorithm statistics: N/A

## Command and Configuration

• Command: `algo(eigenvector_centrality)`
• Configurations for the parameter `params()`:
Name Type
Default
Specification
Description
max_loop_num int 20 >=1 Maximum number of iterations
tolerance float 0.001 (0,1) The convergence bias of the iteration, i.e. the change in the sum of all elements of the normalized vector. The iteration ends when the value of this change is less than this specified convergence bias.
edge_weight_property `@<schema>?.<property>` / Numeric edge property, LTE needed Edge weight property/properties, schema can be either carried or not; edge without any specified property does not participate in the calculation; degree is unweighted if not set
limit int -1 >=-1 Number of results to return; return all results if sets to -1 or not set
order string / ASC or DESC, case insensitive To sort the returned results; no sorting is applied if not set

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

#### 1. File Writeback

Configuration Data in Each Row
filename `_id`,`rank`

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

Configuration Writeback Content Type Data Type
property `rank` Node property `float`

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

Alias Ordinal Type
Description
Column Name
0 []perNode Node and its eigenvector centrality `_uuid`, `rank`

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,
}) as ec
return ec
``````

### Streaming Return

Alias Ordinal Type
Description
Column Name
0 []perNode Node and its eigenvector centrality `_uuid`, `rank`

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.