The amount of pairwise similarity calculations is then linear in the number of nodes times the average number of neighbors in V 2 , which is much better.
in the case of WordNet, each node (synset) has 36 synsets in its V 2 on average, and half of the nodes do not have any neighbors at all.