CODEWITHSUNDEEP
graphnetworkxpartitioning
Daniyal
Daniyal

Reputation: 905

Python networkx: computing conductance for multiple cuts

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

Upvotes: 1

Views: 1068

Answers (1)

Magda Anastasiadou
Magda Anastasiadou

Reputation: 81

According to wikipedia

The conductance of the whole graph is the minimum conductance over all the possible cuts https://en.wikipedia.org/wiki/Conductance_(graph)

So, you can compute it as this as I understand

score = min(nx.conductance(g, cluster_i, weight='weight')
            for cluster_i in clusters_list)

Upvotes: 2

Related Questions