Skip to content

Instantly share code, notes, and snippets.

@renaud

renaud/.block

Last active October 24, 2017 09:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save renaud/5f578e9d07b5cd0b9b1a623a8cdf94f4 to your computer and use it in GitHub Desktop.
Save renaud/5f578e9d07b5cd0b9b1a623a8cdf94f4 to your computer and use it in GitHub Desktop.
Download ZIP
Visualizing PageRank
Raw
.block
license: apache-2.0
height: 650
scrolling: no
border: no
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 step. 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 pink and the new node is stroked in black and "walk" appears as 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.

Raw
index.html
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Visualizing PageRank</title>
<meta charset="utf-8" />
</head>
<script src="http://d3js.org/d3.v3.min.js"></script>
<style>
svg {
background:#FCFCFC;
border: 1px black solid;
}
#annotation {
display: fixed;
top: 20px;
left: 20px;
font-size:16px;
font-weight:900;
}
button {
background-color: gray;
border: 1px black solid;
color: white;
/*padding: 15px 15px;*/
text-align: center;
text-decoration: none;
display: inline-block;
}
</style>
<body onload="pagerankViz()">
<div id="annotation">&nbsp;</div>
<p></p>
<div id="controls"></div>
<svg height="600" width="900"></svg>
<footer>
<script>
miserables2 = {
"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":1},
{"name":"Valjean","group":1},
{"name":"Marguerite","group":1},
{"name":"Mme.deR","group":1},
{"name":"Isabeau","group":1},
{"name":"Gervais","group":1},
{"name":"Tholomyes","group":1},
{"name":"Listolier","group":1},
{"name":"Fameuil","group":1},
{"name":"Blacheville","group":1},
{"name":"Favourite","group":1},
{"name":"Dahlia","group":1},
{"name":"Zephine","group":1},
{"name":"Fantine","group":1},
{"name":"Mme.Thenardier","group":1},
{"name":"Thenardier","group":1},
{"name":"Cosette","group":1},
{"name":"Javert","group":1},
{"name":"Fauchelevent","group":1},
{"name":"Bamatabois","group":1},
{"name":"Perpetue","group":1},
{"name":"Simplice","group":1},
{"name":"Scaufflaire","group":1},
{"name":"Woman1","group":1},
{"name":"Judge","group":1},
{"name":"Champmathieu","group":1},
{"name":"Brevet","group":1},
{"name":"Chenildieu","group":1},
{"name":"Cochepaille","group":1},
{"name":"Pontmercy","group":1},
{"name":"Boulatruelle","group":1},
{"name":"Eponine","group":1},
{"name":"Anzelma","group":1},
{"name":"Woman2","group":1},
{"name":"MotherInnocent","group":1},
{"name":"Gribier","group":1},
{"name":"Jondrette","group":1},
{"name":"Mme.Burgon","group":1},
{"name":"Gavroche","group":1},
{"name":"Gillenormand","group":1},
{"name":"Magnon","group":1},
{"name":"Mlle.Gillenormand","group":1},
{"name":"Mme.Pontmercy","group":1},
{"name":"Mlle.Vaubois","group":1},
{"name":"Lt.Gillenormand","group":1},
{"name":"Marius","group":1},
{"name":"BaronessT","group":1},
{"name":"Mabeuf","group":1},
{"name":"Enjolras","group":1},
{"name":"Combeferre","group":1},
{"name":"Prouvaire","group":1},
{"name":"Feuilly","group":1},
{"name":"Courfeyrac","group":1},
{"name":"Bahorel","group":1},
{"name":"Bossuet","group":1},
{"name":"Joly","group":1},
{"name":"Grantaire","group":1},
{"name":"MotherPlutarch","group":1},
{"name":"Gueulemer","group":1},
{"name":"Babet","group":1},
{"name":"Claquesous","group":1},
{"name":"Montparnasse","group":1},
{"name":"Toussaint","group":1},
{"name":"Child1","group":1},
{"name":"Child2","group":1},
{"name":"Brujon","group":1},
{"name":"Mme.Hucheloup","group":1}
],
"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}
]
};
function pagerankViz() {
speedVal = 200;
dampingFactor = 0.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 = miserables2;
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(-800)
.linkDistance(20)
.size([900, 600])
.gravity(0.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", 0.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")
.attr("r", 2)
.style("fill", "rgb(245, 169, 169)");
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("jump!");
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("&nbsp;");
model.nextStep = randomStart;
return;
}
d3.select("#annotation").style("color", "#F5A9A9").html("walk");
//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("&nbsp;");
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")
.text(function(d) {
return d.pageRank / totalPageRank > 0.03 ? f(d.pageRank / totalPageRank) : "";
});
};
function runOnce() {
speedVal = 1;
model.autoCount = 1;
startAuto();
};
function runTwenty() {
speedVal = 1000;
model.autoCount = 100;
startAuto();
};
function runThousand() {
speedVal = 20;
model.autoCount = 1000;
startAuto();
};
function runTenThousand() {
speedVal = 10;
model.autoCount = 10000;
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("step").on("click", runOnce);
d3.select("#controls").append("button").html("run slow").on("click", runTwenty);
//d3.select("#controls").append("button").html("run 1000 times").on("click", runThousand);
d3.select("#controls").append("button").html("run fast").on("click", runTenThousand);
};
</script>
<p style="font-size: 10px">adapted by Renaud from <a href="http://bl.ocks.org/emeeks/f448eef177b5fe94b1c0">Elijah Meeks</a></p>
</footer>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment