graphology-metrics - npm Package Compare versions

Comparing version 1.8.0 to 1.9.0

modularity.d.ts

@@ -10,5 +10,31 @@ import Graph from 'graphology-types';
   },
-  communities: CommunityMapping
+  communities: CommunityMapping,
+  weighted: boolean
 };
 
-export default function modularity(graph: Graph, options?: ModularityOptions): number;
+interface IModularity {
+  (graph: Graph, options?: ModularityOptions): number;
+
+  dense(graph: Graph, options?: ModularityOptions): number;
+  sparse(graph: Graph, options?: ModularityOptions): number;
+
+  undirectedDelta(
+    M: number,
+    communityTotalWeight: number,
+    nodeDegree: number,
+    nodeCommunityDegree: number
+  ): number;
+
+  directedDelta(
+    M: number,
+    communityTotalInWeight: number,
+    communityTotalOutWeight: number,
+    nodeInDegree: number,
+    nodeOutDegree: number,
+    nodeCommunityDegree: number
+  ): number;
+}
+
+declare const modularity: IModularity;
+
+export default modularity;

modularity.js

@@ -5,19 +5,114 @@ /**
  *
- * Notes:
- * The following code is taken from Gephi and Gephi doesn't consider directed
- * edges:
+ * Implementation of network modularity for graphology.
  *
- * Directed edges produces the same modularity as if they were undirected
- *   - if there are a->b and b->a : consider a<->b
- *   - if there is a->b only or b->a only : consider ALSO a<->b
- *   - if there are a->b , b->a with differents weights, only one is considered
+ * Modularity is a bit of a tricky problem because there are a wide array
+ * of different definitions and implementations. The current implementation
+ * try to stay true to Newman's original definition and consider both the
+ * undirected & directed case as well as the weighted one. The current
+ * implementation should also be aligned with Louvain algorithm's definition
+ * of the metric.
  *
- * The order chosen by Gephi is unknown, it is a sensitive case and is not
- * handled.
+ * Note that the current implementation choses to ignore self-loops. It would
+ * be easy to consider them in the computations but I don't think they were
+ * intended to be taken into account by the metric.
  *
- * Self-loops are not considered at all, not in the total weights, not in the
- * computing part (remove them and it will be the same modularity score).
+ * Hence, here are the retained formulas:
+ *
+ * For dense weighted undirected network:
+ * --------------------------------------
+ *
+ * Q = 1/2m * [ ∑ij[Aij - (di.dj / 2m)] * ∂(ci, cj) ]
+ *
+ * where:
+ *  - i & j being a pair of nodes
+ *  - m is the sum of edge weights
+ *  - Aij being the weight of the ij edge (or 0 if absent)
+ *  - di being the weighted degree of node i
+ *  - ci being the community to which belongs node i
+ *  - ∂ is Kronecker's delta function (1 if x = y else 0)
+ *
+ * For dense weighted directed network:
+ * ------------------------------------
+ *
+ * Qd = 1/m * [ ∑ij[Aij - (dini.doutj / m)] * ∂(ci, cj) ]
+ *
+ * where:
+ *  - dini is the in degree of node i
+ *  - douti is the out degree of node i
+ *
+ * For sparse weighted undirected network:
+ * ---------------------------------------
+ *
+ * Q = ∑c[ (∑cinternal / 2m) - (∑ctotal / 2m)² ]
+ *
+ * where:
+ *  - c is a community
+ *  - ∑cinternal is the total weight of a community internal edges
+ *  - ∑ctotal is the total weight of edges connected to a community
+ *
+ * For sparse weighted directed network:
+ * -------------------------------------
+ *
+ * Qd = ∑c[ (∑cinternal / m) - (∑cintotal * ∑couttotal / m²) ]
+ *
+ * where:
+ *  - ∑cintotal is the total weight of edges pointing towards a community
+ *  - ∑couttotal is the total weight of edges going from a community
+ *
+ * Note that dense version run in O(N²) while sparse version runs in O(V). So
+ * the dense version is mostly here to guarantee the validity of the sparse one.
+ * As such it is not used as default.
+ *
+ * For undirected delta computation:
+ * ---------------------------------
+ *
+ * ∆Q = (dic / 2m) - ((∑ctotal * di) / 2m²)
+ *
+ * where:
+ *  - dic is the degree of the node in community c
+ *
+ * For directed delta computation:
+ * -------------------------------
+ *
+ * ∆Qd = (dic / m) - (((douti * ∑cintotal) + (dini * ∑couttotal)) / m²)
+ *
+ * [Latex]
+ *
+ * Sparse undirected
+ * Q = \sum_{c} \bigg{[} \frac{\sum\nolimits_{c\,in}}{2m} - \left(\frac{\sum\nolimits_{c\,tot}}{2m}\right )^2 \bigg{]}
+ *
+ * Sparse directed
+ * Q_d = \sum_{c} \bigg{[} \frac{\sum\nolimits_{c\,in}}{m} - \frac{\sum_{c\,tot}^{in}\sum_{c\,tot}^{out}}{m^2} \bigg{]}
+ *
+ * [Articles]
+ * M. E. J. Newman, « Modularity and community structure in networks »,
+ * Proc. Natl. Acad. Sci. USA, vol. 103, no 23,‎ 2006, p. 8577–8582
+ * https://dx.doi.org/10.1073%2Fpnas.0601602103
+ *
+ * Blondel, Vincent D., et al. « Fast unfolding of communities in large
+ * networks ». Journal of Statistical Mechanics: Theory and Experiment,
+ * vol. 2008, no 10, octobre 2008, p. P10008. DOI.org (Crossref),
+ * doi:10.1088/1742-5468/2008/10/P10008.
+ * https://arxiv.org/pdf/0803.0476.pdf
+ *
+ * Nicolas Dugué, Anthony Perez. Directed Louvain: maximizing modularity in
+ * directed networks. [Research Report] Université d’Orléans. 2015. hal-01231784
+ * https://hal.archives-ouvertes.fr/hal-01231784
+ *
+ * R. Lambiotte, J.-C. Delvenne and M. Barahona. Laplacian Dynamics and
+ * Multiscale Modular Structure in Networks,
+ * doi:10.1109/TNSE.2015.2391998.
+ * https://arxiv.org/abs/0812.1770
+ *
+ * [ToDo]:
+ *  - Resolution limit.
+ *
+ * [Links]:
+ * https://math.stackexchange.com/questions/2637469/where-does-the-second-formula-of-modularity-comes-from-in-the-louvain-paper-the
+ * https://www.quora.com/How-is-the-formula-for-Louvain-modularity-change-derived
+ * https://github.com/gephi/gephi/blob/master/modules/StatisticsPlugin/src/main/java/org/gephi/statistics/plugin/Modularity.java
  */
 var defaults = require('lodash/defaultsDeep'),
-    isGraph = require('graphology-utils/is-graph');
+    isGraph = require('graphology-utils/is-graph'),
+    inferType = require('graphology-utils/infer-type');
 
@@ -28,102 +123,417 @@ var DEFAULTS = {
     weight: 'weight'
-  }
+  },
+  communities: null,
+  weighted: true
 };
 
-/**
- * Function returning the modularity of the given graph.
- *
- * @param  {Graph}  graph         - Target graph.
- * @param  {object} options       - Options:
- * @param  {object}   communities - Communities mapping.
- * @param  {object}   attributes  - Attribute names:
- * @param  {string}     community - Name of the community attribute.
- * @param  {string}     weight    - Name of the weight attribute.
- * @return {number}
- */
-function modularity(graph, options) {
+function createWeightGetter(weighted, weightAttribute) {
+  return function(attr) {
+    if (!attr)
+      return 0;
 
-  // Handling errors
-  if (!isGraph(graph))
-    throw new Error('graphology-metrics/modularity: the given graph is not a valid graphology instance.');
+    if (!weighted)
+      return 1;
 
-  if (graph.multi)
-    throw new Error('graphology-metrics/modularity: multi graphs are not handled.');
+    var w = attr[weightAttribute];
 
-  if (!graph.size)
-    throw new Error('graphology-metrics/modularity: the given graph has no edges.');
+    if (typeof w !== 'number')
+      w = 1;
 
-  // Solving options
-  options = defaults({}, options, DEFAULTS);
+    return w;
+  };
+}
 
-  var communities,
-      nodes = graph.nodes(),
-      edges = graph.edges(),
-      i,
-      l;
+function collectForUndirectedDense(graph, options) {
+  var communities = new Array(graph.order),
+      weightedDegrees = new Float64Array(graph.order),
+      M = 0;
 
-  // Do we have a community mapping?
-  if (typeof options.communities === 'object') {
-    communities = options.communities;
+  var ids = {};
+
+  var getWeight = createWeightGetter(options.weighted, options.attributes.weight);
+
+  // Collecting communities
+  var i = 0;
+  graph.forEachNode(function(node, attr) {
+    ids[node] = i;
+    communities[i++] = options.communities ?
+      options.communities[node] :
+      attr[options.attributes.community];
+  });
+
+  // Collecting weights
+  graph.forEachUndirectedEdge(function(edge, attr, source, target) {
+    if (source === target)
+      return;
+
+    var weight = getWeight(attr);
+
+    M += weight;
+
+    weightedDegrees[ids[source]] += weight;
+    weightedDegrees[ids[target]] += weight;
+  });
+
+  return {
+    getWeight: getWeight,
+    communities: communities,
+    weightedDegrees: weightedDegrees,
+    M: M
+  };
+}
+
+function collectForDirectedDense(graph, options) {
+  var communities = new Array(graph.order),
+      weightedInDegrees = new Float64Array(graph.order),
+      weightedOutDegrees = new Float64Array(graph.order),
+      M = 0;
+
+  var ids = {};
+
+  var getWeight = createWeightGetter(options.weighted, options.attributes.weight);
+
+  // Collecting communities
+  var i = 0;
+  graph.forEachNode(function(node, attr) {
+    ids[node] = i;
+    communities[i++] = options.communities ?
+      options.communities[node] :
+      attr[options.attributes.community];
+  });
+
+  // Collecting weights
+  graph.forEachDirectedEdge(function(edge, attr, source, target) {
+    if (source === target)
+      return;
+
+    var weight = getWeight(attr);
+
+    M += weight;
+
+    weightedOutDegrees[ids[source]] += weight;
+    weightedInDegrees[ids[target]] += weight;
+  });
+
+  return {
+    getWeight: getWeight,
+    communities: communities,
+    weightedInDegrees: weightedInDegrees,
+    weightedOutDegrees: weightedOutDegrees,
+    M: M
+  };
+}
+
+function undirectedDenseModularity(graph, options) {
+  var result = collectForUndirectedDense(graph, options);
+
+  var communities = result.communities,
+      weightedDegrees = result.weightedDegrees;
+
+  var M = result.M;
+
+  var nodes = graph.nodes();
+
+  var i, j, l, Aij, didj;
+
+  var S = 0;
+
+  var M2 = M * 2;
+
+  for (i = 0, l = graph.order; i < l; i++) {
+
+    // Diagonal
+    // NOTE: could change something here to handle self loops
+    S += 0 - (Math.pow(weightedDegrees[i], 2) / M2);
+
+    // NOTE: it is important to parse the whole matrix here, diagonal and
+    // lower part included. A lot of implementation differ here because
+    // they process only a part of the matrix
+    for (j = i + 1; j < l; j++) {
+
+      // NOTE: Kronecker's delta
+      // NOTE: we could go from O(n^2) to O(avg.C^2)
+      if (communities[i] !== communities[j])
+        continue;
+
+      edgeAttributes = graph.undirectedEdge(nodes[i], nodes[j]);
+
+      Aij = result.getWeight(edgeAttributes);
+      didj = weightedDegrees[i] * weightedDegrees[j];
+
+      // Here we multiply by two to simulate iteration through lower part
+      S += (Aij - (didj / M2)) * 2;
+    }
   }
 
-  // Else we need to extract it from the graph
-  else {
-    communities = {};
+  return S / M2;
+}
 
-    for (i = 0, l = nodes.length; i < l; i++)
-      communities[nodes[i]] = graph.getNodeAttribute(nodes[i], options.attributes.community);
+function directedDenseModularity(graph, options) {
+  var result = collectForDirectedDense(graph, options);
+
+  var communities = result.communities,
+      weightedInDegrees = result.weightedInDegrees,
+      weightedOutDegrees = result.weightedOutDegrees;
+
+  var M = result.M;
+
+  var nodes = graph.nodes();
+
+  var i, j, l, Aij, didj;
+
+  var S = 0;
+
+  for (i = 0, l = graph.order; i < l; i++) {
+
+    // Diagonal
+    // NOTE: could change something here to handle self loops
+    S += 0 - ((weightedInDegrees[i] * weightedOutDegrees[i]) / M);
+
+    // NOTE: it is important to parse the whole matrix here, diagonal and
+    // lower part included. A lot of implementation differ here because
+    // they process only a part of the matrix
+    for (j = 0; j < l; j++) {
+
+      if (i === j)
+        continue;
+
+      // NOTE: Kronecker's delta
+      // NOTE: we could go from O(n^2) to O(avg.C^2)
+      if (communities[i] !== communities[j])
+        continue;
+
+      edgeAttributes = graph.directedEdge(nodes[i], nodes[j]);
+
+      Aij = result.getWeight(edgeAttributes);
+      didj = weightedInDegrees[i] * weightedOutDegrees[j];
+
+      // Here we multiply by two to simulate iteration through lower part
+      S += Aij - (didj / M);
+    }
   }
 
-  var M = 0,
-      Q = 0,
-      internalW = {},
-      totalW = {},
-      bounds,
-      node1, node2, edge,
-      community1, community2,
-      w, weight;
+  return S / M;
+}
 
-  for (i = 0, l = edges.length; i < l; i++) {
-    edge = edges[i];
-    bounds = graph.extremities(edge);
-    node1 = bounds[0];
-    node2 = bounds[1];
+function collectCommunitesForUndirected(graph, options) {
+  var communities = {},
+      totalWeights = {},
+      internalWeights = {};
 
-    if (node1 === node2)
-      continue;
+  if (options.communities)
+    communities = options.communities;
 
-    community1 = communities[node1];
-    community2 = communities[node2];
+  graph.forEachNode(function(node, attr) {
+    var community;
 
-    if (community1 === undefined)
-      throw new Error('graphology-metrics/modularity: the "' + node1 + '" node is not in the partition.');
+    if (!options.communities) {
+      community = attr[options.attributes.community];
+      communities[node] = community;
+    }
+    else {
+      community = communities[node];
+    }
 
-    if (community2 === undefined)
-      throw new Error('graphology-metrics/modularity: the "' + node2 + '" node is not in the partition.');
+    if (typeof community === 'undefined')
+      throw new Error('graphology-metrics/modularity: the "' + node + '" node is not in the partition.');
 
-    w = graph.getEdgeAttribute(edge, options.attributes.weight);
-    weight = isNaN(w) ? 1 : w;
+    totalWeights[community] = 0;
+    internalWeights[community] = 0;
+  });
 
-    totalW[community1] = (totalW[community1] || 0) + weight;
-    if (graph.undirected(edge) || !graph.hasDirectedEdge(node2, node1)) {
-      totalW[community2] = (totalW[community2] || 0) + weight;
-      M += 2 * weight;
+  return {
+    communities: communities,
+    totalWeights: totalWeights,
+    internalWeights: internalWeights
+  };
+}
+
+function collectCommunitesForDirected(graph, options) {
+  var communities = {},
+      totalInWeights = {},
+      totalOutWeights = {},
+      internalWeights = {};
+
+  if (options.communities)
+    communities = options.communities;
+
+  graph.forEachNode(function(node, attr) {
+    var community;
+
+    if (!options.communities) {
+      community = attr[options.attributes.community];
+      communities[node] = community;
     }
     else {
-      M += weight;
+      community = communities[node];
     }
 
-    if (!graph.hasDirectedEdge(node2, node1))
-      weight *= 2;
+    if (typeof community === 'undefined')
+      throw new Error('graphology-metrics/modularity: the "' + node + '" node is not in the partition.');
 
-    if (community1 === community2)
-      internalW[community1] = (internalW[community1] || 0) + weight;
-  }
+    totalInWeights[community] = 0;
+    totalOutWeights[community] = 0;
+    internalWeights[community] = 0;
+  });
 
-  for (community1 in totalW)
-    Q += ((internalW[community1] || 0) - (totalW[community1] * totalW[community1] / M));
+  return {
+    communities: communities,
+    totalInWeights: totalInWeights,
+    totalOutWeights: totalOutWeights,
+    internalWeights: internalWeights
+  };
+}
 
-  return Q / M;
+function undirectedSparseModularity(graph, options) {
+  var result = collectCommunitesForUndirected(graph, options);
+
+  var M = 0;
+
+  var totalWeights = result.totalWeights,
+      internalWeights = result.internalWeights,
+      communities = result.communities;
+
+  var getWeight = createWeightGetter(options.weighted, options.attributes.weight);
+
+  graph.forEachUndirectedEdge(function(edge, edgeAttr, source, target, sourceAttr, targetAttr) {
+    if (source === target)
+      return;
+
+    var weight = getWeight(edgeAttr);
+
+    M += weight;
+
+    var sourceCommunity = communities[source];
+    var targetCommunity = communities[target];
+
+    totalWeights[sourceCommunity] += weight;
+    totalWeights[targetCommunity] += weight;
+
+    if (sourceCommunity !== targetCommunity)
+      return;
+
+    internalWeights[sourceCommunity] += weight * 2;
+  });
+
+  var Q = 0,
+      M2 = M * 2;
+
+  for (var C in internalWeights)
+    Q += internalWeights[C] / M2 - Math.pow(totalWeights[C] / M2, 2);
+
+  return Q;
 }
 
+function directedSparseModularity(graph, options) {
+  var result = collectCommunitesForDirected(graph, options);
+
+  var M = 0;
+
+  var totalInWeights = result.totalInWeights,
+      totalOutWeights = result.totalOutWeights,
+      internalWeights = result.internalWeights,
+      communities = result.communities;
+
+  var getWeight = createWeightGetter(options.weighted, options.attributes.weight);
+
+  graph.forEachDirectedEdge(function(edge, edgeAttr, source, target, sourceAttr, targetAttr) {
+    if (source === target)
+      return;
+
+    var weight = getWeight(edgeAttr);
+
+    M += weight;
+
+    var sourceCommunity = communities[source];
+    var targetCommunity = communities[target];
+
+    totalOutWeights[sourceCommunity] += weight;
+    totalInWeights[targetCommunity] += weight;
+
+    if (sourceCommunity !== targetCommunity)
+      return;
+
+    internalWeights[sourceCommunity] += weight;
+  });
+
+  var Q = 0;
+
+  for (var C in internalWeights)
+    Q += (internalWeights[C] / M) - (totalInWeights[C] * totalOutWeights[C] / Math.pow(M, 2));
+
+  return Q;
+}
+
+function undirectedModularityDelta(M, communityTotalWeight, nodeDegree, nodeCommunityDegree) {
+  return (
+    (nodeCommunityDegree / (2 * M)) -
+    (
+      (communityTotalWeight * nodeDegree) / (2 * (M * M))
+    )
+  );
+}
+
+function directedModularityDelta(M, communityTotalInWeight, communityTotalOutWeight, nodeInDegree, nodeOutDegree, nodeCommunityDegree) {
+  return (
+    (nodeCommunityDegree / M) -
+    (
+      ((nodeOutDegree * communityTotalInWeight) + (nodeInDegree * communityTotalOutWeight)) /
+      (M * M)
+    )
+  );
+}
+
+function denseModularity(graph, options) {
+  if (!isGraph(graph))
+    throw new Error('graphology-metrics/modularity: given graph is not a valid graphology instance.');
+
+  if (graph.size === 0)
+    throw new Error('graphology-metrics/modularity: cannot compute modularity of an empty graph.');
+
+  if (graph.multi)
+    throw new Error('graphology-metrics/modularity: cannot compute modularity of a multi graph. Cast it to a simple one beforehand.');
+
+  var trueType = inferType(graph);
+
+  if (trueType === 'mixed')
+    throw new Error('graphology-metrics/modularity: cannot compute modularity of a mixed graph.');
+
+  options = defaults({}, options || {}, DEFAULTS);
+
+  if (trueType === 'directed')
+    return directedDenseModularity(graph, options);
+
+  return undirectedDenseModularity(graph, options);
+}
+
+function sparseModularity(graph, options) {
+  if (!isGraph(graph))
+    throw new Error('graphology-metrics/modularity: given graph is not a valid graphology instance.');
+
+  if (graph.size === 0)
+    throw new Error('graphology-metrics/modularity: cannot compute modularity of an empty graph.');
+
+  if (graph.multi)
+    throw new Error('graphology-metrics/modularity: cannot compute modularity of a multi graph. Cast it to a simple one beforehand.');
+
+  var trueType = inferType(graph);
+
+  if (trueType === 'mixed')
+    throw new Error('graphology-metrics/modularity: cannot compute modularity of a mixed graph.');
+
+  options = defaults({}, options || {}, DEFAULTS);
+
+  if (trueType === 'directed')
+    return directedSparseModularity(graph, options);
+
+  return undirectedSparseModularity(graph, options);
+}
+
+var modularity = sparseModularity;
+
+modularity.sparse = sparseModularity;
+modularity.dense = denseModularity;
+modularity.undirectedDelta = undirectedModularityDelta;
+modularity.directedDelta = directedModularityDelta;
+
 module.exports = modularity;

package.json

 {
   "name": "graphology-metrics",
-  "version": "1.8.0",
+  "version": "1.9.0",
   "description": "Miscellaneous graph metrics for graphology.",
@@ -49,3 +49,3 @@ "main": "index.js",
     "eslint": "^6.8.0",
-    "graphology": "^0.15.2",
+    "graphology": "^0.16.0",
     "graphology-generators": "^0.10.1",
@@ -68,3 +68,3 @@ "mocha": "^7.0.1"
     "graphology-shortest-path": "^1.1.1",
-    "graphology-types": "^0.15.4",
+    "graphology-types": "^0.16.0",
     "graphology-utils": "^1.6.1",
@@ -71,0 +71,0 @@ "lodash": "^4.17.11"

README.md

@@ -99,3 +99,3 @@ [![Build Status](https://travis-ci.org/graphology/graphology-metrics.svg)](https://travis-ci.org/graphology/graphology-metrics)
 
-Computes the modularity, given the graph and a partitioning
+Computes the modularity, given the graph and a node partition. It works on both directed & undirected networks and will return the relevant modularity.
 
@@ -110,3 +110,3 @@ ```js
 
-// If community mapping is external to the graph
+// If the partition is not given by node attributes
 const Q = modularity(graph, {
@@ -125,2 +125,3 @@ communities: {'1': 0, '2': 0, '3': 1, '4': 1, '5': 1}
     * **weight** *?string* [`weight`]: name of the edges' weight attribute.
+  * **weighted** *?boolean* [`true`]: whether to compute weighted modularity or not.
 
@@ -127,0 +128,0 @@ ### Weighted size

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

59517

increased by26.25%

Lines of code

1392

increased by31.94%

Number of lines in readme file

365

increased by0.27%

Dependency changes

• + Addedgraphology-types@0.16.0(transitive)

• - Removedgraphology-types@0.15.5(transitive)

• Updatedgraphology-types@^0.16.0