PGX 20.1.1
Documentation

Partition Conductance

Category structure evaluation

Algorithm ID pgx_builtin_s5_partition_conductance

Time Complexity O(E) with E = number of edges

Space Requirement O(1)

Javadoc


This variant of the conductance algorithm will compute the conductance for the given number of components, returning an output with the minimun value of conductance found from the corresponding partitions and their average conductance value.

Signature

Input Argument Type Comment
G graph
member nodeProp vertex property with the component label for each vertex in the graph.
num_comp long number of components in the graph.
Output Argument Type Comment
min_cond double minimum conductance value found from the given partitions.
Return Value Type Comment
double average conductance value of the partitions in the graph.

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

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

@GraphAlgorithm
public class PartitionConductance {
  public double conductanceSmallPartition(PgxGraph g, VertexProperty<Long> member, long numComp,
      @Out Scalar<Double> minCond) {
    Scalar<Long> num = Scalar.create(0L);
    minCond.set(0D);
    double sumCondcond = 0;

    while (num.get() < numComp) {
      long dIn = g.getVertices() //
          .filter(u -> member.get(u) == num.get()) //
          .sum(PgxVertex::getOutDegree);

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

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

      double m = dIn < dOut ? dIn : dOut;
      double cond = m == 0 ? 0.0 : cross / m;
      minCond.reduceMin(cond);
      sumCondcond += cond;
      num.increment();
    }

    return numComp == 0 ? 0 : sumCondcond / numComp;
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure conductance_small_partition(graph G, nodeProp<long> member, long num_comp;
    double min_cond) : double {

  long num = 0;
  min_cond = 0;
  double sum_cond = 0;
  while (num < num_comp) {

    long d_in, d_out, cross;

    d_in  = sum (u:G.nodes) (u.member == num) {u.degree()};
    d_out = sum (u:G.nodes) (u.member != num) {u.degree()};
    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;
    double cond = m == 0 ? 0.0 : cross / m;
    min_cond min= cond;
    sum_cond += cond;
    num++;
  }

  return num_comp == 0 ? 0 : sum_cond / num_comp;
}