I have a directed, weighted graph $G = (E,V)$. For example, one might be $|E| = 74000, |G| = 725$.

I want to divide this graph into two parts/clusters/communities, taking the edge weights into account.

I researched several methods, but the problem is that either they automatically detect the number of parts (communities), e.g. the Louvain method, or they only work for undirected graphs, e.g. k-MST. I also considered computing a minimum cut, but my network does not have source and sink.

Which other methods are there?

  • 1
    $\begingroup$ What's the target? $\endgroup$ – xskxzr Aug 26 '19 at 16:29
  • 1
    $\begingroup$ You don't need a source and a sink to compute a minimum cut. You can just choose a random sink $s$ and take the smallest of the minimum $s-t$ cuts for all $t \neq s$. Or if this is too slow you can take a look at ""J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a directed graph." $\endgroup$ – Tassle Aug 26 '19 at 17:04

Your Answer

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

Browse other questions tagged or ask your own question.