// noprotect

// Keith O'Hara <kohara@bard.edu>

// random network pagerank simulation

// 

// d3 viz based on 

// http://bl.ocks.org/mbostock/2706022

​

​

var N = 15;  // number of nodes

var E = 1;   // number of outlinks per node

var width = 800, height = 600;

var S = 0.75;

var K = 500;

​

function randint(lo, hi){

  return Math.floor(Math.random() * (hi - lo)) + lo;

}

​

var pages = [];

var network = {};

​

for (var i = 0; i < N; i++){

  var node = "N" + i;

  pages.push(node);

  network[node] = [];

  var j = 0;

  while (j < E){

    var e = randint(0, N);

    if (e != i){

      network[node].push("N" + e);

      j++;

    }

  }

}

var vertices = createNodes();

var edges = createLinks();

​

​

var scores = vertices.slice();

for (var i = 0; i < N; i++){

  scores[i] = 1/N;

}

​

var force = d3.layout.force()

  .nodes(vertices)

  .links(edges)

  .size([width, height])

  .linkDistance(90)

  .charge(-1200)

  .on("tick", tick)

  .on("end", done)

  .start();

​

var svg = d3.select("body").append("svg")

  .attr("width", width)

  .attr("height", height);

​

var link = svg.selectAll(".link")

  .data(force.links())

  .enter().append("line")

  .attr("marker-end", "url(#arrow)")

  .attr("class", "link");

var node = svg.selectAll(".node")

  .data(force.nodes())

  .enter()

  .append("g")

  .attr("class", "node")

  .call(force.drag);

​

svg.append("defs").append("marker")

  .attr("id", "arrow")

  .attr("viewBox", "0 -5 10 10")

  .attr("refX", 56)

  .attr("refY", 0)

  .attr("markerUnits","strokeWidth")

  .attr("markerWidth", 6)

  .attr("markerHeight", 6)

  .attr("orient", "auto")

.append("path")

  .attr("d", "M0,-5L10,0L0,5")

  .attr("stroke", "#ccc")

  .attr("fill", "#ccc");

​

node.append("circle")

  .attr("r", 18);

​

node.append("text")

  .attr("id", "name")

  .attr("x", 0)

  .attr("y", -4)

  .attr("text-anchor", "middle")

  .attr("dy", ".35em")

  .text(function(d, i) { return d.name; });

​

node.append("text")

  .attr("id", "score")

  .attr("x", 0)

  .attr("y", 6)

  .attr("text-anchor", "middle")

  .attr("dy", ".35em")

  .text((1/N).toFixed(2));

​

function done(){

  scores = computePageRank(pages, network);

}

​

function computePageRank(vertices, network){

  var newscores = scores.slice();

  var k = 0;

  function nextStep(){  

    for (var i = 0; i < N; i++){

      newscores[i] = 0;

    }

    for (var i = 0; i < N; i++){

      var name_i = pages[i];

      var neighbors_i = network[name_i];

      if (neighbors_i.length === 0){

        newscores[i] += scores[i];

      }

      else{

        var s = scores[i] / neighbors_i.length;

        for (var e = 0; e < neighbors_i.length; e++){

          var t = pages.indexOf(neighbors_i[e]);

          newscores[t] += s;

        }

      }

    }

    for (var i = 0; i < N; i++){

      scores[i] = S*newscores[i];

      scores[i] += (1.0-S)/N;

    }

    k = k + 1;

    updateViz();

    if (k < K) setTimeout(nextStep, 1000);

  }

  nextStep();

  return scores;

}

​

function createLinks(){ // for d3 

  var links = [];

  for (var src = 0; src < pages.length; src = src + 1){

    var srcp = pages[src];

    if (network[srcp]){

      for (var j = 0; j < network[srcp].length; j = j + 1){

        var tgt = pages.indexOf(network[srcp][j]);

        if (src != tgt){

          links.push({"source":src, "target":tgt});

        }

      }

    }

  }

  return links;

}

​

function createNodes(){ // for d3 

  var nodes = [];

  for (var src = 0; src < pages.length; src = src + 1){

    nodes.push({name: pages[src]});

  }

  return nodes;

}

​

function tick() {

  link.attr("x1", function(d) { return d.source.x; })

      .attr("y1", function(d) { return d.source.y; })

      .attr("x2", function(d) { return d.target.x; })

      .attr("y2", function(d) { return d.target.y; });

  node.attr("transform", function(d) 

           { return "translate(" + d.x + "," + d.y + ")"; }); 

}

​

function updateViz(){

  var scale = d3.scale.pow().exponent(0.5)

            .domain([d3.min(scores), d3.max(scores)])

            .range([18, 40]);

  node.selectAll("circle")

    .transition()

    .delay(1000)

    .attr("r", function(d){return scale(scores[d.index]);});

​

  node.selectAll("#name")

    .attr("x", 0)

    .attr("y", -4)

    .attr("text-anchor", "middle")

    .attr("dy", ".35em")

    .text(function(d) { return d.name; });

  node.selectAll("#score")

    .attr("x", 0)

    .attr("y", 6)

    .attr("text-anchor", "middle")

    .attr("dy", ".35em")

    .text(function(d) { return scores[d.index].toFixed(2); });

}

​

$(document).ready(function(){});

​