graphology-communities-louvain - npm Package Compare versions

Comparing version 1.0.2 to 1.1.0

index.d.ts

@@ -15,2 +15,3 @@ import Graph from 'graphology';
   randomWalk: boolean,
+  resolution: number,
   rng: RNGFunction,
@@ -29,3 +30,4 @@ weighted: boolean
   moves: Array<Array<number>> | Array<number>,
-  nodesVisited: number
+  nodesVisited: number,
+  resolution: number
 };
@@ -32,0 +34,0 @@

index.js

@@ -13,2 +13,7 @@ /**
  *
+ * Newman, M. E. J. « Community detection in networks: Modularity optimization
+ * and maximum likelihood are equivalent ». Physical Review E, vol. 94, no 5,
+ * novembre 2016, p. 052315. arXiv.org, doi:10.1103/PhysRevE.94.052315.
+ * https://arxiv.org/pdf/1606.02319.pdf
+ *
  * Blondel, Vincent D., et al. « Fast unfolding of communities in large
@@ -51,5 +56,6 @@ * networks ». Journal of Statistical Mechanics: Theory and Experiment,
   },
-  deltaComputation: 'original',
+  deltaComputation: 'fast',
   fastLocalMoves: true,
   randomWalk: true,
+  resolution: 1,
   rng: Math.random,
@@ -171,2 +177,4 @@ weighted: false
 
+DIRECTED_DELTAS.fast = DIRECTED_DELTAS.original;
+
 function undirectedLouvain(detailed, graph, options) {
@@ -178,2 +186,3 @@ var index = new UndirectedLouvainIndex(graph, {
     keepDendrogram: detailed,
+    resolution: options.resolution,
     weighted: options.weighted
@@ -464,2 +473,3 @@ });
     keepDendrogram: detailed,
+    resolution: options.resolution,
     weighted: options.weighted
@@ -786,10 +796,15 @@ });
  *
- * @param  {boolean} assign        - Assign communities to nodes attributes?
- * @param  {boolean} detailed      - Whether to return detailed information.
- * @param  {Graph}   graph         - Target graph.
- * @param  {object}  options       - Options:
- * @param  {object}    attributes  - Attribute names:
- * @param  {string}      community - Community node attribute name.
- * @param  {string}      weight    - Weight edge attribute name.
- * @param  {boolean}   weighted    - Whether to compute the weighted version.
+ * @param  {boolean} assign             - Assign communities to nodes attributes?
+ * @param  {boolean} detailed           - Whether to return detailed information.
+ * @param  {Graph}   graph              - Target graph.
+ * @param  {object}  options            - Options:
+ * @param  {object}    attributes         - Attribute names:
+ * @param  {string}      community          - Community node attribute name.
+ * @param  {string}      weight             - Weight edge attribute name.
+ * @param  {string}    deltaComputation   - Method to use to compute delta computations.
+ * @param  {boolean}   fastLocalMoves     - Whether to use the fast local move optimization.
+ * @param  {boolean}   randomWalk         - Whether to traverse the graph in random order.
+ * @param  {number}    resolution         - Resolution parameter.
+ * @param  {function}  rng                - RNG function to use.
+ * @param  {boolean}   weighted           - Whether to compute the weighted version.
  * @return {object}
@@ -839,3 +854,4 @@ */
     moves: results.moves,
-    nodesVisited: results.nodesVisited
+    nodesVisited: results.nodesVisited,
+    resolution: options.resolution
   };
@@ -842,0 +858,0 @@

package.json

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

README.md

@@ -11,2 +11,4 @@ [![Build Status](https://travis-ci.org/graphology/graphology-communities-louvain.svg)](https://travis-ci.org/graphology/graphology-communities-louvain)
 
+> Newman, M. E. J. « Community detection in networks: Modularity optimization and maximum likelihood are equivalent ». Physical Review E, vol. 94, no 5, novembre 2016, p. 052315. arXiv.org, doi:10.1103/PhysRevE.94.052315. https://arxiv.org/pdf/1606.02319.pdf
+
 > 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
@@ -60,5 +62,6 @@
     * **community** *?string* [`community`]: name of the community attribute.
-  * **deltaComputation** *?string* [`original`]: what computation method to use: `original` for Louvain's paper method, `fast` for Gephi's optimization or `true` for applying true modularity delta formula. `fast` and `true` only work for the undirected version right now.
+  * **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.
   * **randomWalk** *?boolean* [`true`]: whether to traverse the graph randomly.
+  * **resolution** *?number* [`1`]: resolution parameter. An increased resolution should produce more communities.
   * **rng** *?function* [`Math.random`]: RNG function to use for `randomWalk`. Useful if you need to seed your rng using, for instance, [seedrandom](https://www.npmjs.com/package/seedrandom).
@@ -76,1 +79,62 @@ * **weighted** *?boolean* [`false`]: whether to take edge weights into account.
 * **nodesVisited** [`number`]: number of times nodes were visited.
+
+## Benchmark
+
+To run the benchmark:
+
+```
+npm install --no-save ngraph.louvain.native
+node benchmark/comparison.js
+```
+
+```
+Clustered Undirected graph with 1000 nodes and 9724 edges.
+
+graphology undirected1000: 56.898ms
+Communities 8
+Modularity 0.43022131098025784
+
+jlouvain undirected1000: 2592.024ms
+Communities 8
+Modularity 0.4302331134880074
+
+ngraph.louvain undirected1000: 78.188ms
+Communities 8
+
+ngraph.louvain.native undirected1000: 45.867ms
+Communities 7
+
+---
+
+EuroSIS Directed graph with 1285 nodes and 7524 edges.
+
+graphology euroSis: 43.606ms
+Communities 19
+Modularity 0.7384815869034789
+
+jlouvain euroSis: 1716.894ms
+Communities 23
+Modularity 0.7376116434498033
+
+ngraph euroSis: 45.982ms
+Communities 16
+
+ngraph.native euroSis: 21.907ms
+Communities 16
+
+---
+
+Big Undirected graph with 50000 nodes and 994631 edges.
+
+graphology bigGraph: 1114.216ms
+Communities 43
+Modularity 0.48304555149107353
+
+jLouvain is too slow...
+
+ngraph bigGraph: 8799.085ms
+Communities 42
+
+ngraph.native bigGraph: 8084.948ms
+Communities 1
+```

No alert changes

Improved metrics

Total package byte prevSize

31316

increased by8.18%

Lines of code

747

increased by2.33%

Number of lines in readme file

138

increased by86.49%

Dependency changes

• + Addedgraphology-indices@0.7.1(transitive)

• - Removedgraphology-indices@0.6.6(transitive)

• Updatedgraphology-indices@^0.7.1