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⁽⁰⁾.

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⁽¹⁾ = As⁽⁰⁾ is as follows, L2-normalization is applied to rescale:

After k iterations, s^(k) = As^(k-1) = A^ks⁽⁰⁾. 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 λ₁, λ₂, λ₃ and λ₄ that correspond to eigenvectors x₁, x₂, x₃ and x₄ respectively. x₁ is the eigenvector corresponding to the dominate eigenvalue λ₁ that has the largtest absolute value.

According to the Perron-Forbenius theorem, if matrix A has eigenvalues |λ₁| > |λ₂| ≥ |λ₃| ≥ ... ≥ |λ_n|, as k → ∞, the direction of s^(k) = A^ks⁽⁰⁾ converges to x₁, and s⁽⁰⁾ 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 (x₁) of matrix A：

• s⁽¹⁾ = As⁽⁰⁾
• s⁽²⁾ = As⁽¹⁾ = A²s⁽⁰⁾
• ...
• s^(k) = As^(k-1) = A^ks⁽⁰⁾

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

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
create().node_schema("web").edge_schema("link")
create().edge_property(@link, "value", float)
insert().into(@web).nodes([{_id:"web1"}, {_id:"web2"}, {_id:"web3"}, {_id:"web4"}, {_id:"web5"}, {_id:"web6"}, {_id:"web7"}])
insert().into(@link).edges([{_from:"web1", _to:"web1",value:2}, {_from:"web1", _to:"web2",value:1}, {_from:"web2", _to:"web3",value:0.8}, {_from:"web3", _to:"web1",value:0.5}, {_from:"web3", _to:"web2",value:1.1}, {_from:"web3", _to:"web4",value:1.2}, {_from:"web3", _to:"web5",value:0.5}, {_from:"web5", _to:"web3",value:0.5}, {_from:"web6", _to:"web6",value:2}])

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as hdc_eigenvector:

CALL hdc.graph.create("hdc-server-1", "hdc_eigenvector", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_eigenvector", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: eigenvector_centrality

File Writeback

CALL algo.eigenvector_centrality.write("hdc_eigenvector", {
  params: {
    return_id_uuid: "id",
    max_loop_num: 15,
    tolerance: 0.01
  },
  return_params: {
    file: {
      filename: "eigenvector_centrality"
    }
  }
})

algo(eigenvector_centrality).params({
  project: "hdc_eigenvector",
  return_id_uuid: "id",
  max_loop_num: 15,
  tolerance: 0.01
}).write({
  file: {
    filename: "eigenvector_centrality"
  }
})

Result:

_id,eigenvector_centrality
web3,0.460309
web7,2.73277e-05
web1,0.573008
web5,0.255981
web6,0.0189141
web2,0.573028
web4,0.255993

DB Writeback

Writes the eigenvector_centrality values from the results to the specified node property. The property type is float.

CALL algo.eigenvector_centrality.write("hdc_eigenvector", {
  params: {
    edge_weight_property: "@link.value"
  },
  return_params: {
    db: {
      property: "ec"
    }
  }
})

algo(eigenvector_centrality).params({
  project: "hdc_eigenvector",
  edge_weight_property: "@link.value"
}).write({
  db:{ 
    property: 'ec'
  }
})

Full Return

CALL algo.eigenvector_centrality("hdc_eigenvector", {
  params: {
    return_id_uuid: "id",    
    max_loop_num: 20,
    tolerance: 0.01,
    edge_weight_property: "value",
    order: 'desc'
  },
  return_params: {}
}) YIELD ec
RETURN ec

exec{
  algo(eigenvector_centrality).params({
    return_id_uuid: "id",    
    max_loop_num: 20,
    tolerance: 0.01,
    edge_weight_property: "value",
    order: 'desc'
  }) as ec
  return ec
} on hdc_eigenvector

Result:

Stream Return

CALL algo.eigenvector_centrality("hdc_eigenvector", {
  params: {
    return_id_uuid: "id",
    edge_weight_property: "@link.value"
  },
  return_params: {
  	stream: {}
  }
}) YIELD ec
RETURN CASE
  WHEN ec.eigenvector_centrality > 0.4 THEN "important"
  ELSE "normal"
  END as r, count(r) GROUP BY r

exec{
  algo(eigenvector_centrality).params({
    return_id_uuid: "id",
    edge_weight_property: "@link.value"
  }).stream() as ec
  with case
  when ec.eigenvector_centrality > 0.4 then "important"
  else "normal"
  end as r
  group by r
  return r, count(r)
} on hdc_eigenvector

Result: