graphology-communities-louvain - npm Package Compare versions

Comparing version 1.1.0 to 1.2.0

index.d.ts

@@ -12,3 +12,2 @@ import Graph from 'graphology';
   },
-  deltaComputation: 'original' | 'true' | 'fast',
   fastLocalMoves: boolean,
@@ -15,0 +14,0 @@ randomWalk: boolean,

index.js

@@ -55,3 +55,2 @@ /**
   },
-  deltaComputation: 'fast',
   fastLocalMoves: true,
@@ -75,105 +74,2 @@ randomWalk: true,
 
-var UNDIRECTED_DELTAS = {
-  original: function(
-    index,
-    i,
-    degree,
-    currentCommunity,
-    targetCommunityDegree,
-    targetCommunity
-  ) {
-    if (targetCommunity === currentCommunity) {
-      return index.deltaWithOwnCommunity(
-        i,
-        degree,
-        targetCommunityDegree,
-        targetCommunity
-      );
-    }
-
-    return index.delta(
-      i,
-      degree,
-      targetCommunityDegree,
-      targetCommunity
-    );
-  },
-  fast: function(
-    index,
-    i,
-    degree,
-    currentCommunity,
-    targetCommunityDegree,
-    targetCommunity
-  ) {
-    if (targetCommunity === currentCommunity) {
-      return index.fastDeltaWithOwnCommunity(
-        i,
-        degree,
-        targetCommunityDegree,
-        targetCommunity
-      );
-    }
-
-    return index.fastDelta(
-      i,
-      degree,
-      targetCommunityDegree,
-      targetCommunity
-    );
-  },
-  true: function(
-    index,
-    i,
-    degree,
-    currentCommunity,
-    targetCommunityDegree,
-    targetCommunity,
-    communities
-  ) {
-    if (targetCommunity === currentCommunity)
-      return 0;
-
-    return index.trueDelta(
-      i,
-      degree,
-      communities.get(currentCommunity) || 0,
-      targetCommunityDegree,
-      targetCommunity
-    );
-  }
-};
-
-var DIRECTED_DELTAS = {
-  original: function(
-    index,
-    i,
-    inDegree,
-    outDegree,
-    currentCommunity,
-    targetCommunityDegree,
-    targetCommunity
-  ) {
-    if (targetCommunity === currentCommunity) {
-      return index.deltaWithOwnCommunity(
-        i,
-        inDegree,
-        outDegree,
-        targetCommunityDegree,
-        targetCommunity
-      );
-    }
-
-    return index.delta(
-      i,
-      inDegree,
-      outDegree,
-      targetCommunityDegree,
-      targetCommunity
-    );
-  }
-};
-
-DIRECTED_DELTAS.fast = DIRECTED_DELTAS.original;
-
 function undirectedLouvain(detailed, graph, options) {
@@ -189,4 +85,2 @@ var index = new UndirectedLouvainIndex(graph, {
 
-  var deltaComputation = UNDIRECTED_DELTAS[options.deltaComputation];
-
   var randomIndex = createRandomIndex(options.rng);
@@ -199,3 +93,3 @@
   // Communities
-  var currentCommunity, targetCommunity;
+  var currentCommunity, targetCommunity, singletonCommunity;
   var communities = new SparseMap(Float64Array, index.C);
@@ -276,4 +170,14 @@
 
+        singletonCommunity = index.isolate(i, degree);
+
+        if (singletonCommunity !== currentCommunity)
+          communities.set(singletonCommunity, 0);
+
         // Finding best community to move to
-        bestDelta = 0;
+        bestDelta = index.fastDelta(
+          i,
+          degree,
+          communities.get(currentCommunity) || 0,
+          currentCommunity
+        );
         bestCommunity = currentCommunity;
@@ -283,2 +187,6 @@
           targetCommunity = communities.dense[ci];
+
+          if (targetCommunity === currentCommunity)
+            continue;
+
           targetCommunityDegree = communities.vals[ci];
@@ -288,10 +196,7 @@
 
-          delta = deltaComputation(
-            index,
+          delta = index.fastDelta(
             i,
             degree,
-            currentCommunity,
             targetCommunityDegree,
-            targetCommunity,
-            communities
+            targetCommunity
           );
@@ -320,18 +225,16 @@
 
-        // Should we move the node into a different community?
-        if (
-          bestDelta > 0 &&
-          bestCommunity !== currentCommunity
-        ) {
+        // Should we move the node back into its community or into a
+        // different community?
+        if (bestCommunity === currentCommunity || bestDelta <= 0) {
+          if (currentCommunity !== singletonCommunity)
+            index.move(i, degree, currentCommunity);
+        }
+
+        else if (bestCommunity !== singletonCommunity)
+          index.move(i, degree, bestCommunity);
+
+        if (bestDelta > 0 && bestCommunity !== currentCommunity) {
           moveWasMade = true;
           currentMoves++;
 
-          index.move(
-            i,
-            degree,
-            communities.get(currentCommunity) || 0,
-            communities.get(bestCommunity) || 0,
-            bestCommunity
-          );
-
           // Adding neighbors from other communities to the queue
@@ -391,4 +294,14 @@ start = index.starts[i];
 
+          singletonCommunity = index.isolate(i, degree);
+
+          if (singletonCommunity !== currentCommunity)
+            communities.set(singletonCommunity, 0);
+
           // Finding best community to move to
-          bestDelta = 0;
+          bestDelta = index.fastDelta(
+            i,
+            degree,
+            communities.get(currentCommunity) || 0,
+            currentCommunity
+          );
           bestCommunity = currentCommunity;
@@ -398,2 +311,6 @@
             targetCommunity = communities.dense[ci];
+
+            if (targetCommunity === currentCommunity)
+              continue;
+
             targetCommunityDegree = communities.vals[ci];
@@ -403,10 +320,7 @@
 
-            delta = deltaComputation(
-              index,
+            delta = index.fastDelta(
               i,
               degree,
-              currentCommunity,
               targetCommunityDegree,
-              targetCommunity,
-              communities
+              targetCommunity
             );
@@ -435,17 +349,15 @@
 
-          // Should we move the node into a different community?
-          if (
-            bestDelta > 0 &&
-            bestCommunity !== currentCommunity
-          ) {
+          // Should we move the node back into its community or into a
+          // different community?
+          if (bestCommunity === currentCommunity || bestDelta <= 0) {
+            if (currentCommunity !== singletonCommunity)
+              index.move(i, degree, currentCommunity);
+          }
+
+          else if (bestCommunity !== singletonCommunity)
+            index.move(i, degree, bestCommunity);
+
+          if (bestDelta > 0 && bestCommunity !== currentCommunity) {
             localMoveWasMade = true;
             currentMoves++;
-
-            index.move(
-              i,
-              degree,
-              communities.get(currentCommunity) || 0,
-              communities.get(bestCommunity) || 0,
-              bestCommunity
-            );
           }
@@ -485,4 +397,2 @@ }
 
-  var deltaComputation = DIRECTED_DELTAS[options.deltaComputation];
-
   var randomIndex = createRandomIndex(options.rng);
@@ -495,6 +405,4 @@
   // Communities
-  var currentCommunity, targetCommunity;
+  var currentCommunity, targetCommunity, singletonCommunity;
   var communities = new SparseMap(Float64Array, index.C);
-  var communitiesIn = new SparseMap(Float64Array, index.C);
-  var communitiesOut = new SparseMap(Float64Array, index.C);
 
@@ -560,4 +468,2 @@ // Traversal
         communities.clear();
-        communitiesIn.clear();
-        communitiesOut.clear();
 
@@ -579,10 +485,6 @@ currentCommunity = index.belongings[i];
           // Incrementing metrics
-          if (out) {
+          if (out)
             outDegree += weight;
-            addWeightToCommunity(communitiesOut, targetCommunity, weight);
-          }
-          else {
+          else
             inDegree += weight;
-            addWeightToCommunity(communitiesIn, targetCommunity, weight);
-          }
 
@@ -592,4 +494,15 @@ addWeightToCommunity(communities, targetCommunity, weight);
 
+        singletonCommunity = index.isolate(i, inDegree, outDegree);
+
+        if (singletonCommunity !== currentCommunity)
+          communities.set(singletonCommunity, 0);
+
         // Finding best community to move to
-        bestDelta = 0;
+        bestDelta = index.delta(
+          i,
+          inDegree,
+          outDegree,
+          communities.get(currentCommunity) || 0,
+          currentCommunity
+        );
         bestCommunity = currentCommunity;
@@ -599,2 +512,6 @@
           targetCommunity = communities.dense[ci];
+
+          if (targetCommunity === currentCommunity)
+            continue;
+
           targetCommunityDegree = communities.vals[ci];
@@ -604,11 +521,8 @@
 
-          delta = deltaComputation(
-            index,
+          delta = index.delta(
             i,
             inDegree,
             outDegree,
-            currentCommunity,
             targetCommunityDegree,
-            targetCommunity,
-            communities
+            targetCommunity
           );
@@ -637,21 +551,16 @@
 
-        // Should we move the node into a different community?
-        if (
-          bestDelta > 0 &&
-          bestCommunity !== currentCommunity
-        ) {
+        // Should we move the node back into its community or into a
+        // different community?
+        if (bestCommunity === currentCommunity || bestDelta <= 0) {
+          if (currentCommunity !== singletonCommunity)
+            index.move(i, inDegree, outDegree, currentCommunity);
+        }
+
+        else if (bestCommunity !== singletonCommunity)
+          index.move(i, inDegree, outDegree, bestCommunity);
+
+        if (bestDelta > 0 && bestCommunity !== currentCommunity) {
           moveWasMade = true;
           currentMoves++;
 
-          index.move(
-            i,
-            inDegree,
-            outDegree,
-            communitiesIn.get(currentCommunity) || 0,
-            communitiesOut.get(currentCommunity) || 0,
-            communitiesIn.get(bestCommunity) || 0,
-            communitiesOut.get(bestCommunity) || 0,
-            bestCommunity
-          );
-
           // Adding neighbors from other communities to the queue
@@ -694,4 +603,2 @@ start = index.starts[i];
           communities.clear();
-          communitiesIn.clear();
-          communitiesOut.clear();
 
@@ -713,10 +620,6 @@ currentCommunity = index.belongings[i];
             // Incrementing metrics
-            if (out) {
+            if (out)
               outDegree += weight;
-              addWeightToCommunity(communitiesOut, targetCommunity, weight);
-            }
-            else {
+            else
               inDegree += weight;
-              addWeightToCommunity(communitiesIn, targetCommunity, weight);
-            }
 
@@ -726,4 +629,15 @@ addWeightToCommunity(communities, targetCommunity, weight);
 
+          singletonCommunity = index.isolate(i, inDegree, outDegree);
+
+          if (singletonCommunity !== currentCommunity)
+            communities.set(singletonCommunity, 0);
+
           // Finding best community to move to
-          bestDelta = 0;
+          bestDelta = index.delta(
+            i,
+            inDegree,
+            outDegree,
+            communities.get(currentCommunity) || 0,
+            currentCommunity
+          );
           bestCommunity = currentCommunity;
@@ -733,2 +647,6 @@
             targetCommunity = communities.dense[ci];
+
+            if (targetCommunity === currentCommunity)
+              continue;
+
             targetCommunityDegree = communities.vals[ci];
@@ -738,11 +656,8 @@
 
-            delta = deltaComputation(
-              index,
+            delta = index.delta(
               i,
               inDegree,
               outDegree,
-              currentCommunity,
               targetCommunityDegree,
-              targetCommunity,
-              communities
+              targetCommunity
             );
@@ -771,20 +686,15 @@
 
-          // Should we move the node into a different community?
-          if (
-            bestDelta > 0 &&
-            bestCommunity !== currentCommunity
-          ) {
+          // Should we move the node back into its community or into a
+          // different community?
+          if (bestCommunity === currentCommunity || bestDelta <= 0) {
+            if (currentCommunity !== singletonCommunity)
+              index.move(i, inDegree, outDegree, currentCommunity);
+          }
+
+          else if (bestCommunity !== singletonCommunity)
+            index.move(i, inDegree, outDegree, bestCommunity);
+
+          if (bestDelta > 0 && bestCommunity !== currentCommunity) {
             localMoveWasMade = true;
             currentMoves++;
-
-            index.move(
-              i,
-              inDegree,
-              outDegree,
-              communitiesIn.get(currentCommunity) || 0,
-              communitiesOut.get(currentCommunity) || 0,
-              communitiesIn.get(bestCommunity) || 0,
-              communitiesOut.get(bestCommunity) || 0,
-              bestCommunity
-            );
           }
@@ -839,5 +749,2 @@ }
 
-  if (graph.size === 0)
-    throw new Error('graphology-communities-louvain: cannot run the algorithm on an empty graph.');
-
   var type = inferType(graph);
@@ -851,2 +758,36 @@
 
+  // Empty graph case
+  var c = 0;
+
+  if (graph.size === 0) {
+    if (assign) {
+      graph.forEachNode(function(node) {
+        graph.setNodeAttribute(node, options.attributes.communities, c++);
+      });
+
+      return;
+    }
+
+    var communities = {};
+
+    graph.forEachNode(function(node) {
+      communities[node] = c++;
+    });
+
+    if (!detailed)
+      return communities;
+
+    return {
+      communities: communities,
+      count: graph.order,
+      deltaComputations: 0,
+      dendrogram: null,
+      level: 0,
+      modularity: NaN,
+      moves: null,
+      nodesVisited: 0,
+      resolution: options.resolution
+    };
+  }
+
   var fn = type === 'undirected' ? undirectedLouvain : directedLouvain;
@@ -853,0 +794,0 @@

package.json

 {
   "name": "graphology-communities-louvain",
-  "version": "1.1.0",
+  "version": "1.2.0",
   "description": "Louvain community detection for graphology.",
@@ -59,3 +59,3 @@ "main": "index.js",
   "dependencies": {
-    "graphology-indices": "^0.7.1",
+    "graphology-indices": "^0.8.0",
     "graphology-types": "^0.16.0",
@@ -62,0 +62,0 @@ "graphology-utils": "^1.7.0",

README.md

@@ -61,3 +61,2 @@ [![Build Status](https://travis-ci.org/graphology/graphology-communities-louvain.svg)](https://travis-ci.org/graphology/graphology-communities-louvain)
     * **community** *?string* [`community`]: name of the community attribute.
-  * **deltaComputation** *?string* [`fast|original`]: what computation method to use: `original` for Louvain's paper method, `fast` for a simplified but equivalent version or `true` for applying true modularity delta formula. `fast` and `true` only work for the undirected version right now.
   * **fastLocalMoves** *?boolean* [`true`]: whether to use a well-known optimization relying on a queue set to traverse the graph more efficiently.
@@ -91,14 +90,14 @@ * **randomWalk** *?boolean* [`true`]: whether to traverse the graph randomly.
 
-graphology undirected1000: 56.898ms
+graphology undirected1000: 52.732ms
 Communities 8
-Modularity 0.43022131098025784
+Modularity 0.42944314393593924
 
-jlouvain undirected1000: 2592.024ms
+jlouvain undirected1000: 2368.053ms
 Communities 8
 Modularity 0.4302331134880074
 
-ngraph.louvain undirected1000: 78.188ms
+ngraph.louvain undirected1000: 71.108ms
 Communities 8
 
-ngraph.louvain.native undirected1000: 45.867ms
+ngraph.louvain.native undirected1000: 39.185ms
 Communities 7
@@ -110,14 +109,14 @@
 
-graphology euroSis: 43.606ms
+graphology euroSis: 30.809ms
 Communities 19
-Modularity 0.7384815869034789
+Modularity 0.7375260763995757
 
-jlouvain euroSis: 1716.894ms
+jlouvain euroSis: 1310.008ms
 Communities 23
 Modularity 0.7376116434498033
 
-ngraph euroSis: 45.982ms
+ngraph euroSis: 38.262ms
 Communities 16
 
-ngraph.native euroSis: 21.907ms
+ngraph.native euroSis: 20.018ms
 Communities 16
@@ -127,15 +126,15 @@
 
-Big Undirected graph with 50000 nodes and 994631 edges.
+Big Undirected graph with 50000 nodes and 994713 edges.
 
-graphology bigGraph: 1114.216ms
+graphology bigGraph: 937.942ms
 Communities 43
-Modularity 0.48304555149107353
+Modularity 0.481431448861252
 
 jLouvain is too slow...
 
-ngraph bigGraph: 8799.085ms
-Communities 42
+ngraph bigGraph: 7783.050ms
+Communities 44
 
-ngraph.native bigGraph: 8084.948ms
+ngraph.native bigGraph: 8415.692ms
 Communities 1
 ```

No alert changes

Worsened metrics

Total package byte prevSize

30361

decreased by-3.05%

Lines of code

670

decreased by-10.31%

Number of lines in readme file

137

decreased by-0.72%

Dependency changes

• + Addedgraphology-indices@0.8.0(transitive)

• - Removedgraphology-indices@0.7.1(transitive)

• Updatedgraphology-indices@^0.8.0