graphology-metrics - npm Package Compare versions

Comparing version 1.16.1 to 1.17.0

centrality/index.d.ts

 export {default as betweenness} from './betweenness';
 export {default as degree} from './degree';
+export {default as eigenvector} from './eigenvector';
 export {default as hits} from './hits';
 export {default as pagerank} from './pagerank';

centrality/index.js

@@ -9,3 +9,4 @@ /**
 exports.degree = require('./degree.js');
+exports.eigenvector = require('./eigenvector.js');
 exports.hits = require('./hits.js');
 exports.pagerank = require('./pagerank.js');

centrality/pagerank.js

@@ -13,2 +13,4 @@ /**
 var resolveDefaults = require('graphology-utils/defaults');
+var WeightedOutboundNeighborhoodIndex =
+  require('graphology-indices/neighborhood/outbound').WeightedOutboundNeighborhoodIndex;
 
@@ -47,3 +49,3 @@ /**
     throw new Error(
-      'graphology-pagerank: the given graph is not a valid graphology instance.'
+      'graphology-metrics/centrality/pagerank: the given graph is not a valid graphology instance.'
     );
@@ -53,3 +55,3 @@
     throw new Error(
-      'graphology-pagerank: the pagerank algorithm does not work with MultiGraphs.'
+      'graphology-metrics/centrality/pagerank: the pagerank algorithm does not work with MultiGraphs.'
     );
@@ -59,78 +61,45 @@
 
-  var pagerankAttribute = options.attributes.pagerank,
-    weightAttribute = options.attributes.weight,
-    alpha = options.alpha,
-    maxIterations = options.maxIterations,
-    tolerance = options.tolerance,
-    weighted = options.weighted;
+  var alpha = options.alpha;
+  var maxIterations = options.maxIterations;
+  var tolerance = options.tolerance;
+  var weighted = options.weighted;
 
-  var N = graph.order,
-    p = 1 / N,
-    x = {};
+  var pagerankAttribute = options.attributes.pagerank;
+  var weightAttribute = weighted ? options.attributes.weight : null;
 
-  var danglingNodes = [];
+  var N = graph.order;
+  var p = 1 / N;
 
-  var nodes = graph.nodes(),
-    edges,
-    weights = {},
-    degrees = {},
-    weight,
-    iteration = 0,
-    dangleSum,
-    xLast,
-    neighbor,
-    error,
-    d,
-    k,
-    n,
-    e,
-    i,
-    j,
-    l,
-    m;
+  var index = new WeightedOutboundNeighborhoodIndex(graph, weightAttribute);
 
-  // Initialization
-  for (i = 0; i < N; i++) {
-    n = nodes[i];
-    x[n] = p;
+  var i, j, l, d;
 
-    if (weighted) {
-      // Here, we need to factor in edges' weight
-      d = 0;
+  var x = new Float64Array(graph.order);
 
-      edges = graph.undirectedEdges().concat(graph.outEdges(n));
+  // Normalizing edge weights & indexing dangling nodes
+  var normalizedEdgeWeights = new Float64Array(index.weights.length);
+  var danglingNodes = [];
 
-      for (j = 0, m = edges.length; j < m; j++) {
-        e = edges[j];
-        d += graph.getEdgeAttribute(e, weightAttribute) || 1;
-      }
-    } else {
-      d = graph.undirectedDegree(n) + graph.outDegree(n);
-    }
+  for (i = 0; i < N; i++) {
+    x[i] = p;
+    l = index.starts[i + 1];
+    d = index.outDegrees[i];
 
-    degrees[n] = d;
+    if (d === 0) danglingNodes.push(i);
 
-    if (d === 0) danglingNodes.push(n);
+    for (j = index.starts[i]; j < l; j++) {
+      normalizedEdgeWeights[j] = index.weights[j] / d;
+    }
   }
 
-  // Precompute normalized edge weights
-  edges = graph.edges();
-  for (i = 0, l = graph.size; i < l; i++) {
-    e = edges[i];
-    n = graph.source(e);
+  // Power iterations
+  var iteration = 0;
+  var error = 0;
+  var dangleSum, neighbor, xLast;
+  var converged = false;
 
-    d = degrees[n];
-
-    weight = weighted ? graph.getEdgeAttribute(e, weightAttribute) || 1 : 1;
-
-    weights[e] = weight / d;
-  }
-
-  // Performing the power iterations
   while (iteration < maxIterations) {
     xLast = x;
-    x = {};
+    x = new Float64Array(graph.order); // TODO: it should be possible to swap two arrays to avoid allocations (bench)
 
-    for (k in xLast) x[k] = 0;
-
     dangleSum = 0;
@@ -144,12 +113,10 @@
     for (i = 0; i < N; i++) {
-      n = nodes[i];
-      edges = graph.undirectedEdges(n).concat(graph.outEdges(n));
+      l = index.starts[i + 1];
 
-      for (j = 0, m = edges.length; j < m; j++) {
-        e = edges[j];
-        neighbor = graph.opposite(n, e);
-        x[neighbor] += alpha * xLast[n] * weights[e];
+      for (j = index.starts[i]; j < l; j++) {
+        neighbor = index.neighborhood[j];
+        x[neighbor] += alpha * xLast[i] * normalizedEdgeWeights[j];
       }
 
-      x[n] += dangleSum * p + (1 - alpha) * p;
+      x[i] += dangleSum * p + (1 - alpha) * p;
     }
@@ -160,10 +127,9 @@
 
-    for (n in x) error += Math.abs(x[n] - xLast[n]);
+    for (i = 0; i < N; i++) {
+      error += Math.abs(x[i] - xLast[i]);
+    }
 
     if (error < N * tolerance) {
-      if (assign) {
-        for (n in x) graph.setNodeAttribute(n, pagerankAttribute, x[n]);
-      }
-
-      return x;
+      converged = true;
+      break;
     }
@@ -174,3 +140,11 @@
 
-  throw Error('graphology-pagerank: failed to converge.');
+  if (!converged)
+    throw Error('graphology-metrics/centrality/pagerank: failed to converge.');
+
+  if (assign) {
+    index.assign(pagerankAttribute, x);
+    return;
+  }
+
+  return index.collect(x);
 }
@@ -177,0 +151,0 @@

modularity.js

@@ -115,3 +115,3 @@ /**
  * M. E. J. Newman, « Modularity and community structure in networks »,
- * Proc. Natl. Acad. Sci. USA, vol. 103, no 23,‎ 2006, p. 8577–8582
+ * Proc. Natl. Acad. Sci. USA, vol. 103, no 23, 2006, p. 8577–8582
  * https://dx.doi.org/10.1073%2Fpnas.0601602103
@@ -118,0 +118,0 @@ *

package.json

 {
   "name": "graphology-metrics",
-  "version": "1.16.1",
+  "version": "1.17.0",
   "description": "Miscellaneous graph metrics for graphology.",
@@ -55,3 +55,3 @@ "main": "index.js",
   "dependencies": {
-    "graphology-shortest-path": "^1.5.0",
+    "graphology-shortest-path": "^1.5.1",
     "graphology-utils": "^2.3.0",
@@ -58,0 +58,0 @@ "mnemonist": "^0.38.3"

README.md

@@ -26,2 +26,3 @@ # Graphology metrics
   - [Degree centrality](#degree-centrality)
+  - [Eigenvector centrality](#eigenvector-centrality)
   - [HITS](#hits)
@@ -249,2 +250,31 @@ - [Pagerank](#pagerank)
 
+### Eigenvector centrality
+
+Computes the eigenvector centrality of a graph's nodes.
+
+```js
+import eigenvectorCentrality from 'graphology-metrics/centrality/eigenvector';
+
+// To compute the eigenvector centrality and return the score per node:
+const scores = eigenvectorCentrality(graph);
+
+// To directly map the result to nodes' attributes:
+eigenvectorCentrality.assign(graph);
+
+// Note that you can also pass options to customize the algorithm:
+const p = eigenvectorCentrality(graph, {tolerance: 1e-3, weighted: false});
+```
+
+_Arguments_
+
+- **graph** _Graph_: target graph.
+- **options** _?object_: options:
+  - **attributes** _?object_: attributes' names:
+    - **centrality** _?string_ [`eigenvectorCentrality`]: name of the node attribute that will be assigned the eigenvector centrality.
+    - **weight** _?string_ [`weight`]: name of the edges' weight attribute.
+  - **maxIterations** _?number_ [`100`]: maximum number of iterations to perform.
+  - **tolerance** _?number_ [`1.e-6`]: convergence error tolerance.
+  - **weighted** _?boolean_ [`false`]: whether to use available weights or not.
+
+
 ### HITS
@@ -283,3 +313,2 @@
 
-
 ```js
@@ -286,0 +315,0 @@ import pagerank from 'graphology-metrics/centrality/pagerank';

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

90306

increased by7.04%

Number of package files

41

increased by5.13%

Lines of code

2187

increased by6.48%

Number of lines in readme file

556

increased by5.5%

Dependency changes

• + Addedgraphology-types@0.24.8(transitive)

• - Removedgraphology-types@0.24.7(transitive)

• Updatedgraphology-shortest-path@^1.5.1