Given a graph, test if some vertices are more connected than the background

Question

I have a neighborhood graph of some 10k vertices (a k-NN graph of single-cell RNA-seq data).

I am interested if a given set of vertices is more connected to each other than you would expect by chance. In particular I am looking for

• a score that describes how connected the vertices are and
• a statistical test that tells me if the vertices are more connected than a randomly chosen set of vertices.

The score should be comparable between different sets of vertices, s.t. I can conclude the vertices in set "A" are more connected than those in set "B".

EDIT

I though about

• as a score: dividing the number of edges in the subgraph by the number of possible edges in the subgraph, i.e. $S = \frac{|E|}{\frac{|V|(|V|-1)}{2}}$

• For the test: generating a background distribution by randomly sampling sets with the same number of vertices from the graph

But I have the feeling there must be a more standardized metric?

Answer 1

What you are looking for, I think, is the now classical graph modularity. It is usually computed on an entire graph partition, but it may as well be computed for only a specific part.

You may also find inspiration from the various graph partition quality functions used in the literature; I suggest you have a look at: A Generalized and Adaptive Method for Community Detection by Romain Campigotto, Patricia Conde Céspedes, and Jean-Loup Guillaume.