# Divide directed weighted graph into two parts

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?

• What's the target? – xskxzr Aug 26 '19 at 16:29
• 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." – Tassle Aug 26 '19 at 17:04