Salton's Cosine

up:: 041 MOC Graph Theory

Given an Adjacency Matrix for a Simple Graph, one can calculate the similarity between nodes by comparing the neighbors of each, through their rows¹ in the adjacency matrix, respectively.

Thus, each node has a corresponding vector , and their cosine similarity is

In terms of powers of the adjacency matrix, and noting that is ‘s Node Degree², one can re-write this as

since measures the number of 2-paths between nodes. We also define if and are in disjoint components³.

An alternative way to measure similarity between nodes is the Jaccard Similarity, which is the fraction of common neighbors over all distinct shared neighbors.

---

References

• NEWMAN, Mark. Networks. Oxford University Press, 2018.

Footnotes

1. Using the convention that corresponds to an edge going from towards . ↩

2. Note that this makes sense for undirected networks and not necessarily for directed networks, since . That is, is (the square root of) the number of 2-loops of node , which coincide with ‘s degree for undirected networks (for directed networks, this needs not apply). ↩

3. A rationalization of this would be that, since nodes with similarity can’t reach each other, they might as well be entirely disconnected from the entire network, as far as “being connected to each other” goes! ↩