I wanted to compute the conductance of three partitions S', S'' and S''' resulting for multiple cuts on a graph G.

However, the networkx conductance function computes the conductance given two partitions S' and S'' as described in https://networkx.github.io/documentation/latest/reference/algorithms/generated/networkx.algorithms.cuts.conductance.html

Also in wikipedia, the conductance is defined for two given partitions: https://en.wikipedia.org/wiki/Conductance_(graph)

The question at this point is: how can the conductance be computed having not two partitions S' and S'' but three, with S'''?

One idea was to perform a pairwise computation of the nominator:

\sum_{i \in S', j \in S''} a_{ij} + \sum_{i \in S', k \in S'''} a_{ik} + \sum_{j \in S'', k \in S'''} a_{jk} 

and to include the a(S''') in the denominator. But I am not sure if this approach works that simple. This is basically just computing the sum of the pairwise connections between each of the partitions.

Best regards

0 Answers