Overview
Graph centrality of a node is measured by the maximum shortest distance from the node to all other reachable nodes. 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.
Graph centrality takes on values between 0 to 1, nodes with higher scores are closer to the center.
Concepts
Shortest Distance
The shortest distance of two nodes is the number of edges contained in the shortest path between them. Please refer to Closeness Centrality for more details.
Graph Centrality
Graph centrality score of a node defined by this algorithm is the inverse of the maximum shortest distance from the node to all other reachable nodes. 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 number and red number next to each node is the shortest distance between the node and the green node and red node. Graph 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 have the same closeness centrality score, graph centrality can be viewed as the subsidiary basis to determine which node is closer to the center.
Considerations
- The graph centrality score of isolated nodes is 0.
- The Graph Centrality algorithm ignores the direction of edges but calculates them as undirected edges.
Example Graph
To create this graph:
// Runs each row separately in order in an empty graphset
create().node_schema("user").edge_schema("vote")
insert().into(@user).nodes([{_id:"A"},{_id:"B"},{_id:"C"},{_id:"D"},{_id:"E"},{_id:"F"},{_id:"G"},{_id:"H"},{_id:"I"},{_id:"J"}])
insert().into(@vote).edges([{_from:"A", _to:"B"}, {_from:"A", _to:"C"}, {_from:"A", _to:"D"}, {_from:"E", _to:"A"}, {_from:"E", _to:"F"}, {_from:"F", _to:"G"}, {_from:"F", _to:"I"}, {_from:"G", _to:"H"}, {_from:"H", _to:"I"}])
Creating HDC Projection
To project the entire graph to the HDC server hdc-server-1
as hdc_graph_centrality
:
CALL hdc.graph.create("hdc-server-1", "hdc_graph_centrality", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_graph_centrality", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).to("hdc-server-1")
Parameters
Algorithm name: graph_centrality
Name |
Type |
Spec |
Default |
Optional |
Description |
---|---|---|---|---|---|
ids |
[]_id |
/ | / | Yes | Specifies nodes for computation by their _id ; computes for all nodes if it is unset. |
uuids |
[]_uuid |
/ | / | Yes | Specifies nodes for computation by their _uuid ; computes for all nodes if it is unset. |
direction |
String | in , out |
/ | Yes | Specifies that the shortest paths shoud only contain incoming edges (in ) or outgoing edges (out ). |
return_id_uuid |
String | uuid , id , both |
uuid |
Yes | Includes _uuid , _id , or both to represent nodes in the results. |
limit |
Integer | ≥-1 | -1 |
Yes | Limits the number of results returned; -1 includes all results. |
order |
String | asc , desc |
/ | Yes | Sorts the results by graph_centrality . |
File Writeback
CALL algo.graph_centrality.write("hdc_graph_centrality", {
params: {
return_id_uuid: "id"
},
return_params: {
file: {
filename: "graph_centrality"
}
}
})
algo(graph_centrality).params({
project: "hdc_graph_centrality",
return_id_uuid: "id"
}).write({
file: {
filename: "graph_centrality"
}
})
Result:
_id,graph_centrality
J,0
D,0.2
F,0.333333
H,0.2
B,0.2
A,0.25
E,0.333333
C,0.2
I,0.25
G,0.25
DB Writeback
Writes the graph_centrality
values from the results to the specified node property. The property type is float
.
CALL algo.graph_centrality.write("hdc_graph_centrality", {
params: {},
return_params: {
db: {
property: 'gc'
}
}
})
algo(graph_centrality).params({
project: "hdc_graph_centrality"
}).write({
db:{
property: 'gc'
}
})
Full Return
CALL algo.graph_centrality("hdc_graph_centrality", {
params: {
return_id_uuid: "id",
ids: ["A","B","C"],
order: "asc"
},
return_params: {}
}) YIELD gc
RETURN gc
exec{
algo(graph_centrality).params({
return_id_uuid: "id",
ids: ["A","B","C"],
order: "asc"
}) as gc
return gc
} on hdc_graph_centrality
Result:
_id | graph_centrality |
---|---|
B | 0.2 |
C | 0.2 |
A | 0.25 |
Stream Return
CALL algo.graph_centrality("hdc_graph_centrality", {
params: {
return_id_uuid: "id"
},
return_params: {type: "stream"}
}) YIELD gc
FILTER gc.graph_centrality > 0.25
RETURN gc
exec{
algo(graph_centrality).params({
return_id_uuid: "id"
}).stream() as gc
where gc.graph_centrality > 0.25
return gc
} on hdc_graph_centrality
Result:
_id | graph_centrality |
---|---|
E | 0.333333 |
F | 0.333333 |