Change Password

Input error
Input error
Input error
Submit

Change Nickname

Current Nickname:
Submit
Search
v4.0
    v4.0

    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

    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 return the results ordered by ascending rank score of nodes

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

    Real-time Statistics

    This algorithm has no statistics.

    Please complete the following information to download this book
    *
    公司名称不能为空
    *
    公司邮箱必须填写
    *
    你的名字必须填写
    *
    你的电话必须填写
    *
    你的电话必须填写