Depende de qué tan grande sea su gráfico, qué patrones de densidad espera y qué tan aproximada puede ser la búsqueda. Una técnica simple es calcular, para cada vértice, el número de otros vértices dentro de k = 2 (o k = 3) saltos lejos de él. Esta es una medida de densidad local, por lo que puede elegir varios vértices con muchos vecinos cercanos e intentar “hacer crecer” un subgrafo a partir de ella incluyendo iterativamente los vecinos cercanos que también tienen muchos vecinos cercanos.
Si desea algo más elegante, puede usar un enfoque de arriba hacia abajo que usaría una partición equilibrada de min-cut del gráfico de forma recursiva para crear muchos subgrafos pequeños que luego pueden comparar entre sí. Pero la partición equilibrada es NP-hard, por lo que tendrá que usar heurísticas, y no son fáciles de implementar. Entonces, iría con el enfoque ascendente más simple primero.
”