 PGX 20.1.1
Documentation

## Conductance

##### Categorystructure evaluationAlgorithm IDpgx_builtin_s3_conductanceTime ComplexityO(V) with V = number of verticesSpace RequirementO(1)JavadocAnalyst#conductance(PgxGraph graph, Partition partition, long partitionIndex) Analyst#conductance(PgxGraph graph, Partition partition, long partitionIndex, Scalar conductance)

Conductance in a graph is computed for a specific cut of it. A cut is a partition of the graph into two subsets (components), disconnecting the graph if the edges from the cut are removed. Thus the algorithm requires a labeling for the vertices in the different subsets of the graph, then the conductance is computed by the ratio of the edges belonging to the given cut (i.e. the edges that split the graph into disconnected components) and the edges belonging to each of these subsets. If there is more than one cut (or partition), this implementation will take the given component number as reference to compute the conductance associated with that particular cut.

## Signature

Input Argument Type Comment
G graph
member nodeProp vertex property with the component label for each vertex in the graph.
num long number of the component to be used for computing its conductance.
Return Value Type Comment
double conductance value of the graph cut.

## Code

```/*
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;

import static java.lang.Double.POSITIVE_INFINITY;

@GraphAlgorithm
public class Conductance {
public double conductance(PgxGraph g, VertexProperty<Long> member, long num) {
long dIn = g
.getVertices()
.filter(u -> member.get(u) == num)
.sum(PgxVertex::getOutDegree);

long dOut = g
.getVertices()
.filter(u -> member.get(u) != num)
.sum(PgxVertex::getOutDegree);

long cross = g
.getVertices()
.filter(u -> member.get(u) == num)
.sum(u -> u.getNeighbors().filter(j -> member.get(j) != num).size());

double m = dIn < dOut ? dIn : dOut;

if (m == 0) {
return cross == 0 ? 0.0 : POSITIVE_INFINITY;
} else {
return cross / m;
}
}
}
```
```/*
*/

procedure conductance(graph G, nodeProp<long> member, long num) : double {

long d_in = sum (u:G.nodes) (u.member == num) {u.degree()};
long d_out = sum (u:G.nodes) (u.member != num) {u.degree()};
long cross = sum (u:G.nodes) (u.member == num) {count (j: u.nbrs) (j.member != num)};

double m = d_in < d_out ? d_in : d_out;
if (m == 0) {
return cross == 0 ? 0.0 : INF;
} else {
return cross / m;
}
}
```