Change Password

Please enter the password.
Please enter the password. Between 8-64 characters. Not identical to your email address. Contain at least 3 of: uppercase, lowercase, numbers, and special characters.
Please enter the password.
Submit

Change Nickname

Current Nickname:
Submit

Apply New License

License Detail

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

The MAC address of the server you want to deploy.

Please complete this required field.

Please complete this required field.

Cancel
Apply
ID
Product
Status
Cores
Applied Validity Period(days)
Effective Date
Excpired Date
Mac Address
Apply Comment
Review Comment
Close
Profile
  • Full Name:
  • Phone:
  • Company:
  • Company Email:
  • Country:
  • Language:
Change Password
Apply

You have no license application record.

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

Not having one? Apply now! >>>

Product Created On ID Amount (USD) Invoice
Product Created On ID Amount (USD) Invoice

No Invoice

v4.5
Search
    English
    v4.5

      Eigenvector Centrality

      ✓ File Writeback ✓ Property Writeback ✓ Direct Return ✓ Stream Return ✕ Stats

      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(0).

      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(1) = As(0) is as follows, L2-normalization is applied to rescale:

      After k iterations, s(k) = As(k-1) = Aks(0). 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 λ1, λ2, λ3 and λ4 that correspond to eigenvectors x1, x2, x3 and x4 respectively. x1 is the eigenvector corresponding to the dominate eigenvalue λ1 that has the largtest absolute value.

      According to the Perron-Forbenius theorem, if matrix A has eigenvalues 1| > |λ2| ≥ |λ3| ≥ ... ≥ |λn|, as k → ∞, the direction of s(k) = Aks(0) converges to x1, and s(0) 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 (x1) of matrix A

      • s(1) = As(0)
      • s(2) = As(1) = A2s(0)
      • ...
      • s(k) = As(k-1) = Aks(0)

      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:
      Name
      Type
      Spec
      Default
      Optional
      Description
      max_loop_num int ≥1 20 Yes Maximum rounds of iterations; the algorithm ends after running for all rounds, even though the condition of tolerance is not met
      tolerance float (0,1) 0.001 Yes When all scores change less than the tolerance between iterations, the result is considered stable and the algorithm ends
      edge_weight_property @<schema>?.<property> Numeric type, must LTE / Yes Edge property(-ies) to use as edge weight(s), where the values of multiple properties are summed up
      limit int ≥-1 -1 Yes Number of results to return, -1 to return all results
      order string asc, desc / Yes Sort nodes by the centrality score

      Examples

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

      File Writeback

      Spec Content
      filename _id,rank
      algo(eigenvector_centrality).params({
        max_loop_num: 15,
        tolerance: 0.01
      }).write({
          file: {
            filename: 'rank'
          }
      })
      

      Results: File rank

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

      Property Writeback

      Spec Content Write to Data Type
      property rank Node property float
      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

      Alias Ordinal Type
      Description
      Columns
      0 []perNode Node and its centrality _uuid, rank
      algo(eigenvector_centrality).params({
        max_loop_num: 20,
        tolerance: 0.01,
        edge_weight_property: '@link.value',
        order: 'desc'
      }) as ec 
      return ec
      

      Results: ec

      _uuid rank
      1 0.73133802
      6 0.48346400
      2 0.43551901
      3 0.17412201
      4 0.098612003
      5 0.041088000
      7 0.0000000

      Stream Return

      Alias Ordinal Type
      Description
      Columns
      0 []perNode Node and its centrality _uuid, rank

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

      algo(eigenvector_centrality).params({
        edge_weight_property: '@link.value'
      }).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))

      r count(r)
      attention 3
      normal 4
      Please complete the following information to download this book
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写