Hello,
Would it be possible to expand on how to actually find the set S that that minimizes the conductance? It is not entirely clear to me how we get from Phi(S) to Phi, as we could have an exponential number of possible partitions.
Thank you in advance.
Usually (for example, in the exercises), you can come up with this set S yourself (deduce the best cut from the graph shape).
I don't think there's a quick way to determine the best partition for an arbitrary graph. Of course you can use exhaustive checking but this does not scale so we usually prefer greedy algorithms (for example, you will later talk about the Louvain algorithm).
Conductance of a graph
Hello,
Would it be possible to expand on how to actually find the set S that that minimizes the conductance? It is not entirely clear to me how we get from Phi(S) to Phi, as we could have an exponential number of possible partitions.
Thank you in advance.
Usually (for example, in the exercises), you can come up with this set S yourself (deduce the best cut from the graph shape).
I don't think there's a quick way to determine the best partition for an arbitrary graph. Of course you can use exhaustive checking but this does not scale so we usually prefer greedy algorithms (for example, you will later talk about the Louvain algorithm).
2
Add comment