Skip to content
Library: graphlib (measures)

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:

MeasureDescription
jaccard_similarityA similarity measure between two nodes using the Jaccard index.
cosine_similarityA similarity measure between two nodes using the cosine between their neighborhood vectors.
preferential_attachmentA score between two nodes using preferential attachment.
adamic_adarA measure between two nodes using the Adamic-Adar index.
common_neighborA 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 TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedYesEdge weights not considered.
UnweightedYes

Parameters

ParameterTypeDescription
uG:nodeA node in G.
vG:nodeA node in G.
scoreFloatThe 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 TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedYes
UnweightedNo

Parameters

ParameterTypeDescription
uG:nodeA node in G.
vG:nodeA 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 idedge weights attached to node 1edge weights attached to node 2minmax
10.01.60.01.6
21.60.00.01.6
31.40.460.461.4
40.00.00.00.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 TypeSupportedNotes
UndirectedYes
DirectedNo
WeightedYes
UnweightedYesWeights not considered.

Parameters

ParameterTypeDescription
uG:nodeA node in G.
vG:nodeA node in G.
scoreFloatThe 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 TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedYes
UnweightedNo

Parameters

ParameterTypeDescription
uG:nodeA node in G.
vG:nodeA node in G.
scoreFloatThe 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 ith component is the weight of the edge between u and the ith 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 TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedNo

Parameters

ParameterTypeDescription
uG:nodeA node in G.
vG:nodeA node in G.
scoreIntThe 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 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.

Supported Graph Types

Graph TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedNo

Parameters

ParameterTypeDescription
uG:nodeA node in G.
vG:nodeA node in G.
scoreFloatThe 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 TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedYesIgnores weights.

Parameters

ParameterTypeDescription
uG:nodeA node in G.
vG:nodeA node in G.
wG:nodeA 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
Was this doc helpful?