PageRank

PageRank is an algorithm used by Google Search to rank websites in their search engine results.
Before viewing this visualization, we recommend you give the E-Factory Page a read (link provided under References).
The top-most view simulates a mini-internet: a web of connections. A directed edge from A to B means that web Page A provides a link to B. The next view will display the final ranks. We first calculate the no. of links a page has, i.e., its outgoing edges and display in the next view pane.
The last visual is an array of arrays. From 0 (top of matrix) down to the Nth Node (bottom), each stores an array of the Nodes pointing to it.
For eg-if the first line of Matrix says “2 3 -1 -1 -1”, it means Web Page 2 and 3 have a link to Web Page 0. The -1s represent null (nothing).
The bottom-most view is where you will see the logs as the algorithm progresses.

Applications

• Web Page Indexing for refining search results

Complexity

• Time: worst ![](https://latex.codecogs.com/svg.latex?O(

  V

  +

  E

  ))

• Space: worst ![](https://latex.codecogs.com/svg.latex?O(

  V

  ))

References

• Princeton university
• E-Factory

Implementations

• Python
• JavaScript

• 1
  # TODO: Implement in Python
  

• 1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
  100
  101
  102
  103
  104
  105
  106
  107
  function filledArray(length, value) {
    return Array(...Array(length)).map(Number.prototype.valueOf, value);
  }
  
  /*
    PageRank Algorithm Version 2
    Equation:
      PR (X) = ( (1 - D)/N ) + D (Summation i->X (PR (I) / Out (i)))
    NOTE: Algorithm uses the recommended damping factor (D). Number of iterations is small because only a small Web of 5 Pages is simulated
  */
  
  function arraySum(array) {
    return array.reduce(
      (sum, curr) =>
        sum + (curr ? 1 : 0) // if curr is 0 (no edge) or undefined (loop not allowed), sum remains unchanged
      , 0,
    );
  }
  
  function showOutgoingEdges(i) {
    G[i].forEach((edgeExists, j) => {
      if (edgeExists) {
        
      }
    });
  }
  
  // PRECOMPUTATIONS
  
  console.log('Calculate Outgoing Edge Count for each Node');
  
  (function calculateOEC() {
    G.forEach((relations, i) => {
      outgoingEdgeCounts[i] = arraySum(relations);
      showOutgoingEdges(i);
  
    });
  }());
  
  console.log('determine incoming nodes for each node');
  
  (function determineIN() {
    for (let i = 0; i < G.length; i++) {
      for (let j = 0; j < G.length; j++) {
        if (G[i][j]) {
          // there's an edge FROM i TO j
  
          const nextPos = incomingNodes[j].indexOf(-1);
          incomingNodes[j][nextPos] = i;
          
        }
      }
    }
  
    // console.log ('All -1s will be removed from incoming node records, they are irrelevant');
    incomingNodes.forEach((arr) => {
      arr.splice(arr.indexOf(-1));
    });
  }());
  
  function updateRank(nodeIndex) {
    let inNodeSummation = 0;
    let result;
  
    console.log(`Updating rank of ${nodeIndex}`);
    console.log(`The incoming Nodes of ${nodeIndex} are being highlighted`);
  
    incomingNodes[nodeIndex].forEach((incoming, i) => {
  
      inNodeSummation += (ranks[incoming] / outgoingEdgeCounts[incoming]);
  
    });
    
    console.log(`In-Node summation of ${nodeIndex} = ${inNodeSummation}`);
  
    result = ((1 - damping) / G.length) + (damping * inNodeSummation); // notice the subtle difference between equations of Basic PR & PR version 2 (divide by N)
    
    console.log(`Therefore, using Equation, new rank of ${nodeIndex} = ${result}`);
    
    return result;
  }
  
  let damping = 0.85;
  let iterations = 7;
  const initialRank = 1.0;
  
  console.log(`Initialized all Page ranks to ${initialRank}`);
  
  ranks = filledArray(G.length, initialRank);
  
  console.log('Begin execution of PageRank Version #1');
  console.log('Equation used: PR (X) = (1 - D) + D (In-Node-Summation i->X (PR (I) / Out (i)))');
  console.log('D = Damping Factor, PR (X) = Page rank of Node X, i = the ith In-Node of X, Out (i) = outgoing Edge Count of i');
  console.log('');
  
  while (iterations--) {
    for (let node = 0; node < ranks.length; node++) {
      ranks[node] = updateRank(node);
      
    }
  }
  
  console.log('Page Ranks have been converged to.');
  ranks.forEach((rank, node) => {
    console.log(`Rank of Node #${node} = ${rank}`);
  });
  console.log('Done');