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".


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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.