block by emeeks f448eef177b5fe94b1c0

Visualizing the PageRank Model

Full Screen

This is a simple attempt to visualize the model that the PageRank algorithm is based on. PageRank is a method for discovering central nodes in a network by treating nodes as web pages and edges as links between them, upon which a simulated web surfer starts on a random page and clicks a random link, navigating to a new page, with a 15% chance that the surfer ends that session. In this example, you can step through the process by clicking “run once”. The first random node is colored green and “start” appears at the top. If the random walk goes to a new node, the link is colored red and the new node is stroked in black and “step” appears as the top. If the random walk is ended, “end” will appear at the top. After each tick, new PageRank values are calculated for each node by totaling the number of visits to that node and dividing it by summing the number of total visits to any node in the network. You’ll notice that early on the PageRank values can change dramatically, but as you run more passes they eventually stabilize. You can see that by running a hundred or a thousand random walks. This is not a visualization of the PageRank algorithm, but rather the model that it’s based on.

index.html

<html xmlns="//www.w3.org/1999/xhtml">
<head>
  <title>Visualizing PageRank Centrality</title>
  <meta charset="utf-8" />
</head>
<script src="//d3js.org/d3.v3.min.js"></script>
<script src="//d3js.org/colorbrewer.v1.min.js"></script>
<style>
  
  svg {
    background:#FCFCFC;
    border: 1px black solid;
  }
  #annotation {
    display: fixed;
    top: 20px;
    left: 20px;
    font-size:16px;
    font-weight:900;
  }
</style>
<body onload="pagerankViz()">
  <div id="annotation">X</div>
  <div id="controls"></div>
  <svg height="500" width="500"></svg>
  <footer>
<script>

function pagerankViz() {
  
  speedVal = 200;
  dampingFactor = .85;
  maxPageRank = 0;
  nodeAmount = 10;
  currentPagingNodeID = 0;
  model = {};
  model.autoCount = 0;
  pageRankColoration = d3.scale.linear().domain([0,1]).range(["black","#F5A9A9"])
  pageRankSize = d3.scale.linear().domain([0,1]).range([2,12])
  var f = d3.format(",.2f");
  
  ///GRAPH GENERATOR
  nodesSeed = d3.range(nodeAmount);
  numConnections = 2;
  nodes = [];
  edges = [];
  for (x in nodesSeed) {
    nodes.push({id: x, label: "node " + x, pageRank: 0})
  }
  
  //This is just making a bunch of random edges 
  var pass = Math.floor(Math.random() * 10) + 2;
  var z = 0;
  while (z < pass) {
  for (x in nodes) {
    var y = Math.floor(Math.random() * nodes.length);
    var numEdges = y + 1;
    while (y <= numEdges) {
      if (y < nodes.length && y != x) {
        edges.push({source: nodes[x], target: nodes[y], id:nodes[x].id + "-" + nodes[y].id})
      }
      y++;
    }
    }
    z++;
  }

  d3.json("miserables.json", function(error, graph) {
      model.nextStep = randomStart;

      graph.nodes.forEach( function(node,i) {
      node.id = i;
      node.pageRank = 0;
      })
    graph.links.forEach( function(edge,i) {
      edge.id = edge.source.id + "-" + edge.target.id;
    })
    var svg = d3.select("svg").on("click", function() {model.nextStep()})

    nodes = graph.nodes;
    edges = graph.links;
    nodeAmount = graph.nodes.length;
    force = d3.layout.force()
      .charge(-500)
      .linkDistance(20)
      .size([500, 500])
      .gravity(.5)
      .on("tick", redrawGraph)
      .nodes(nodes)
      .links(edges)
      
      svg.append("g").attr("class", "linkG").selectAll("line.link").data(edges).enter().append("line")
      .attr("id", function (d,i) {return "edge" + i})
      .attr("class", "link")
      .style("opacity", .5)
      .style("stroke-width", "1px")
      .style("stroke", "black")

      
      var nodeEnter = svg.append("g").attr("class", "nodeG").selectAll("g.node").data(nodes).enter().append("g")
      .attr("id", function (d,i) {return "node" + i})
      .attr("class", "node")
      .call(force.drag());

      nodeEnter.append("circle")
      .style("stroke-width", "1px")
      .style("stroke", "black")
      .attr("r", 6)
      .style("fill",function() {
    return "hsl(" + Math.random() * 360 + ",100%,50%)";
    })
      
      nodeEnter.append("text")
      .style("text-anchor", "middle")
      .style("font-size", "10px")
      .attr("y", 4)
      .text("")
      
      function redrawGraph() {
        d3.selectAll("g.node")
        .attr("transform", function (d) {return "translate(" + d.x + "," + d.y + ")"});
        
        d3.selectAll("line.link")
        .attr("x1", function (d) {return d.source.x})
        .attr("x2", function (d) {return d.target.x})
        .attr("y1", function (d) {return d.source.y})
        .attr("y2", function (d) {return d.target.y});
        
        
        }
        
        force.start();

      /// END GRAPH GENERATOR
      
      function randomStart() {
        d3.select("#annotation").style("color", "green").html("start");
        d3.selectAll("g.node").select("circle")
      .style("stroke-width", "0")
      .style("fill", "#F5A9A9");
      d3.selectAll("line.link").style("stroke-width", "1px").style("stroke", "gray");
      
        currentPagingNodeID = Math.floor(Math.random() * nodeAmount);
        d3.select("#node" + currentPagingNodeID).select("circle").style("fill", "green")
        model.nextStep = stepTo;
        increasePageRank();
      }
      
      function stepTo() {
        if (Math.random() > dampingFactor) {
        d3.select("#annotation").style("color", "black").html("end");
          model.nextStep = randomStart;
          return;
        }
        d3.select("#annotation").style("color", "#F5A9A9").html("step");

        //undirected network
/*        var connectingEdges = edges.filter(function(d) {
          return d.source.id == currentPagingNodeID || d.target.id == currentPagingNodeID
        })
*/
        //directed network
        var connectingEdges = edges.filter(function(d) {
          return d.source.id == currentPagingNodeID;
        })
        
        if (connectingEdges.length == 0) {
          d3.select("#annotation").style("color", "black").html("end");
          model.nextStep = randomStart;
          return;
        }

        var randomEdge = Math.floor(Math.random() * connectingEdges.length);
      d3.selectAll("line.link").filter(function(d) {return d == connectingEdges[randomEdge]}).transition().duration(speedVal).style("stroke-width", "4px").style("stroke", "red").each(function() {this.parentNode.appendChild(this)});
        
        currentPagingNodeID = connectingEdges[randomEdge].target.id == currentPagingNodeID ? connectingEdges[randomEdge].source.id : connectingEdges[randomEdge].target.id;
        increasePageRank();

      }
      
      function increasePageRank() {
      d3.select("#node" + currentPagingNodeID).select("circle").style("stroke-width", "2px").each(function (d) {d.pageRank += 1});
      maxPageRank = d3.max(nodes, function(d) {return d.pageRank});
      totalPageRank = d3.sum(nodes, function(d) {return d.pageRank});
      pageRankColoration.domain([0,maxPageRank]);
      pageRankSize.domain([0,maxPageRank])
      d3.selectAll("g.node").select("circle")
      .transition().duration(speedVal)
      .attr("r", function(d) {return pageRankSize(d.pageRank)})  
      d3.selectAll("g.node").select("text")
      //.style("fill", function(d) {return pageRankColoration(d.pageRank)})  
      .text(function(d) {return d.pageRank / totalPageRank > 0.03 ? f(d.pageRank / totalPageRank) : ""})  
      }
      
      function runOnce() {
        speedVal = 1;
        model.autoCount = 1;
        startAuto();
      }

      function runHundred() {
        speedVal = 200;
        model.autoCount = 100;
        startAuto();
      }
      
        function runThousand() {
        speedVal = 20;
        model.autoCount = 1000;
        startAuto();
      }

      function startAuto() {
        if (model.autoCount > 0) {
          setTimeout(autoRun,speedVal);
          model.autoCount--;
        }
        else {
          return;
        }
      }
      
      function autoRun() {
        model.nextStep();
        startAuto();
      }

      d3.select("#controls").append("button").html("run once").on("click", runOnce);
      d3.select("#controls").append("button").html("run 100 times").on("click", runHundred);
      d3.select("#controls").append("button").html("run 1000 times").on("click", runThousand);
  })
}

</script>
  </footer>
</body>
</html>

miserables.json

{
  "nodes":[
    {"name":"Myriel","group":1},
    {"name":"Napoleon","group":1},
    {"name":"Mlle.Baptistine","group":1},
    {"name":"Mme.Magloire","group":1},
    {"name":"CountessdeLo","group":1},
    {"name":"Geborand","group":1},
    {"name":"Champtercier","group":1},
    {"name":"Cravatte","group":1},
    {"name":"Count","group":1},
    {"name":"OldMan","group":1},
    {"name":"Labarre","group":2},
    {"name":"Valjean","group":2},
    {"name":"Marguerite","group":3},
    {"name":"Mme.deR","group":2},
    {"name":"Isabeau","group":2},
    {"name":"Gervais","group":2},
    {"name":"Tholomyes","group":3},
    {"name":"Listolier","group":3},
    {"name":"Fameuil","group":3},
    {"name":"Blacheville","group":3},
    {"name":"Favourite","group":3},
    {"name":"Dahlia","group":3},
    {"name":"Zephine","group":3},
    {"name":"Fantine","group":3},
    {"name":"Mme.Thenardier","group":4},
    {"name":"Thenardier","group":4},
    {"name":"Cosette","group":5},
    {"name":"Javert","group":4},
    {"name":"Fauchelevent","group":0},
    {"name":"Bamatabois","group":2},
    {"name":"Perpetue","group":3},
    {"name":"Simplice","group":2},
    {"name":"Scaufflaire","group":2},
    {"name":"Woman1","group":2},
    {"name":"Judge","group":2},
    {"name":"Champmathieu","group":2},
    {"name":"Brevet","group":2},
    {"name":"Chenildieu","group":2},
    {"name":"Cochepaille","group":2},
    {"name":"Pontmercy","group":4},
    {"name":"Boulatruelle","group":6},
    {"name":"Eponine","group":4},
    {"name":"Anzelma","group":4},
    {"name":"Woman2","group":5},
    {"name":"MotherInnocent","group":0},
    {"name":"Gribier","group":0},
    {"name":"Jondrette","group":7},
    {"name":"Mme.Burgon","group":7},
    {"name":"Gavroche","group":8},
    {"name":"Gillenormand","group":5},
    {"name":"Magnon","group":5},
    {"name":"Mlle.Gillenormand","group":5},
    {"name":"Mme.Pontmercy","group":5},
    {"name":"Mlle.Vaubois","group":5},
    {"name":"Lt.Gillenormand","group":5},
    {"name":"Marius","group":8},
    {"name":"BaronessT","group":5},
    {"name":"Mabeuf","group":8},
    {"name":"Enjolras","group":8},
    {"name":"Combeferre","group":8},
    {"name":"Prouvaire","group":8},
    {"name":"Feuilly","group":8},
    {"name":"Courfeyrac","group":8},
    {"name":"Bahorel","group":8},
    {"name":"Bossuet","group":8},
    {"name":"Joly","group":8},
    {"name":"Grantaire","group":8},
    {"name":"MotherPlutarch","group":9},
    {"name":"Gueulemer","group":4},
    {"name":"Babet","group":4},
    {"name":"Claquesous","group":4},
    {"name":"Montparnasse","group":4},
    {"name":"Toussaint","group":5},
    {"name":"Child1","group":10},
    {"name":"Child2","group":10},
    {"name":"Brujon","group":4},
    {"name":"Mme.Hucheloup","group":8}
  ],
  "links":[
    {"source":1,"target":0,"value":1},
    {"source":2,"target":0,"value":8},
    {"source":3,"target":0,"value":10},
    {"source":3,"target":2,"value":6},
    {"source":4,"target":0,"value":1},
    {"source":5,"target":0,"value":1},
    {"source":6,"target":0,"value":1},
    {"source":7,"target":0,"value":1},
    {"source":8,"target":0,"value":2},
    {"source":9,"target":0,"value":1},
    {"source":11,"target":10,"value":1},
    {"source":11,"target":3,"value":3},
    {"source":11,"target":2,"value":3},
    {"source":11,"target":0,"value":5},
    {"source":12,"target":11,"value":1},
    {"source":13,"target":11,"value":1},
    {"source":14,"target":11,"value":1},
    {"source":15,"target":11,"value":1},
    {"source":17,"target":16,"value":4},
    {"source":18,"target":16,"value":4},
    {"source":18,"target":17,"value":4},
    {"source":19,"target":16,"value":4},
    {"source":19,"target":17,"value":4},
    {"source":19,"target":18,"value":4},
    {"source":20,"target":16,"value":3},
    {"source":20,"target":17,"value":3},
    {"source":20,"target":18,"value":3},
    {"source":20,"target":19,"value":4},
    {"source":21,"target":16,"value":3},
    {"source":21,"target":17,"value":3},
    {"source":21,"target":18,"value":3},
    {"source":21,"target":19,"value":3},
    {"source":21,"target":20,"value":5},
    {"source":22,"target":16,"value":3},
    {"source":22,"target":17,"value":3},
    {"source":22,"target":18,"value":3},
    {"source":22,"target":19,"value":3},
    {"source":22,"target":20,"value":4},
    {"source":22,"target":21,"value":4},
    {"source":23,"target":16,"value":3},
    {"source":23,"target":17,"value":3},
    {"source":23,"target":18,"value":3},
    {"source":23,"target":19,"value":3},
    {"source":23,"target":20,"value":4},
    {"source":23,"target":21,"value":4},
    {"source":23,"target":22,"value":4},
    {"source":23,"target":12,"value":2},
    {"source":23,"target":11,"value":9},
    {"source":24,"target":23,"value":2},
    {"source":24,"target":11,"value":7},
    {"source":25,"target":24,"value":13},
    {"source":25,"target":23,"value":1},
    {"source":25,"target":11,"value":12},
    {"source":26,"target":24,"value":4},
    {"source":26,"target":11,"value":31},
    {"source":26,"target":16,"value":1},
    {"source":26,"target":25,"value":1},
    {"source":27,"target":11,"value":17},
    {"source":27,"target":23,"value":5},
    {"source":27,"target":25,"value":5},
    {"source":27,"target":24,"value":1},
    {"source":27,"target":26,"value":1},
    {"source":28,"target":11,"value":8},
    {"source":28,"target":27,"value":1},
    {"source":29,"target":23,"value":1},
    {"source":29,"target":27,"value":1},
    {"source":29,"target":11,"value":2},
    {"source":30,"target":23,"value":1},
    {"source":31,"target":30,"value":2},
    {"source":31,"target":11,"value":3},
    {"source":31,"target":23,"value":2},
    {"source":31,"target":27,"value":1},
    {"source":32,"target":11,"value":1},
    {"source":33,"target":11,"value":2},
    {"source":33,"target":27,"value":1},
    {"source":34,"target":11,"value":3},
    {"source":34,"target":29,"value":2},
    {"source":35,"target":11,"value":3},
    {"source":35,"target":34,"value":3},
    {"source":35,"target":29,"value":2},
    {"source":36,"target":34,"value":2},
    {"source":36,"target":35,"value":2},
    {"source":36,"target":11,"value":2},
    {"source":36,"target":29,"value":1},
    {"source":37,"target":34,"value":2},
    {"source":37,"target":35,"value":2},
    {"source":37,"target":36,"value":2},
    {"source":37,"target":11,"value":2},
    {"source":37,"target":29,"value":1},
    {"source":38,"target":34,"value":2},
    {"source":38,"target":35,"value":2},
    {"source":38,"target":36,"value":2},
    {"source":38,"target":37,"value":2},
    {"source":38,"target":11,"value":2},
    {"source":38,"target":29,"value":1},
    {"source":39,"target":25,"value":1},
    {"source":40,"target":25,"value":1},
    {"source":41,"target":24,"value":2},
    {"source":41,"target":25,"value":3},
    {"source":42,"target":41,"value":2},
    {"source":42,"target":25,"value":2},
    {"source":42,"target":24,"value":1},
    {"source":43,"target":11,"value":3},
    {"source":43,"target":26,"value":1},
    {"source":43,"target":27,"value":1},
    {"source":44,"target":28,"value":3},
    {"source":44,"target":11,"value":1},
    {"source":45,"target":28,"value":2},
    {"source":47,"target":46,"value":1},
    {"source":48,"target":47,"value":2},
    {"source":48,"target":25,"value":1},
    {"source":48,"target":27,"value":1},
    {"source":48,"target":11,"value":1},
    {"source":49,"target":26,"value":3},
    {"source":49,"target":11,"value":2},
    {"source":50,"target":49,"value":1},
    {"source":50,"target":24,"value":1},
    {"source":51,"target":49,"value":9},
    {"source":51,"target":26,"value":2},
    {"source":51,"target":11,"value":2},
    {"source":52,"target":51,"value":1},
    {"source":52,"target":39,"value":1},
    {"source":53,"target":51,"value":1},
    {"source":54,"target":51,"value":2},
    {"source":54,"target":49,"value":1},
    {"source":54,"target":26,"value":1},
    {"source":55,"target":51,"value":6},
    {"source":55,"target":49,"value":12},
    {"source":55,"target":39,"value":1},
    {"source":55,"target":54,"value":1},
    {"source":55,"target":26,"value":21},
    {"source":55,"target":11,"value":19},
    {"source":55,"target":16,"value":1},
    {"source":55,"target":25,"value":2},
    {"source":55,"target":41,"value":5},
    {"source":55,"target":48,"value":4},
    {"source":56,"target":49,"value":1},
    {"source":56,"target":55,"value":1},
    {"source":57,"target":55,"value":1},
    {"source":57,"target":41,"value":1},
    {"source":57,"target":48,"value":1},
    {"source":58,"target":55,"value":7},
    {"source":58,"target":48,"value":7},
    {"source":58,"target":27,"value":6},
    {"source":58,"target":57,"value":1},
    {"source":58,"target":11,"value":4},
    {"source":59,"target":58,"value":15},
    {"source":59,"target":55,"value":5},
    {"source":59,"target":48,"value":6},
    {"source":59,"target":57,"value":2},
    {"source":60,"target":48,"value":1},
    {"source":60,"target":58,"value":4},
    {"source":60,"target":59,"value":2},
    {"source":61,"target":48,"value":2},
    {"source":61,"target":58,"value":6},
    {"source":61,"target":60,"value":2},
    {"source":61,"target":59,"value":5},
    {"source":61,"target":57,"value":1},
    {"source":61,"target":55,"value":1},
    {"source":62,"target":55,"value":9},
    {"source":62,"target":58,"value":17},
    {"source":62,"target":59,"value":13},
    {"source":62,"target":48,"value":7},
    {"source":62,"target":57,"value":2},
    {"source":62,"target":41,"value":1},
    {"source":62,"target":61,"value":6},
    {"source":62,"target":60,"value":3},
    {"source":63,"target":59,"value":5},
    {"source":63,"target":48,"value":5},
    {"source":63,"target":62,"value":6},
    {"source":63,"target":57,"value":2},
    {"source":63,"target":58,"value":4},
    {"source":63,"target":61,"value":3},
    {"source":63,"target":60,"value":2},
    {"source":63,"target":55,"value":1},
    {"source":64,"target":55,"value":5},
    {"source":64,"target":62,"value":12},
    {"source":64,"target":48,"value":5},
    {"source":64,"target":63,"value":4},
    {"source":64,"target":58,"value":10},
    {"source":64,"target":61,"value":6},
    {"source":64,"target":60,"value":2},
    {"source":64,"target":59,"value":9},
    {"source":64,"target":57,"value":1},
    {"source":64,"target":11,"value":1},
    {"source":65,"target":63,"value":5},
    {"source":65,"target":64,"value":7},
    {"source":65,"target":48,"value":3},
    {"source":65,"target":62,"value":5},
    {"source":65,"target":58,"value":5},
    {"source":65,"target":61,"value":5},
    {"source":65,"target":60,"value":2},
    {"source":65,"target":59,"value":5},
    {"source":65,"target":57,"value":1},
    {"source":65,"target":55,"value":2},
    {"source":66,"target":64,"value":3},
    {"source":66,"target":58,"value":3},
    {"source":66,"target":59,"value":1},
    {"source":66,"target":62,"value":2},
    {"source":66,"target":65,"value":2},
    {"source":66,"target":48,"value":1},
    {"source":66,"target":63,"value":1},
    {"source":66,"target":61,"value":1},
    {"source":66,"target":60,"value":1},
    {"source":67,"target":57,"value":3},
    {"source":68,"target":25,"value":5},
    {"source":68,"target":11,"value":1},
    {"source":68,"target":24,"value":1},
    {"source":68,"target":27,"value":1},
    {"source":68,"target":48,"value":1},
    {"source":68,"target":41,"value":1},
    {"source":69,"target":25,"value":6},
    {"source":69,"target":68,"value":6},
    {"source":69,"target":11,"value":1},
    {"source":69,"target":24,"value":1},
    {"source":69,"target":27,"value":2},
    {"source":69,"target":48,"value":1},
    {"source":69,"target":41,"value":1},
    {"source":70,"target":25,"value":4},
    {"source":70,"target":69,"value":4},
    {"source":70,"target":68,"value":4},
    {"source":70,"target":11,"value":1},
    {"source":70,"target":24,"value":1},
    {"source":70,"target":27,"value":1},
    {"source":70,"target":41,"value":1},
    {"source":70,"target":58,"value":1},
    {"source":71,"target":27,"value":1},
    {"source":71,"target":69,"value":2},
    {"source":71,"target":68,"value":2},
    {"source":71,"target":70,"value":2},
    {"source":71,"target":11,"value":1},
    {"source":71,"target":48,"value":1},
    {"source":71,"target":41,"value":1},
    {"source":71,"target":25,"value":1},
    {"source":72,"target":26,"value":2},
    {"source":72,"target":27,"value":1},
    {"source":72,"target":11,"value":1},
    {"source":73,"target":48,"value":2},
    {"source":74,"target":48,"value":2},
    {"source":74,"target":73,"value":3},
    {"source":75,"target":69,"value":3},
    {"source":75,"target":68,"value":3},
    {"source":75,"target":25,"value":3},
    {"source":75,"target":48,"value":1},
    {"source":75,"target":41,"value":1},
    {"source":75,"target":70,"value":1},
    {"source":75,"target":71,"value":1},
    {"source":76,"target":64,"value":1},
    {"source":76,"target":65,"value":1},
    {"source":76,"target":66,"value":1},
    {"source":76,"target":63,"value":1},
    {"source":76,"target":62,"value":1},
    {"source":76,"target":48,"value":1},
    {"source":76,"target":58,"value":1}
  ]
}