Skip to content

Instantly share code, notes, and snippets.

@emeeks

emeeks/index.html

Last active February 6, 2024 09:02
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 5 You must be signed in to fork a gist
  • Save emeeks/f448eef177b5fe94b1c0 to your computer and use it in GitHub Desktop.
Save emeeks/f448eef177b5fe94b1c0 to your computer and use it in GitHub Desktop.
Download ZIP
Visualizing the PageRank Model
Raw
readme.md

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.

Raw
index.html
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Visualizing PageRank Centrality</title>
<meta charset="utf-8" />
</head>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="http://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>
Raw
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}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment