Awesome
ngraph.pagerank
PageRank algorithm implementation in JavaScript. This module is part of ngraph family.
usage
Let's compute PageRank for a simple graph with two nodes, one edge:
var graph = require('ngraph.graph')();
graph.addLink(1, 2);
var pageRank = require('ngraph.pagerank');
var rank = pageRank(graph);
This code will compute PageRank for two nodes:
{
"1": 0.350877,
"2": 0.649123
}
configuring
The PageRank algorithm allows you to specify a probability at any step that a person will continue clicking outgoing links. This probability in some literature is called a dumping factor, and is recommended to be set between 0.80 and 0.90.
To configure this probability use the second, optional argument of the pageRank()
function:
// by default this value is 0.85. Bump it to 0.9:
var internalJumpProbability = 0.90;
var rank = pageRank(graph, internalJumpProbability);
Current implementation uses approximate solution for eigenvector problem. To specify precision level use the last optional argument:
var internalJumpProbability = 0.85;
// by default it's set to 0.005, let's increase it:
var precision = 0.00001;
var rank = pageRank(graph, internalJumpProbability, precision);
precision
will affect algorithm performance and serves as an exit criteria:
|r(t) - r(t - 1)| < precision
Here r(t)
is eigenvector (or pageRank of a graph) at time step t
.
performance
The focus of this module is to be very fast. I tried multiple approaches, including
- Easy to read code with plain old javascript objects
- Approach with typed arrays, where objects are stored into flat array
- C++ version of the code, compiled into asm.js and extracted into separate module
So far approach with typed array gives the fastest results in v8/node.js 0.12:
43 ops/sec
. asm.js version is the fastest when executed inside
spider monkey (firefox) with 50 ops/sec
. Unfortunately asm.js version
gives terrible results in iojs 1.5
(around 20 ops/sec), and while performs at
47 ops/sec
in node.js 0.12
the deviation is too big (around 7%) to call it
stable. I'm frankly a little bit lost and not sure why asm.js gives such poor
results in v8. So currently sticking with approach with typed arrays.
demo
A small demo is available here. It computes PageRank for a graph from Wikipedia and then renders it with force based layout.
install
With npm do:
npm install ngraph.pagerank
Or download from CDN:
<script src='https://unpkg.com/ngraph.pagerank@2.1.0/dist/ngraph.pagerank.min.js'></script>
If you download from CDN the library will be available under pageRank
global name.
license
MIT
TODO:
Implement topic-specific rank?