This page was translated from French to English with the help of AI. Read the original in French.
The second-to-last part of my talk at Que Du Web 2017 in Deauville.
Here we explore an algorithm that comes out of graph theory and can do automatic keyword extraction, as well as automatic article summaries.
(See the overview of the talk with all the episodes)
The matching slides:
The transcript (summarized and simplified)
So far we’ve seen the parallel between a website and a graph.
Between the bridges of Königsberg and a graph.
But those are a bit too obvious, we can do more, and I’m going to tell you about TextRank.
Now careful: whatever it may look like, whatever similarities you might find or imagine, this is not, and has nothing to do with, the concept of metamots.
Here’s the beginning of the Wikipedia article on “SEO”.
. . .
And I promise you, I see a graph in there.
So you’re probably going to ask me:
Where’s Waldo? (in France he goes by Charlie)
No, that’s not the right question.
That one’s too easy, because Charlie was in Deauville for #QueDuWeb, of course!
(a little wink to @LydiaArzour)
Want to see the graph? Here’s how it works (I’ve simplified it, I hope the purists will forgive me).
In this text, you can see I’ve highlighted a few words (normally you’d take every word into account), and the words themselves are going to be the nodes of our graph.
then what we do is take each sentence one by one, and link the words that show up in the same sentence.
For example here, “search”, “engine” and “website”, which appear in the same sentence.
We create our nodes and link them.
We take the next sentence: “content” is a new word. We add that word and link it.
We carry on with the next sentence, giving more weight to the relations we come across again (in bold on the graph), and so on.
So here, we’ve just turned the text into a graph.
On that basis, we can run…
…a little PageRank-style calculation, and give each word a weight based on its links to the others.
Now of course, here I’ve oversimplified wildly with just a handful of words, but here’s the “real” resulting graph:
Very pretty, but what on earth can we do with that???
We can, for example, look at the most important terms.
And these are NOT the most frequent terms, the most repeated ones; it has nothing to do with TF.IDF, for instance. They’re rather the terms most “connected” to the others.
We’ve encoded a lot more information than in a “bag of words” model.
Incidentally, you can guess at a certain bias in the article, since one essential term is missing from these “important” words.
Yep, links.
But actually, the graph itself doesn’t matter much to us here, since it’s just an intermediate step to compute the weight of each term.
To do things properly, we can then glue back together the words that always show up together, and we end up with a list of words ranked by importance.
We’ve extracted the most important keywords with no training, no reference corpus, no assumptions about the language, nothing but the text itself.
With a small variant, where the nodes are sentences rather than words, we can cook up something similar on the text and pull out the most significant sentences.
And we get an automatic summary of an article.
The kind of thing that can come in handy, rather than grabbing the first lines of a text, to cut down on duplicate content on a site…
There you go. Now, if you want something more actionable, more concrete, do what @Julien_Gadanho did: the right Google search, something like
github textrank
and you’ll find several libraries and examples, in your language of choice 🙂
Now all you have to do is try it. See you next week for the conclusion!