# What is the "common neighborhood" of a single vertex in a graph?

In the paper "On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types" the authors propose an improvement to an algorithm, by sorting candidate vertices by "common neighborhood size" (page 8 at left).

What is the "common" neighborhood for a single vertex?

• A "neighborhood" of a vertex is the set of vertices it is adjacent to, so "common neighborhood size" would most likely mean "vertices of the same degree." Commented Dec 24, 2018 at 22:11

Given two vertices $$x$$ and $$y$$, $$N(x, y) = N(x) \cap N(y)$$ is the common neighbourhood of those two vertices where the size would be denoted as $$|N(x) \cap N(y)|$$.
$$N(x, x) = N(x) \cap N(x) = N(x) \tag{Idempotent law}$$
I think the authors of the paper are primarily concerned with comparing distinct vertices in partition $$V$$. This is covered in section "Candidate selection" which describes why selecting candidates in non-decreasing order of common neighbourhood size might reduce the number of non-maximal subsets that the algorithm has to generate. So in Figure 5 for graph $$G_4$$, they are sorting based on $$|N(v_i, v_{j})|$$, which in this example results in the algorithm not picking candidate vertex $$v_1$$ first.