HDC
Overview
The Common Neighbors algorithm computes the number of common neighbors between two nodes as a measure of their similarity.
The logic behind this algorithm is that if two nodes have a high number of neighbors in common, they are likely to be similar or connected in some meaningful way. It is computed using the following formula:
where N(x) and N(y) are the sets of adjacent nodes to nodes x and y respectively.
More common neighbors indicate greater similarity between nodes, while a number of 0 indicates no similarity between two nodes.
In this example, CN(D,E) = |N(D) ∩ N(E)| = |{B, F}| = 2.
Considerations
- The Common Neighbors 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
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}])
insert().into(@default).edges([{_from:"A", _to:"B"}, {_from:"B", _to:"E"}, {_from:"C", _to:"B"}, {_from:"C", _to:"D"}, {_from:"C", _to:"F"}, {_from:"D", _to:"B"}, {_from:"D", _to:"E"}, {_from:"F", _to:"D"}, {_from:"F", _to:"G"}])
Creating HDC Graph
To load the entire graph to the HDC server hdc-server-1 as hdc_tlp:
CALL hdc.graph.create("hdc-server-1", "hdc_tlp", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_tlp", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).to("hdc-server-1")
Parameters
Algorithm name: topological_link_prediction
Name |
Type |
Spec |
Default |
Optional |
Description |
|---|---|---|---|---|---|
ids |
[]_id |
/ | / | No | Specifies the first group of nodes for computation by their _id; computes for all nodes if it is unset. |
uuids |
[]_uuid |
/ | / | No | Specifies the first group of nodes for computation by their _uuid; computes for all nodes if it is unset. |
ids2 |
[]_id |
/ | / | No | Specifies the second group of nodes for computation by their _id; computes for all nodes if it is unset. |
uuids2 |
[]_uuid |
/ | / | No | Specifies the second group of nodes for computation by their _uuid; computes for all nodes if it is unset. |
type |
String | Common_Neighbors |
Adamic_Adar |
No | Specifies the similarity type; for Common Neighbors, keep it as Common_Neighbors. |
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. |
File Writeback
CALL algo.topological_link_prediction.write("hdc_tlp", {
params: {
ids: ["C"],
ids2: ["A","E","G"],
type: "Common_Neighbors",
return_id_uuid: "id"
},
return_params: {
file: {
filename: "cn.txt"
}
}
})
algo(topological_link_prediction).params({
project: "hdc_tlp",
ids: ["C"],
ids2: ["A","E","G"],
type: "Common_Neighbors",
return_id_uuid: "id"
}).write({
file: {
filename: "cn.txt"
}
})
Result:
_id1,_id2,result
C,A,1
C,E,2
C,G,1
Full Return
CALL algo.topological_link_prediction("hdc_tlp", {
params: {
ids: ["C"],
ids2: ["A","C","E","G"],
type: "Common_Neighbors",
return_id_uuid: "id"
},
return_params: {}
}) YIELD cn
RETURN cn
exec{
algo(topological_link_prediction).params({
ids: ["C"],
ids2: ["A","C","E","G"],
type: "Common_Neighbors",
return_id_uuid: "id"
}) as cn
return cn
} on hdc_tlp
Result:
| _id1 | _id2 | result |
|---|---|---|
| C | A | 1 |
| C | E | 2 |
| C | G | 1 |
Stream Return
MATCH (n)
RETURN collect_list(n._id) AS IdList
NEXT
CALL algo.topological_link_prediction("hdc_tlp", {
params: {
ids: ["C"],
ids2: IdList,
type: "Common_Neighbors",
return_id_uuid: "id"
},
return_params: {
stream: {}
}
}) YIELD cn
FILTER cn.result >= 2
RETURN cn
find().nodes() as n
with collect(n._id) as IdList
exec{
algo(topological_link_prediction).params({
ids: ["C"],
ids2: IdList,
type: "Common_Neighbors",
return_id_uuid: "id"
}).stream() as cn
where cn.result >= 2
return cn
} on hdc_tlp
Result:
| _id1 | _id2 | result |
|---|---|---|
| C | D | 2 |
| C | E | 2 |