graphology-indices - npm Package Compare versions

Comparing version 0.7.1 to 0.8.0

neighborhood/louvain.d.ts

@@ -30,7 +30,6 @@ import Graph from 'graphology-types';
   project(): NeighborhoodProjection;
+  isolate(index: number, degree: number): number;
   move(
     index: number,
     degree: number,
-    currentCommunityDegree: number,
-    targetCommunityDegree: number,
     targetCommunity: number
@@ -44,9 +43,2 @@ ): void;
   deltaWithOwnCommunity(index: number, degree: number, targetCommunityDegree: number, targetCommunity: number): number;
-  trueDelta(
-    index: number,
-    degree: number,
-    currentCommunityDegree: number,
-    targetCommunityDegree: number,
-    targetCommunity: number
-  ): number;
   fastDelta(index: number, degree: number, targetCommunityDegree: number, targetCommunity: number): number;
@@ -77,2 +69,3 @@ fastDeltaWithOwnCommunity(index: number, degree: number, targetCommunityDegree: number, targetCommunity: number): number;
   projectOut(): NeighborhoodProjection;
+  isolate(index: number, inDegree: number, outDegree: number): number;
   move(
@@ -82,6 +75,2 @@ index: number,
     outDegree: number,
-    currentCommunityInDegree: number,
-    currentCommunityOutDegree: number,
-    targetCommunityInDegree: number,
-    targetCommunityOutDegree: number,
     targetCommunity: number
@@ -88,0 +77,0 @@ ): void;

neighborhood/louvain.js

@@ -11,7 +11,4 @@ /**
  * Note that this index shares a lot with the classic Union-Find data
- * structure. As such, note that its structural integrity is only guaranteed
- * if the number of communities only decreases, never increases, which is the
- * case when applying Louvain's algorithm. It is possible to allow communities
- * to increase back, i.e. by isolating nodes again, but this would require
- * to store a stack of now unused community ids.
+ * structure. It also relies on a unused id stack to make sure we can
+ * increase again the number of communites when isolating nodes.
  *
@@ -59,8 +56,5 @@ * [Articles]
  * Q1 - Q2 but rather between Q when considered node is isolated in its own
- * community versus Q with this node in target community.
- *
- * Thus, and this is where implementation differ, if you allow negative moves,
- * you will need to consider additional possibilities:
- *  - Delta of keeping node in its current community
- *  - Delta of keeping node isolated in its own community
+ * community versus Q with this node in target community. This is in fact
+ * an optimization because the subtract part is constant in the formulae and
+ * does not affect delta comparisons.
  */
@@ -113,3 +107,3 @@ var typed = require('mnemonist/utils/typed-arrays');
   var NeighborhoodPointerArray = typed.getPointerArray(upperBound);
-  var NodesPointerArray = typed.getPointerArray(graph.order);
+  var NodesPointerArray = typed.getPointerArray(graph.order + 1);
 
@@ -120,2 +114,3 @@ // Properties
   this.E = graph.size * 2;
+  this.U = 0;
   this.resolution = resolution;
@@ -139,3 +134,4 @@ this.level = 0;
   // Community-level
-  this.internalWeights = new Float64Array(graph.order);
+  this.counts = new NodesPointerArray(graph.order);
+  this.unused = new NodesPointerArray(graph.order);
   this.totalWeights = new Float64Array(graph.order);
@@ -165,2 +161,3 @@
     self.belongings[i] = i;
+    self.counts[i] = 1;
     i++;
@@ -182,3 +179,2 @@ });
       self.totalWeights[source] += weight * 2;
-      self.internalWeights[source] += weight * 2;
       self.loops[source] = weight * 2;
@@ -209,7 +205,27 @@ }
 
+UndirectedLouvainIndex.prototype.isolate = function(i, degree) {
+  var currentCommunity = this.belongings[i];
+
+  // The node is already isolated
+  if (this.counts[currentCommunity] === 1)
+    return currentCommunity;
+
+  var newCommunity = this.unused[--this.U];
+
+  var loops = this.loops[i];
+
+  this.totalWeights[currentCommunity] -= degree + loops;
+  this.totalWeights[newCommunity] += degree + loops;
+
+  this.belongings[i] = newCommunity;
+
+  this.counts[currentCommunity]--;
+  this.counts[newCommunity]++;
+
+  return newCommunity;
+};
+
 UndirectedLouvainIndex.prototype.move = function(
   i,
   degree,
-  currentCommunityDegree,
-  targetCommunityDegree,
   targetCommunity
@@ -223,33 +239,23 @@ ) {
 
-  this.internalWeights[currentCommunity] -= currentCommunityDegree * 2 + loops;
-  this.internalWeights[targetCommunity] += targetCommunityDegree * 2 + loops;
+  this.belongings[i] = targetCommunity;
 
-  this.belongings[i] = targetCommunity;
+  var nowEmpty = this.counts[currentCommunity]-- === 1;
+  this.counts[targetCommunity]++;
+
+  if (nowEmpty)
+    this.unused[this.U++] = currentCommunity;
 };
 
 UndirectedLouvainIndex.prototype.expensiveMove = function(i, ci, dryRun) {
-  var o, l, n, cn, weight;
+  var o, l, weight;
 
-  var degree = 0,
-      currentCommunityDegree = 0,
-      targetCommunityDegree = 0;
+  var degree = 0;
 
-  var c = this.belongings[i];
-
   for (o = this.starts[i], l = this.starts[i + 1]; o < l; o++) {
-    n = this.neighborhood[o];
     weight = this.weights[o];
 
     degree += weight;
-
-    cn = this.belongings[n];
-
-    if (cn === ci)
-      targetCommunityDegree += weight;
-
-    if (c === cn)
-      currentCommunityDegree += weight;
   }
 
-  var args = [i, degree, currentCommunityDegree, targetCommunityDegree, ci];
+  var args = [i, degree, ci];
 
@@ -282,3 +288,3 @@ if (dryRun)
         totalWeights: this.totalWeights[ci],
-        internalWeights: this.internalWeights[ci]
+        internalWeights: 0
       };
@@ -313,3 +319,5 @@ C++;
 
-    adj = inducedGraph[ci].adj;
+    data = inducedGraph[ci];
+    adj = data.adj;
+    data.internalWeights += this.loops[i];
 
@@ -320,4 +328,6 @@ for (j = this.starts[i], m = this.starts[i + 1]; j < m; j++) {
 
-      if (ci === cj)
+      if (ci === cj) {
+        data.internalWeights += this.weights[j];
         continue;
+      }
 
@@ -343,4 +353,4 @@ if (!(cj in adj))
     this.totalWeights[ci] = data.totalWeights;
-    this.internalWeights[ci] = data.internalWeights;
     this.loops[ci] = data.internalWeights;
+    this.counts[ci] = 1;
 
@@ -362,2 +372,3 @@ this.starts[ci] = n;
   this.E = E;
+  this.U = 0;
   this.level++;
@@ -367,11 +378,28 @@ };
 UndirectedLouvainIndex.prototype.modularity = function() {
+  var ci, cj, i, j, m;
 
   var Q = 0;
   var M2 = this.M * 2;
+  var internalWeights = new Float64Array(this.C);
 
-  for (var i = 0; i < this.C; i++)
+  for (i = 0; i < this.C; i++) {
+    ci = this.belongings[i];
+    internalWeights[ci] += this.loops[i];
+
+    for (j = this.starts[i], m = this.starts[i + 1]; j < m; j++) {
+      cj = this.belongings[this.neighborhood[j]];
+
+      if (ci !== cj)
+        continue;
+
+      internalWeights[ci] += this.weights[j];
+    }
+  }
+
+  for (i = 0; i < this.C; i++) {
     Q += (
-      this.internalWeights[i] / M2 -
+      internalWeights[i] / M2 -
       Math.pow(this.totalWeights[i] / M2, 2) * this.resolution
     );
+  }
 
@@ -413,28 +441,4 @@ return Q;
 
-// NOTE: this function cannot work for self community move without changing
-// the underlying formula. We don't have to use it thusly anyway since
-// ∆Q is 0 in this case.
-// TODO: this formula does not work with resolution != 1
-UndirectedLouvainIndex.prototype.trueDelta = function(i, degree, currentCommunityDegree, targetCommunityDegree, targetCommunity) {
-  var M = this.M;
-
-  var currentCommunity = this.belongings[i],
-      loops = this.loops[i];
-
-  var currentCommunityTotalWeight = this.totalWeights[currentCommunity],
-      targetCommunityTotalWeight = this.totalWeights[targetCommunity];
-
-  return (
-    ((targetCommunityDegree - currentCommunityDegree) / M) +
-    (
-      (loops + degree) * currentCommunityTotalWeight -
-      Math.pow(degree, 2) -
-      Math.pow(loops, 2) -
-      (2 * loops * degree) -
-      (loops + degree) * targetCommunityTotalWeight
-    ) / (2 * Math.pow(M, 2))
-  );
-};
-
-// NOTE: this is Gephi's corrected faster delta computation
+// NOTE: this is just a faster but equivalent version of #.delta
+// It is just off by a constant factor and is just faster to compute
 UndirectedLouvainIndex.prototype.fastDelta = function(i, degree, targetCommunityDegree, targetCommunity) {
@@ -526,2 +530,3 @@ var M = this.M;
   proxy.E = this.E;
+  proxy.U = this.U;
   proxy.resolution = this.resolution;
@@ -533,3 +538,3 @@ proxy.level = this.level;
   var eTruncated = ['neighborhood', 'weights'];
-  var cTruncated = ['loops', 'belongings', 'internalWeights', 'totalWeights'];
+  var cTruncated = ['counts', 'loops', 'belongings', 'totalWeights'];
 
@@ -546,2 +551,4 @@ var self = this;
 
+  proxy.unused = this.unused.slice(0, this.U);
+
   if (this.keepDendrogram)
@@ -588,3 +595,3 @@ proxy.dendrogram = this.dendrogram;
   var NeighborhoodPointerArray = typed.getPointerArray(upperBound);
-  var NodesPointerArray = typed.getPointerArray(graph.order);
+  var NodesPointerArray = typed.getPointerArray(graph.order + 1);
 
@@ -595,2 +602,3 @@ // Properties
   this.E = graph.size * 2;
+  this.U = 0;
   this.resolution = resolution;
@@ -615,3 +623,4 @@ this.level = 0;
   // Community-level
-  this.internalWeights = new Float64Array(graph.order);
+  this.counts = new NodesPointerArray(graph.order);
+  this.unused = new NodesPointerArray(graph.order);
   this.totalInWeights = new Float64Array(graph.order);
@@ -645,2 +654,3 @@ this.totalOutWeights = new Float64Array(graph.order);
     self.belongings[i] = i;
+    self.counts[i] = 1;
     i++;
@@ -661,3 +671,2 @@ });
       self.E -= 2;
-      self.internalWeights[source] += weight;
       self.loops[source] += weight;
@@ -734,2 +743,27 @@ self.totalInWeights[source] += weight;
 
+DirectedLouvainIndex.prototype.isolate = function(i, inDegree, outDegree) {
+  var currentCommunity = this.belongings[i];
+
+  // The node is already isolated
+  if (this.counts[currentCommunity] === 1)
+    return currentCommunity;
+
+  var newCommunity = this.unused[--this.U];
+
+  var loops = this.loops[i];
+
+  this.totalInWeights[currentCommunity] -= inDegree + loops;
+  this.totalInWeights[newCommunity] += inDegree + loops;
+
+  this.totalOutWeights[currentCommunity] -= outDegree + loops;
+  this.totalOutWeights[newCommunity] += outDegree + loops;
+
+  this.belongings[i] = newCommunity;
+
+  this.counts[currentCommunity]--;
+  this.counts[newCommunity]++;
+
+  return newCommunity;
+};
+
 DirectedLouvainIndex.prototype.move = function(
@@ -739,6 +773,2 @@ i,
   outDegree,
-  currentCommunityInDegree,
-  currentCommunityOutDegree,
-  targetCommunityInDegree,
-  targetCommunityOutDegree,
   targetCommunity
@@ -755,46 +785,27 @@ ) {
 
-  this.internalWeights[currentCommunity] -= currentCommunityInDegree + currentCommunityOutDegree + loops;
-  this.internalWeights[targetCommunity] += targetCommunityInDegree + targetCommunityOutDegree + loops;
+  this.belongings[i] = targetCommunity;
 
-  this.belongings[i] = targetCommunity;
+  var nowEmpty = this.counts[currentCommunity]-- === 1;
+  this.counts[targetCommunity]++;
+
+  if (nowEmpty)
+    this.unused[this.U++] = currentCommunity;
 };
 
 DirectedLouvainIndex.prototype.expensiveMove = function(i, ci, dryRun) {
-  var o, l, n, out, cn, weight;
+  var o, l, out, weight;
 
   var inDegree = 0,
-      outDegree = 0,
-      currentCommunityInDegree = 0,
-      currentCommunityOutDegree = 0,
-      targetCommunityInDegree = 0,
-      targetCommunityOutDegree = 0;
+      outDegree = 0;
 
-  var c = this.belongings[i],
-      s = this.offsets[i];
+  var s = this.offsets[i];
 
   for (o = this.starts[i], l = this.starts[i + 1]; o < l; o++) {
     out = o < s;
-    n = this.neighborhood[o];
     weight = this.weights[o];
 
-    cn = this.belongings[n];
-
-    if (out) {
+    if (out)
       outDegree += weight;
-
-      if (cn === ci)
-        targetCommunityOutDegree += weight;
-
-      if (c === cn)
-        currentCommunityOutDegree += weight;
-    }
-    else {
+    else
       inDegree += weight;
-
-      if (cn === ci)
-        targetCommunityInDegree += weight;
-
-      if (c === cn)
-        currentCommunityInDegree += weight;
-    }
   }
@@ -806,6 +817,2 @@
     outDegree,
-    currentCommunityInDegree,
-    currentCommunityOutDegree,
-    targetCommunityInDegree,
-    targetCommunityOutDegree,
     ci
@@ -842,3 +849,3 @@ ];
         totalOutWeights: this.totalOutWeights[ci],
-        internalWeights: this.internalWeights[ci]
+        internalWeights: 0
       };
@@ -877,2 +884,3 @@ C++;
     outAdj = data.outAdj;
+    data.internalWeights += this.loops[i];
 
@@ -886,4 +894,8 @@ for (j = this.starts[i], m = this.starts[i + 1]; j < m; j++) {
 
-      if (ci === cj)
+      if (ci === cj) {
+        if (out)
+          data.internalWeights += this.weights[j];
+
         continue;
+      }
 
@@ -911,4 +923,4 @@ if (!(cj in adj))
     this.totalOutWeights[ci] = data.totalOutWeights;
-    this.internalWeights[ci] = data.internalWeights;
     this.loops[ci] = data.internalWeights;
+    this.counts[ci] = 1;
 
@@ -940,2 +952,3 @@ this.starts[ci] = n;
   this.E = E;
+  this.U = 0;
   this.level++;
@@ -945,9 +958,25 @@ };
 DirectedLouvainIndex.prototype.modularity = function() {
+  var ci, cj, i, j, m;
 
   var Q = 0;
   var M = this.M;
+  var internalWeights = new Float64Array(this.C);
 
-  for (var i = 0; i < this.C; i++)
+  for (i = 0; i < this.C; i++) {
+    ci = this.belongings[i];
+    internalWeights[ci] += this.loops[i];
+
+    for (j = this.starts[i], m = this.offsets[i]; j < m; j++) {
+      cj = this.belongings[this.neighborhood[j]];
+
+      if (ci !== cj)
+        continue;
+
+      internalWeights[ci] += this.weights[j];
+    }
+  }
+
+  for (i = 0; i < this.C; i++)
     Q += (
-      (this.internalWeights[i] / M) -
+      (internalWeights[i] / M) -
       (this.totalInWeights[i] * this.totalOutWeights[i] / Math.pow(M, 2)) *
@@ -1033,2 +1062,3 @@ this.resolution
   proxy.E = this.E;
+  proxy.U = this.U;
   proxy.resolution = this.resolution;
@@ -1040,3 +1070,3 @@ proxy.level = this.level;
   var eTruncated = ['neighborhood', 'weights'];
-  var cTruncated = ['offsets', 'loops', 'belongings', 'internalWeights', 'totalInWeights', 'totalOutWeights'];
+  var cTruncated = ['counts', 'offsets', 'loops', 'belongings', 'totalInWeights', 'totalOutWeights'];
 
@@ -1053,2 +1083,4 @@ var self = this;
 
+  proxy.unused = this.unused.slice(0, this.U);
+
   if (this.keepDendrogram)
@@ -1055,0 +1087,0 @@ proxy.dendrogram = this.dendrogram;

package.json

 {
   "name": "graphology-indices",
-  "version": "0.7.1",
+  "version": "0.8.0",
   "description": "Miscellaneous indices for graphology.",
@@ -5,0 +5,0 @@ "main": "index.js",

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

Lines of code

1028

increased by0.39%

Worsened metrics

Total package byte prevSize

37739

decreased by-0.73%

No dependency changes