For a finite simple graph $G$ and a natural number $p$, the neighbourhood complexity $π_G(p)$ is the maximum, over sets $X$ of $p$ vertices, of the number of distinct traces on $X$ of the neighbourhoods of vertices outside $X$. A graph class has linear neighbourhood complexity if $π_G(p)$ is bounded by a constant multiple of $p$ for every positive $p$.