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
Task Writeback
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,
edge_weight_propery: @link.score
}) 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.