PGX 20.2.2
Documentation

## Conductance Minimization (Soman and Narang Algorithm)

##### Categorycommunity detectionAlgorithm IDpgx_builtin_c2_community_detection_conductance_minimizationTime ComplexityO(E * k) with E = number of edges, k <= maximum number of iterationsSpace RequirementO(5 * V + 2 * E) with V = number of vertices, E = number of edgesJavadocAnalyst#communitiesConductanceMinimization(PgxGraph graph) Analyst#communitiesConductanceMinimization(PgxGraph graph, int max) Analyst#communitiesConductanceMinimization(PgxGraph graph, int max, VertexProperty partitonDistribution) Analyst#communitiesConductanceMinimization(PgxGraph graph, VertexProperty partitonDistribution)

The algorithm proposed by Soman and Narang to find community structures in a graph can be regarded as a variant of the label propagation algorithm, since it takes into account weights over the edges when looking for the community assignments. This implementation generates the weight of the edges by using the triangles in the graph, and just like label propagation, it assigns a unique community label to each vertex in the graph at the beginning, which is then updated on each iteration by looking and choosing the most frequent label from the labels of their neighbors. Convergence is achieved once the label of each vertex is the same as the most frequent one amongst its neighbors, i.e. when there are no changes in the communities assigned to the vertices in one iteration.

## Signature

Input Argument Type Comment
G graph
max_iterations int maximum number of iterations that will be performed. For most graphs, a maximum of 100 iterations should be enough.
Output Argument Type Comment
label vertexProp vertex property holding the label of the community assigned to each vertex.
Return Value Type Comment
long returns the total number of communities found.

## Code

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

import oracle.pgx.algorithm.EdgeProperty;
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.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Reduction.updateMaxValue;
import static oracle.pgx.algorithm.Traversal.inBFS;
import static java.lang.Double.NEGATIVE_INFINITY;

@GraphAlgorithm
public class SomanNarang {
public long communityDetection(PgxGraph g, int maxIterations, @Out VertexProperty<Long> communityId) {
VertexProperty<PgxVertex> community = VertexProperty.create();

//count triangles for edge_weights
EdgeProperty<Integer> triangles = EdgeProperty.create();
g.getEdges().forEach(e -> {
PgxVertex src = e.sourceVertex();
PgxVertex dest = e.destinationVertex();

Scalar<Integer> numTriangles = Scalar.create(0);
src.getNeighbors().forEach(v -> {
if (dest.hasEdgeTo(v)) {
numTriangles.increment();
}
});
triangles.set(e, numTriangles.get());
});

EdgeProperty<Double> edgeWeight = EdgeProperty.create();
edgeWeight.setAll(0.0);
//compute edge_weights
g.getVertices().forEach(n -> {
int s = n.getOutEdges().sum(triangles);
if (s != 0) {
n.getOutEdges().forEach(e -> edgeWeight.set(e, (double) triangles.get(e) / s));
}
});

VertexProperty<PgxVertex> communityAux = VertexProperty.create();
VertexProperty<Double> weight = VertexProperty.create();
//compute node weights
g.getVertices().forEach(n -> {
community.set(n, n);
communityAux.set(n, n);
weight.set(n, n.getOutEdges().max(e -> (double) triangles.get(e)));
});

VertexProperty<Long> communityDegree = VertexProperty.create();
communityDegree.setAll(PgxVertex::getOutDegree);

//use BFS to give neighboring nodes with equal weights the same community
g.getVertices().forSequential(n -> {
if (community.get(n) == n) { //handle only unhandled nodes
inBFS(g, n).navigator(v -> community.get(v) == v && weight.get(v) == weight.get(n)).forward(v -> {
PgxVertex old = community.get(v);
PgxVertex newV = community.get(n);
community.set(v, newV);
});
}
});

int iteration = 0;
Scalar<Boolean> stable = Scalar.create(false);
while (!stable.get() && iteration < maxIterations) {
stable.set(true);

g.getVertices().forEach(n -> {
double maxValue = NEGATIVE_INFINITY;
PgxVertex c = community.get(n);
n.getInEdges().forSequential(e -> {
PgxVertex i = e.sourceVertex();
PgxVertex comm = community.get(i);
int sumTriangles = i.getOutEdges().sum(triangles);
if (sumTriangles != 0) {
updateMaxValue(maxValue,
triangles.get(e) * (1 - ((double) communityDegree.get(comm) / (2 * g.getNumEdges()))))
.andUpdate(c, comm);
}
});
communityAux.set(n, c);
});

g.getVertices().forEach(n -> {
PgxVertex old = community.get(n);
PgxVertex newV = communityAux.get(n);
if (old != newV) {
community.set(n, newV);
stable.set(false);
}
});

iteration++;
}

Scalar<Long> id = Scalar.create(0L);
g.getVertices().forSequential(x -> {
if (community.get(x) == x) {
communityId.set(x, id.get());
id.increment();
}
});

g.getVertices().forSequential(x -> {
PgxVertex n = community.get(x);
communityId.set(x, communityId.get(n));
});

return id.get();
}
}
```
```/*
*/

procedure community_detection(graph G, int max_iterations; vertexProp<long> community_id) : long {

vertexProp<node> community;

//count triangles for edge_weights
edgeProp<int> triangles;
foreach (e: G.edges) {
node src = e.fromNode();
node dest = e.toNode();

int numTriangles = 0;
foreach (v: src.nbrs) {
if (dest.hasEdgeTo(v)) {
numTriangles++;
}
}
e.triangles = numTriangles;
}

edgeProp<double> edge_weight;
G.edge_weight = 0.0;
//compute edge_weights
foreach (n: G.nodes) {
int s = sum (out: n.outEdges) {out.triangles};
if(s != 0) {
foreach (e: n.outEdges) {
e.edge_weight = (double) e.triangles / s;
}
}
}

vertexProp<node> community_aux;
vertexProp<double> weight;
//compute node weights
foreach (n: G.nodes) {
n.community = n;
n.community_aux = n;
n.weight = max(e: n.outEdges) {e.triangles};
}

vertexProp<int> community_degree;
G.community_degree = (int) _.outDegree();

//use BFS to give neighboring nodes with equal weights the same community
for (n: G.nodes) {
if (n.community == n) { //handle only unhandled nodes
inBFS (v: G.nodes from n) [v.community == v && v.weight == n.weight] {
node old = v.community;
node new = n.community;
v.community = new;
old.community_degree += (int) (-1 * v.outDegree());
new.community_degree += (int) v.outDegree();
}
}
}

int iteration = 0;
bool stable = false;
while (!stable && iteration < max_iterations) {
stable = true;

foreach (n: G.nodes)  {
double maxValue = -INF;
node c = n.community;
for (e: n.inEdges) {
node i = e.fromNode();
node comm = i.community;
int sumTriangles = sum (z: i.outEdges) {z.triangles};
if (sumTriangles != 0) {
<maxValue; c> max= <e.triangles * (1 - ((double) comm.community_degree / (2.0 * G.numEdges()))); comm>;
}
}
n.community_aux = c;
}

foreach (n: G.nodes) {
node old = n.community;
node new = n.community_aux;
if (old != new) {
n.community = new;
old.community_degree += (int) (-1 * n.outDegree());
new.community_degree += (int) n.outDegree();
stable = false;
}
}
iteration++;
}

long id = 0;
for (x: G.nodes) {
if (x.community == x) {
x.community_id = id;
id ++;
}
}
for (x:G.nodes) {
node n = x.community;
x.community_id = n.community_id;
}

return id;
}
```