Eccentricity Centrality

Overview

The eccentricity of a node in a graph is the maximum shortest distance from the node to any other reachable nodes in the graph. This measurement, along with other measurements like closeness centrality and graph diameter, can be considered jointly to determine whether a node is literally located at the very center of the graph.

Concepts

Shortest Distance

The shortest distance between two nodes is the number of edges in the shortest path connecting them. Please refer to Closeness Centrality for more details.

Eccentricity

The eccentricity of a node is the maximum shortest-path distance from that node to any other reachable node. For example, if the shortest distances from node A to all other nodes are [1, 2, 3, 1], then A's eccentricity is 3.

Related concepts:

• Radius: The minimum eccentricity across all nodes in the graph.
• Diameter: The maximum eccentricity across all nodes in the graph.
• Center nodes: Nodes whose eccentricity equals the radius — the most central nodes in the graph.

Eccentricity Centrality

The eccentricity centrality score of a node is the inverse of its eccentricity. The formula is:

where x is the target node, y is any node that connects with x along edges (x itself is excluded), d(x,y) is the shortest distance between x and y.

In this graph, the green and red numbers next to each node represent the shortest distances from that node to the green and red nodes, respectively. Eccentricity centrality scores of the green and red nodes are 1/4 = 0.25 and 1/3 = 0.3333 respectively.

Regarding closeness centrality, the green node has score 8/(1+1+1+1+2+3+4+3) = 0.5, the red node has score 8/(3+3+3+2+1+1+2+1) = 0.5. When two nodes share the same closeness centrality score, eccentricity centrality can act as a secondary metric to determine which node is closer to the center.

Considerations

• The eccentricity centrality score of isolated nodes is 0.

Example Graph

GQL
INSERT (A:user {_id: "A"}), (B:user {_id: "B"}),
       (C:user {_id: "C"}), (D:user {_id: "D"}),
       (E:user {_id: "E"}), (F:user {_id: "F"}),
       (G:user {_id: "G"}), (H:user {_id: "H"}),
       (I:user {_id: "I"}), (J:user {_id: "J"}),
       (A)-[:vote {weight: 1}]->(B), (A)-[:vote {weight: 2}]->(C),
       (A)-[:vote {weight: 3}]->(D), (E)-[:vote {weight: 2}]->(A),
       (E)-[:vote {weight: 1}]->(F), (F)-[:vote {weight: 4}]->(G),
       (F)-[:vote {weight: 1}]->(I), (G)-[:vote {weight: 2}]->(H),
       (H)-[:vote {weight: 1}]->(I)

Parameters

Run Mode

Returns:

Eccentricity centrality for all nodes:

GQL
CALL algo.eccentricity({
  order: "desc"
}) YIELD nodeId, eccentricity, centrality, isCenter

Result:

Weighted eccentricity centrality:

GQL
CALL algo.eccentricity({
  ids: ["A", "B"],
  weight: ["weight"]
}) YIELD nodeId, eccentricity, centrality, isCenter

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.eccentricity.stream({
  order: "desc"
}) YIELD nodeId, centrality
FILTER centrality > 0.25
RETURN nodeId, centrality

Result:

Stats Mode

Returns:

GQL
CALL algo.eccentricity.stats() YIELD nodeCount, radius, diameter, centerCount, componentCount

Result:

Write Mode

Computes results and writes them back to node properties. The write configuration is passed as a second argument map.

Write parameters:

Writable columns:

Returns:

GQL
CALL algo.eccentricity.write({}, {
  db: {
    property: "gc_score"
  }
}) YIELD task_id, nodesWritten, computeTimeMs, writeTimeMs