Of Notes

Node Similarity

2 min read · revised 16 October 2026 · referred to by 2 notes · ·

Node Cosine Similarity

How similar are two nodes?

This is a measure between the neighborhood sets of two nodes:

Which in English is the intersection of the two sets, normalized.

The neighborhood sets \(\partial_i\) (faint, left) and \(\partial_j\) (muted, right) of the accented nodes \(i\) and \(j\); the shared neighbors \(a\) and \(b\) sit in \(\partial_i \cap \partial_j\) and are counted by the numerator, so \(\sigma_{ij} = 2/\sqrt{4 \cdot 5}\).
Fig. 1. The neighborhood sets (faint, left) and (muted, right) of the accented nodes and ; the shared neighbors and sit in and are counted by the numerator, so .

If either node has a degree of then . The range of the outputs of this function is between and .

Node Pearson Correlation Similarity

This new kind of similarity can also be negative.

As then since the denominators explode.

We start by constructing a joint probability distribution for the nodes which will measure a ratio over some new node that falls into 4 distinct categories:

  • Nodes connected to both and .
  • Connected to but not .
  • Connected to but not .
  • Connected to neither nor .

where the Kronecker delta and act as a kind of filter.

We can then define the similarity as the which when expanded:

where the numerator is the covariance of the two rows minus its chance-level value , and the denominators normalize by the standard deviations, exactly as in Pearson Correlation. As with fixed degrees the correction terms vanish and . The result ranges over , so unlike the cosine measure it can be negative, meaning and share fewer neighbors than random chance would predict.

/ or Ctrl K
search; empty, it shows notes to revise and lately read
m
mark this note to revise, or unmark it
c
cover maths, proofs and solutions to test yourself
n
uncover the next covered item
y
copy this note’s org-roam link
e
copy this note as markdown, LaTeX kept as TeX
p
the next problem to work; there h hints, s shows the solution, x passes it for today
→ ← j k space
turn the page, when reading in pages
l
on the map, trace the greatest distance, then the longest path
double-click
a formula, to copy its TeX
rest on maths
bind a part of a formula and open the wheel of notes it comes from; scroll or ↑ ↓ widens it, 1–6 goes
?
this card