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.
<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>
{
"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}
]
}