# Graph Library (`graphlib`

) — Measures Extension

A library extension to `graphlib`

containing various similarity and other measures.

## Module: rel:graphlib

View source`rel: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 source```
jaccard_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`

.

Supported Graph Types

Graph Type | Supported | Notes |
---|---|---|

Undirected | Yes | |

Directed | Yes | |

Weighted | Yes | Edge weights not considered. |

Unweighted | Yes |

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.25
```

Compute 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)
```

### weighted_jaccard_similarity

View source``weighted_jaccard_similarity(u, v, score)``

Compute the weighted Jaccard index as the `score`

between every pair of nodes `u`

and
`v`

in a weighted graph.

Supported Graph Types

Graph Type | Supported | Notes |
---|---|---|

Undirected | Yes | |

Directed | Yes | |

Weighted | Yes | |

Unweighted | No |

Parameters

Parameter | Type | Description |
---|---|---|

`u` | `G:node` | A node in `G` . |

`v` | `G:node` | A node in `G` . |

Explanation

In weighted graphs, the weighted Jaccard index considers the weights of the edges to
compute the similarity between two nodes. We use the definition linked in the reference
below. The weighted jaccard similarity between two nodes `u`

and `v`

is the ratio
between the following two quantities:
(1) For every node in the graph, find the minimum weight of the edge between that
node and either `u`

or `v`

, and sum these minimum weights. This is the numerator.
(2) For every node in the graph, find the maximum weight of the edge between that
node and either `u`

or `v`

, and sum these maximum weights. This is the denominator.

If an edge does not exist between any two nodes, the weight is understood to be 0.0. This can be better understood via an example. In the example below, we show this computation on a small graph (same graph used in the Rel script below). Note that in the case of a directed graph, we consider the out-edges only.

node id | edge weights attached to node 1 | edge weights attached to node 2 | min | max |
---|---|---|---|---|

1 | 0.0 | 1.6 | 0.0 | 1.6 |

2 | 1.6 | 0.0 | 0.0 | 1.6 |

3 | 1.4 | 0.46 | 0.46 | 1.4 |

4 | 0.0 | 0.0 | 0.0 | 0.0 |

The weighted Jaccard similarity between node 1 and 2 is then:
`0.46 / (1.6 + 1.6 + 1.4) = 0.1`

.

Examples

Compute the weighted Jaccard similarity between two nodes:

```
def W = {
(1, 2, 1.6);
(1, 3, 1.4);
(2, 3, 0.46);
(3, 4, 2.5)
}
def G = create_graph[{(:weight, W)}, {(:is_weighted)}]
@inline def my_graphlib = rel:graphlib[G]
def output = my_graphlib:weighted_jaccard_similarity[1, 2]
//output> 0.1
```

Reference

Frigo M, Cruciani E, Coudert D, Deriche R, Natale E, Deslauriers-Gauthier S. Network alignment and similarity reveal atlas-based topological differences in structural connectomes. Netw Neurosci. 2021 Aug 30;5(3):711-733. doi: 10.1162/netn_a_00199. PMID: 34746624; PMCID: PMC8567827.

### cosine_similarity

View source```
cosine_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`

.

Supported Graph Types

Graph Type | Supported | Notes |
---|---|---|

Undirected | Yes | |

Directed | No | |

Weighted | Yes | |

Unweighted | Yes | Weights not considered. |

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`

. For example,
the neighborhood vector of `u`

is indexed by `G:node`

and value 1 and 0 represents
whether there is an edge between `u`

and the indexed node for non-weighted graphs and
weights for weighted graph. 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.408248290463863
```

Compute 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)
```

### weighted_cosine_similarity

View source
`weighted_cosine_similarity(u, v, score)`

`weighted_cosine_similarity`

computes the cosine similarity between every node and every
other node in a weighted graph `G`

.

Supported Graph Types

Graph Type | Supported | Notes |
---|---|---|

Undirected | Yes | |

Directed | Yes | |

Weighted | Yes | |

Unweighted | No |

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 weighted cosine similarity between two nodes `u`

and `v`

in a graph is defined
as the inner product of the two vectors representing their neighborhoods, weighted
by the edges. The weighted neighborhood vector of a node `u`

is an `N`

-dimensional
vector, where `N`

is the number of nodes in the graph, whose `i`

th component is the
weight of the edge between `u`

and the `i`

th node, or 0 if no edge exists. Values
range from -1.0 to 1.0. Two identical nodes have a cosine similarity of 1.0.

Examples

Compute the weighted cosine similarity:

```
def my_weighted_edges = {
(1, 2, 1.6);
(1, 3, 1.4);
(2, 3, 1.2);
(3, 4, 2.5);
(14, 13, 1)
}
def my_weighted_graph = create_graph[{(:weight, my_weighted_edges)}, {(:is_weighted)}]
@inline def my_graphlib = rel:graphlib[my_weighted_graph]
def output = my_graphlib:weighted_cosine_similarity[1, 2]
// ouput> 0.395103
```

### preferential_attachment

View source```
preferential_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`

.

Supported Graph Types

Graph Type | Supported | Notes |
---|---|---|

Undirected | Yes | |

Directed | Yes | |

Weighted | No |

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> 3
```

Compute 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 source```
adamic_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 in`G`

.
`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 that`score`

is the Adamic-Adar index between `u`

and
`v`

.

Supported Graph Types

Graph Type | Supported | Notes |
---|---|---|

Undirected | Yes | |

Directed | Yes | |

Weighted | No |

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.9102392266268373
```

Compute 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 source```
common_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`

.

Supported Graph Types

Graph Type | Supported | Notes |
---|---|---|

Undirected | Yes | |

Directed | Yes | |

Weighted | Yes | Ignores weights. |

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
```