Overview

Eigenvector centrality quantifies a node's influence within a graph. A node's importance is determined by its neighbors - it is influenced by them while also exerting influence to them. However, not all connections the same; a node's centrality increases if it is connected to other highly influential nodes.

Eigenvector centrality takes on values between 0 to 1, nodes with higher centralities are more influential in the network.

Concepts

Eigenvector Centrality

The influence of a node is computed in a recursive way. Consider the graph below, and assume that nodes receive influence through incoming edges. In the adjacency matrix A, element Aij reflects the number of incoming edges of node i. Initially, each node is randomly assigned a centrality value — all set to 1 as an example —represented by the vector c(0).

In each round of influence propagation, a node's centrality is updated as the sum of centralities of all its incoming neighbors. In the first round, this operation is equivalent to multiplying the vector c(0) by the matrix A, i.e., c(1) = Ac(0). Afterward, the L2-normalization is applied to rescale the vector c(1):

After k rounds, c(k) is computed by c(k) = Ac(k-1). As k grows, c(k) stabilizes. In this example, the stablization is reached after around 20 rounds, the elements in c(k) are the centrality of the corresponding nodes.

The algorithm continues until the sum of changes of all elements in c(k) converges to within some tolerance, or the maximum iteration rounds is met.

Eigenvalue and Eigenvector

Given A is a 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 above adjacency matrix A has four eigenvalues λ1, λ2, λ3 and λ4 that correspond to eigenvectors x1, x2, x3 and x4, respectively. x1 is the eigenvector corresponds to the eigenvalue λ1 which has the largtest absolute value, λ1 is called the dominant eigenvalue, and x1 the dominant eigenvector.

In fact, as k grows, c(k) always converges to x1, regardless of how c(0) is initialized. This phenomenon is explained by the Perron-Forbenius theorem. Therefore, computing the eigenvector centrality of nodes in a graph is equivalent to finding the dominant eigenvector of the adjacency matrix A.

Considerations

• To solve the influence leak problem in acyclic digraphs, the algorithm adopts the sum of adjacency matrix and unit matrix (i.e., A = A + I) rather than the adjacency matrix itself.
• Self-loop is counted as one in-link and one out-link.

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,
    direction: "in"
  },
  return_params: {
    file: {
      filename: "eigenvector_centrality"
    }
  }
})

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

Result:

_id,eigenvector_centrality
web6,0.0183902
web2,0.573482
web4,0.255287
web3,0.459952
web7,6.35024e-06
web1,0.57348
web5,0.255292

DB Writeback

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

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

algo(eigenvector_centrality).params({
  projection: "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",
    direction: "in",
    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",
    direction: "in",
    order: 'desc'
  }) as ec
  return ec
} on hdc_eigenvector

Result:

Stream Return

CALL algo.eigenvector_centrality("hdc_eigenvector", {
  params: {
    edge_weight_property: "@link.value",
    direction: "in"
  },
  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({
    edge_weight_property: "@link.value",
    direction: "in"
  }).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: