Understanding PageRank in a network graph

README.md

Visualizing pagerank of nodes in a graph.

Example studied is that of extracting most informative sentences from a textual document for auto summarization. Uses the LexRank algorithm. A graph G is created where :

• Nodes: All sentences of the document.
• Edges: There is an edge between two nodes if the frequency vectors of the corresponding sentences have (cosine) similarity above a threshold. For more details on SentenceGraph, refer to TextGraphics

LexRank asserts that PageRank (now called LexRank) scores of sentences in such a graph can be used to rank sentences in the order of their relevance to the document. And in turn, can be used for generating a summary of teh document.

Usage:

• The landing page has a sentence graph, created from the text of my answer to a question on Quora.
• Click on the Rank Nodes button, the nodes will be re-sized according to their LexRank scores.
• Click on a node will print the associated sentence on the right side of the canvas. Try different nodes to explore the sentences.
• Click on the text of the sentence on the right side, will remove the sentence from the view.

graphContents.json

{"nodes": [{"radius": 0.04660802677582351, "name": " I don't think Witten is as strong a mathematician as a professional mathematician"}, {"radius": 0.05459923584934769, "name": "Edward Witten knew basic mathematics very well, as you would expect from a physicist working on quantum field theory"}, {"radius": 0.04418939973503892, "name": " The interaction with Atiyah lead to some of Witten's greatest work on topology and geometry"}, {"radius": 0.03599892404859607, "name": " They was never rigorously defined and their properties were never proven in Witten's work"}, {"radius": 0.04409955938279091, "name": " But this intrigued Witten and he decided to learn this way of approaching the subject"}, {"radius": 0.03620560796752431, "name": " He talked to Atiyah, who I believe, was the brand ambassador for mathematical physics at that time (You would be surprised to know how many top researchers in this area were influenced by Atiyah)"}, {"radius": 0.046176301837732935, "name": " I remember reading about Witten in a book about the founders of Index Theory (I forgot what it's called)"}, {"radius": 0.03708109281505356, "name": " And once you acquire a level of mathematical maturity (if you are a mathematician, you know what I'm talking about), you can pretty much dive into any subject and start reading"}, {"radius": 0.04230935448247822, "name": " He used the advance mathematics in his work, but Witten's genius is in seeing the connections"}, {"radius": 0.035446390382893676, "name": " It has biographical essays on Michael Atiyah, Isadore Singer, Raol Bott and other associated with the inception of Index theory"}, {"radius": 0.03531237898037547, "name": " He probably knows more maths than a smart beginning grad student in mathematics"}, {"radius": 0.06087255244991109, "name": " Witten being a physicist had some level of mathematical maturity which was enhanced multifold after he started working with advance mathematics"}, {"radius": 0.034955211637594505, "name": " He wrote his PhD thesis on topics related to strong interactions under David Gross"}, {"radius": 0.05809463228216917, "name": " It was at Oxford, Witten learnt a lot of advance mathematics"}, {"radius": 0.05228280256180224, "name": " Witten writes that when he was a post-doc at Harvard, Atiyah gave a talk on mathematics related to QFT which none of the physicists (including Witten) understood"}, {"radius": 0.0487056765658605, "name": " Other than a proof of Positive Energy theorem, I don't think Witten rigorously proved any mathematical statements"}, {"radius": 0.04545454545454538, "name": " Which inspired some mathematicians like Kontsevich to do wonders"}, {"radius": 0.05988187647975896, "name": " There was an essay written by Edward Witten on Atiyah"}, {"radius": 0.05297126909253317, "name": " Atiyah invited Witten to spend one year at Oxford and work with him"}, {"radius": 0.04545454545454529, "name": " Witten, with others, came up with some topological/symplectic invariants and these invariants arose as physical quantities in QFTs"}, {"radius": 0.037846070309079174, "name": " Written said in that essay how Atiyah guided him on what to read and he read tons of yellow Springer books on topology and geometry"}, {"radius": 0.04545454545454528, "name": " He showed you can see knot invariants in as physical quantities in QFTs"}], "links": [{"source": 0, "target": 0, "value": 0}, {"source": 0, "target": 1, "value": 0}, {"source": 0, "target": 11, "value": 0}, {"source": 0, "target": 12, "value": 0}, {"source": 0, "target": 13, "value": 0}, {"source": 0, "target": 6, "value": 0}, {"source": 0, "target": 14, "value": 0}, {"source": 0, "target": 4, "value": 0}, {"source": 0, "target": 17, "value": 0}, {"source": 0, "target": 18, "value": 0}, {"source": 0, "target": 15, "value": 0}, {"source": 1, "target": 1, "value": 0}, {"source": 1, "target": 15, "value": 0}, {"source": 1, "target": 5, "value": 0}, {"source": 1, "target": 11, "value": 0}, {"source": 1, "target": 13, "value": 0}, {"source": 1, "target": 6, "value": 0}, {"source": 1, "target": 14, "value": 0}, {"source": 1, "target": 4, "value": 0}, {"source": 1, "target": 8, "value": 0}, {"source": 1, "target": 9, "value": 0}, {"source": 1, "target": 17, "value": 0}, {"source": 1, "target": 18, "value": 0}, {"source": 1, "target": 10, "value": 0}, {"source": 2, "target": 2, "value": 0}, {"source": 2, "target": 3, "value": 0}, {"source": 2, "target": 20, "value": 0}, {"source": 2, "target": 14, "value": 0}, {"source": 2, "target": 8, "value": 0}, {"source": 2, "target": 17, "value": 0}, {"source": 2, "target": 18, "value": 0}, {"source": 3, "target": 18, "value": 0}, {"source": 3, "target": 8, "value": 0}, {"source": 3, "target": 3, "value": 0}, {"source": 3, "target": 15, "value": 0}, {"source": 4, "target": 11, "value": 0}, {"source": 4, "target": 13, "value": 0}, {"source": 4, "target": 6, "value": 0}, {"source": 4, "target": 14, "value": 0}, {"source": 4, "target": 4, "value": 0}, {"source": 4, "target": 7, "value": 0}, {"source": 4, "target": 17, "value": 0}, {"source": 4, "target": 18, "value": 0}, {"source": 4, "target": 15, "value": 0}, {"source": 5, "target": 5, "value": 0}, {"source": 5, "target": 11, "value": 0}, {"source": 5, "target": 7, "value": 0}, {"source": 5, "target": 9, "value": 0}, {"source": 5, "target": 15, "value": 0}, {"source": 6, "target": 7, "value": 0}, {"source": 6, "target": 13, "value": 0}, {"source": 6, "target": 6, "value": 0}, {"source": 6, "target": 14, "value": 0}, {"source": 6, "target": 9, "value": 0}, {"source": 6, "target": 17, "value": 0}, {"source": 6, "target": 11, "value": 0}, {"source": 6, "target": 18, "value": 0}, {"source": 6, "target": 15, "value": 0}, {"source": 7, "target": 11, "value": 0}, {"source": 7, "target": 7, "value": 0}, {"source": 7, "target": 15, "value": 0}, {"source": 8, "target": 11, "value": 0}, {"source": 8, "target": 13, "value": 0}, {"source": 8, "target": 14, "value": 0}, {"source": 8, "target": 8, "value": 0}, {"source": 8, "target": 10, "value": 0}, {"source": 9, "target": 9, "value": 0}, {"source": 10, "target": 11, "value": 0}, {"source": 10, "target": 13, "value": 0}, {"source": 10, "target": 14, "value": 0}, {"source": 10, "target": 10, "value": 0}, {"source": 11, "target": 15, "value": 0}, {"source": 11, "target": 13, "value": 0}, {"source": 11, "target": 14, "value": 0}, {"source": 11, "target": 17, "value": 0}, {"source": 11, "target": 11, "value": 0}, {"source": 11, "target": 18, "value": 0}, {"source": 12, "target": 14, "value": 0}, {"source": 12, "target": 12, "value": 0}, {"source": 13, "target": 15, "value": 0}, {"source": 13, "target": 13, "value": 0}, {"source": 13, "target": 14, "value": 0}, {"source": 13, "target": 17, "value": 0}, {"source": 13, "target": 18, "value": 0}, {"source": 14, "target": 14, "value": 0}, {"source": 14, "target": 17, "value": 0}, {"source": 14, "target": 18, "value": 0}, {"source": 14, "target": 20, "value": 0}, {"source": 14, "target": 15, "value": 0}, {"source": 15, "target": 17, "value": 0}, {"source": 15, "target": 18, "value": 0}, {"source": 15, "target": 15, "value": 0}, {"source": 16, "target": 16, "value": 0}, {"source": 17, "target": 17, "value": 0}, {"source": 17, "target": 18, "value": 0}, {"source": 17, "target": 20, "value": 0}, {"source": 18, "target": 18, "value": 0}, {"source": 18, "target": 20, "value": 0}, {"source": 19, "target": 21, "value": 0}, {"source": 19, "target": 19, "value": 0}, {"source": 20, "target": 20, "value": 0}, {"source": 21, "target": 21, "value": 0}]}

index.html

<!DOCTYPE html>
<meta charset="utf-8">
<style>

.node {
  stroke: #fff;
  stroke-width: 1.5px;
}

.link {
  stroke: #999;
  stroke-opacity: .8;
}

button{
  height: 30px;
  width: 200px;
  font-style: sans-serif;
  position: absolute;
  top: 15%;
  left: 1%;
  /*background-color: lightblue;*/
  font-size: 15px;
}

svg{
  position: absolute;
  top:20%;
  left:1%;
  /*background-color: red;*/
}

.div1{
  position: absolute;
  top:20%;
  left: 60%;
}

</style>
<body>
<h2>Understanding PageRank in a network graph.</h2>
<h3>Case Study: Ranking sentences in a document for auto text summarization.</h3>

<button>Rank Nodes</button>
<div class="div1"></div>
<!-- <script src="d3.js"></script> -->
<script type="text/javascript" src="http://d3js.org/d3.v3.min.js"></script>
<script>

var width = 800,
    height = 500;


var color = d3.scale.category20();

var x = d3.scale.linear()
        .range([7, 20]);

d3.select("button")
    .on("click", function(){
      svg.selectAll(".node")
        .transition()
        .duration(1000)
        .attr("r", function(d){return x(d.radius);});
      });


var force = d3.layout.force()
    .charge(-300)
    .linkDistance(200)
    .size([width, height]);

var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);

d3.json("graphContents.json", function(error, graph) {
  if (error) throw error;

  force
      .nodes(graph.nodes)
      .links(graph.links)
      .start();

  x.domain(d3.extent(graph.nodes, function(d){return d.radius;})).nice();


  var link = svg.selectAll(".link")
      .data(graph.links)
    .enter().append("line")
      .attr("class", "link")
      .style("stroke-width", 1.2);


  var node = svg.selectAll(".node")
      .data(graph.nodes)
    .enter().append("circle")
      .attr("class", "node")
      .on("click", function(d){
        d3.select(".div1")
          .append("p")
          .attr("class", "p")
          .html(d.name)
          .on("click", function(){
            this.remove();
          }); 
      })
      .attr("r", 10)
      .style("fill", function(d) { return color(d.group); })
      .call(force.drag);

  node.append("text")
      .attr("x", 12)
      .attr("dy", ".35em")
      .text(function(d) { return d.name; });





  force.on("tick", function() {
    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("cx", function(d) { return d.x; })
        .attr("cy", function(d) { return d.y; });
  });



});

</script>