Modularity in a graph is a measure for assessing the quality of the partition induced by the components (or community structures) within the graph found by any clustering algorithm (e.g. label propagation, Infomap, WCC, etc.). It compares the number of the edges between the vertices within a component against the expected number of edges if these were generated at random (assuming a uniform probability distribution). A possitive modularity value means that, on average, there are more edges within the components than the amount expected (meaning stronger components), and viceversa for a negative modularity value. This implementation is intended for directed graphs.
Input Argument | Type | Comment |
---|---|---|
G | graph | |
member | vertexProp |
vertex property with the component label for each vertex in the graph. |
num_comp | long | number of components in the graph found by any clustering algorithm. |
Return Value | Type | Comment |
---|---|---|
double | modularity value corresponding to the given components in the graph. |
/* * 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; @GraphAlgorithm public class PartitionModularity { public double modularitySmallPartition(PgxGraph g, VertexProperty<Long> member, long numComp) { Scalar<Double> firstTerm = Scalar.create(0D); double secondTerm = 0; double m1 = 1 / (double) g.getNumEdges(); // compute first term: fraction of edges inside community g.getVertices().forEach(n -> { n.getNeighbors().forEach(m -> { if (member.get(n) == member.get(m)) { firstTerm.increment(); } }); }); firstTerm.set(firstTerm.get() * m1); // compute second term: expected number of edges inside community when // uniform Scalar<Long> num = Scalar.create(0L); while (num.get() < numComp) { long dIn = g.getVertices().filter(u -> member.get(u) == num.get()).sum(PgxVertex::getInDegree); long dOut = g.getVertices().filter(u -> member.get(u) == num.get()).sum(PgxVertex::getOutDegree); secondTerm += m1 * dIn * dOut; // avoid overflow num.increment(); } secondTerm = secondTerm * m1; return firstTerm.get() - secondTerm; } }
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ procedure modularity_small_partition(graph G, vertexProp<long> member, long num_comp) : double { double first_term = 0; double second_term = 0; double m_1 = 1 / (double) G.numEdges(); // compute first term: fraction of edges inside community foreach (n: G.nodes) { foreach (m: n.nbrs) { if (n.member == m.member) { first_term++; } } } first_term = first_term * m_1; // compute second term: expected number of edges inside community when // uniform long num = 0; while (num < num_comp) { long d_in = sum (u: G.nodes) (u.member == num) {u.inDegree()}; long d_out = sum (u: G.nodes) (u.member == num) {u.outDegree()}; second_term += m_1 * d_in * d_out; // avoid overflow num++; } second_term = second_term * m_1; return first_term - second_term; }