EXPERIMENTAL: These features are experimental and should not be used in production systems.
Graph Library (graphlib) — Measures Extension
A library extension to graphlib containing various similarity and other measures.
Module: rel:graphlib
View sourcerel:graphlib[G]This section of the graph library supports the following similarity metrics and interfaces:
| Measure | Description |
|---|---|
jaccard_similarity | A similarity measure between two nodes using the Jaccard index. |
cosine_similarity | A similarity measure between two nodes using the cosine between their neighborhood vectors. |
preferential_attachment | A score between two nodes using preferential attachment. |
adamic_adar | A measure between two nodes using the Adamic-Adar index. |
common_neighbor | A set of common neighbors between two nodes. |
jaccard_similarity
View sourcejaccard_similarity
jaccard_similarity[u]
jaccard_similarity[u, v]
jaccard_similarity(u, v, score)jaccard_similarity computes the Jaccard index between every node and every other node
in G. jaccard_similarity[u] computes the Jaccard index between u and every other
node in G. jaccard_similarity[u, v] computes the Jaccard index between u and v
in G. jaccard_similarity(u, v, score) checked whether score is the Jaccard index
between u and v.
Parameters
| Parameter | Type | Description |
|---|---|---|
u | G:node | A node in G. |
v | G:node | A node in G. |
score | Float | The Jaccard Index between node u and v. |
Explanation
The Jaccard index can be used to measure similarity between two nodes. It ranges from 0 to 1. The higher the value, the more similar the nodes are.
Examples
Compute the Jaccard similarity between two nodes:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:jaccard_similarity[12, 14]
//output> 0.25Compute the Jaccard similarity on the whole graph:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:jaccard_similarity
//output> (11, 11, 1.0);
// (11, 13, 0.3333333333333333);
// (11, 14, 0.5);
// (12, 12, 1.0);
// ...Be careful when using jaccard_similarity on the entire graph, as in the preceding
example. For large graphs, this may be infeasible.
Compute the Jaccard similarity between a given node and every other node:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:jaccard_similarity[12]
//output> (12, 1.0);
// (13, 0.5);
// (14, 0.25);
Compute the Jaccard similarity between all nodes in a subset of nodes of a graph:
```rel
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def my_nodes = {11; 12}
def my_jaccard_similarity[u in my_nodes, v in my_nodes] =
my_graphlib:jaccard_similarity[u, v]
def output = my_jaccard_similarity
//output> (11, 11, 1.0);
// (12, 12, 1.0)cosine_similarity
View sourcecosine_similarity
cosine_similarity[u]
cosine_similarity[u, v]
cosine_similarity(u, v, score)cosine_similarity computes the cosine similarity between every node and every other
node in G. cosine_similarity[u] computes the cosine similarity between u and
every other node in G. cosine_similarity[u, v] computes the cosine similarity b
etween u and v in G. cosine_similarity(u, v, score) checked whether score is
the cosine similarity between u and v.
Parameters
| Parameter | Type | Description |
|---|---|---|
u | G:node | A node in G. |
v | G:node | A node in G. |
score | Float | The cosine similarity between nodes u and v. |
Explanation
The cosine similarity between two nodes u and v in a graph is defined as the inner
product of the two vectors representing the neighborhoods of u and v. Two identical
nodes have a cosine similarity of 1.
Examples
Compute the cosine similarity between two nodes:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:cosine_similarity[12, 14]
//output> 0.408248290463863Compute the cosine similarity on the whole graph:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:cosine_similarity
//output> (11, 11, 1.0);
// (11, 13, 0.5773502691896257);
// (11, 14, 0.7071067811865476);
// (12, 12, 1.0);
// ...Be careful when using cosine_similarity on the entire graph, as in the preceding
example. For large graphs, this may be infeasible.
Compute the cosine similarity between a given node and every other node:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:cosine_similarity[12]
//output> (12, 1.0);
// (13, 0.6666666666666666);
// (14, 0.408248290463863);
// ...Compute the cosine similarity between all nodes in a subset of nodes of a graph:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def my_nodes = {11; 12}
def my_cosine_similarity[u in my_nodes, v in my_nodes] =
my_graphlib:cosine_similarity[u, v]
def output = my_cosine_similarity
//output> (11, 11, 1.0);
// (12, 12, 1.0)preferential_attachment
View sourcepreferential_attachment
preferential_attachment[u]
preferential_attachment[u, v]
preferential_attachment(u, v, score)preferential_attachment computes the preferential attachment score between every node
and every other node in G. preferential_attachment[u] computes the preferential
attachment score between u and every other node in G. preferential_attachment[u, v]
computes the preferential attachment score between u and v in G.
preferential_attachment(u, v, score) checked whether score is the preferential
attachment score between u and v.
Parameters
| Parameter | Type | Description |
|---|---|---|
u | G:node | A node in G. |
v | G:node | A node in G. |
score | Int | The preferential attachment between node u and v. |
Explanation
The preferential attachment score between two nodes u and v is the
number of nodes adjacent to u multiplied by the number of nodes adjacent to v.
Examples
Compute the preferential attachment score between two given nodes:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:preferential_attachment[11, 13]
//output> 3Compute preferential attachment scores on a whole graph:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:preferential_attachment
//output> (11, 11, 1);
// (11, 12, 3);
// (11, 13, 3);
// (11, 14, 2);
// ...Be careful when using preferential_attachment on the entire graph, as in the preceding
example. For large graphs, this may be infeasible.
Compute the preferential attachment scores between a given node and every other node:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:preferential_attachment[11]
//output> (11, 1);
// (12, 3);
// (13, 3);
// (14, 2)Compute the preferential attachment scores between all nodes in a subset of nodes of a graph:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def my_nodes = {11; 12}
def my_preferential_attachment[u in my_nodes, v in my_nodes] =
my_graphlib:preferential_attachment[u, v]
def output = my_preferential_attachment
//output> (11, 11, 1);
// (11, 12, 3);
// (12, 11, 3);
// (12, 12, 9)adamic_adar
View sourceadamic_adar
adamic_adar[u]
adamic_adar[u, v]
adamic_adar(u, v, score)adamic_adar computes the Adamic-Adar index between every pair of nodes inG.
adamic_adar[u] computes the Adamic-Adar index between u and every other node in G.
adamic_adar[u, v] computes the Adamic-Adar index between u and v in G.
adamic_adar(u, v, score) checks thatscore is the Adamic-Adar index between u and
v.
Parameters
| Parameter | Type | Description |
|---|---|---|
u | G:node | A node in G. |
v | G:node | A node in G. |
score | Float | The Adamic-Adar index between nodes u and v. |
Explanation
The Adamic Adar index (opens in a new tab)
measures the similarity of two nodes u and v according to the amount of shared edges
between them.
Examples
Compute the Adamic-adar index between two given nodes:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:adamic_adar[12, 14]
//output> 0.9102392266268373Compute the Adamic-Adar index on the whole graph:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:adamic_adar
//output> (11, 11, 0.9102392266268373);
// (11, 13, 0.9102392266268373);
// (11, 14, 0.9102392266268373);
// (12, 12, Infinity)
// ...Be careful when using adamic_adar on the entire graph, as in the preceding example.
For large graphs, this may be infeasible.
Compute the Adamic-Adar index between a given node and every other node:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:adamic_adar[12]
//output> (12, Infinity);
// (13, 2.352934267515801);
// (14, 0.9102392266268373);Compute the Adamic-Adar index between all nodes in a subset of nodes of a graph:
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def my_nodes = {11; 12}
def my_adamic_adar[u in my_nodes, v in my_nodes] = my_graphlib:adamic_adar[u, v]
def output = my_adamic_adar
//output> (11, 11, 0.9102392266268373);
// (12, 12, Infinity)common_neighbor
View sourcecommon_neighbor
common_neighbor[u]
common_neighbor[u, v]
common_neighbor(u, v, w)common_neighbor computes the common neighbors between every pair of nodes in G.
common_neighbor[u] computes the common neighbors between u and v for every node
v in G. common_neighbor[u, v] computes the common neighbors of u and v in G.
common_neighbor(u, v, w) checks that w is a common neighbor of u and v.
Parameters
| Parameter | Type | Description |
|---|---|---|
u | G:node | A node in G. |
v | G:node | A node in G. |
w | G:node | A common neighbor between nodes u and v. |
Examples
def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:common_neighbor[12, 14]
//output> 13