Common neighbors

Common neighbor is a directly heuristic method in many graph applications, like paper:Liben-Nowell Kleinberg J. Am.Soc.Inf.Sci.2007.

Formal Definition

Say $x,y$ are two nodes in the graph, $\Gamma (x)$ means neighbors of $x$. Common neighbors of $x$ and $y$ consist the set: $\Gamma (x)\cap \Gamma (y)$.

In many applications, only $|\Gamma (x)\cap \Gamma (y)|$ is considered.