Temporal Networks, Where Page Rank meets Lord of the Rings - Computerphile

0:00 If I say to a computer file audience network,

0:03 probably their minds are going to go to Wi-Fi and Ethernet or whatever.

0:08 But there's another way to interpret network.

0:11 What a mathematician would call a graph.

0:15 Just anything that's connected.

0:18 So we can we can visualize loads of things as networks.

0:23 the connection between people who talk to each other,

0:27 people who are friends network.

0:30 Um, if we ask about everybody who's

0:33 ever made videos on the same YouTube channel,

0:35 we could construct that as a network, you know.

0:37 So, I'm now connected to all your other contributors.

0:41 This is where a lot of my researches

0:43 these days and I want to talk specifically about

0:45 the idea of temporal networks where we've got

0:49 a connection and the connection happens at a particular time.

0:56 Let's give a specific example.

0:57 Let's imagine we're thinking into the the murky world of cryptocurrency, right?

1:02 And um a lot of people are immediately going, "Oh, it's a scam, Richard.

1:07 You don't." Right?

1:08 I know.

1:09 All right.

1:10 But maybe the interesting question is it's what type of scam?

1:13 Maybe that's the interesting question.

1:14 So let's think about this as a network.

1:16 How do we form this into a network?

1:18 So let's imagine this represents wallet one.

1:22 So this is somebody with a wallet on a crypto network.

1:26 This is somebody else with a wallet.

1:28 This is somebody else with.

1:30 So they've got certain amount of money.

1:33 Why do we always draw dollars when we're in the UK?

1:35 Eh, it's just easier I think that people understand all around the world.

1:38 If I draw a pound sign, it's going to look a bit wonky.

1:41 So, these people are sending some money about the network.

1:44 So, here and I'm going to send them like

1:50 $10 and I'm going to send that at 9 a.m.

1:58 I'm going to send them $10.

2:02 I'm going to send that at 10 a.m.

2:08 Now, let's imagine now this crypto networks can

2:14 have a little bit fraud on them, maybe.

2:17 Let's imagine this person little bit dishonest.

2:20 They've stolen some money.

2:22 They also send $10 just to keep the example easy,

2:25 but they've sent it at 9:30 a.m.

2:29 So now we've got a network.

2:33 We can think of this, we can abstract this as some nodes and some links.

2:41 So a node and a link here and the links are annotated with time.

2:50 Why is that useful?

2:52 If we want to ask the question, so this person uh has stolen this money,

2:57 we want to ask where's this stolen money gone?

3:00 It was sent at 9:30.

3:04 It can't have gone this way cuz this links at 9.

3:07 It's a very very obvious um observation.

3:11 The money has not gone in this direction.

3:14 It's definitely gone in this direction.

3:15 But if we don't put time into the network, we can't really follow that.

3:20 We can't follow the path through the network.

3:21 And people do take pains to hide these things.

3:25 So they do make a lot of like the the shell game

3:28 you see here in London on uh on like um London Bridges.

3:32 You'll see somebody with you know three cups and a ball under it.

3:36 You know, they'll they'll move the money to try and disguise it.

3:39 But you can only follow it through these time respecting paths.

3:43 That's one of the reasons we like to study the temporal networks.

3:46 I'm going to talk very briefly.

3:49 I'm going to give you a motivating example.

3:52 Um, so you have got a video that covers this a little bit,

3:57 but it's it's really important.

3:59 So, it is worth going through again.

4:02 Do you recall something called page rank?

4:05 Maybe it's I'm putting you on the spot because that was a long time ago.

4:08 I I do remember page rank.

4:10 Is it about how Google used to choose what went to the top of the search?

4:13 Yeah.

4:14 Very, very good.

4:14 Very good.

4:14 Yeah.

4:15 It ranks pages.

4:16 Although, weirdly, it's named after Larry Page.

4:19 Oh, yeah.

4:20 One of the founders of Google.

4:21 Yes.

4:22 Yeah.

4:22 Um, mathematically, we study it as a Markoff chain.

4:25 I try and motivate my my students by saying Larry Page is

4:28 a multi-billionaire because he paid attention

4:30 to when somebody was teaching in Markoff chains.

4:32 While I'm teaching Markoff chains,

4:35 please carry on with Please listen.

4:38 Um, so I'm going to briefly show you

4:43 just recall page rank a little bit more detail.

4:46 Then we're going to go and look

4:48 at some software that deals with temporal networks.

4:51 The software is called Rafter.

4:53 R A P H T O R Y Ry.

4:57 And it was created by a PhD student of mine

5:00 several years ago and it's become pretty successful now.

5:03 So I really love this bit of software.

5:05 It's great for doing stuff with temporal graphs.

5:08 I'm not on the payroll, uh,

5:09 but it's something that I use in almost all of my research.

5:15 So, let's have a look at this page rank and see how it

5:18 works and then we'll go over to the computer and see it in action.

5:21 The task we have is how do we find the most important web page?

5:28 Cuz old school search engines were real bad.

5:30 Well, it was a list, wasn't it really?

5:32 It was kind of it was a list, but it wasn't particularly in any order, right?

5:36 So, you'd say, "Oh, give me a web page about computers." And it would go,

5:40 "All right, here's 50 web pages about computers." And, you know,

5:43 some of them would be real like, "Okay,

5:45 that that is 50 web pages about computers,

5:47 but look at the state of them." We need some way to say what's important.

5:55 So, let's imagine we've we've Google.

5:58 We try to search for um we'll try to search for something.

6:02 Want to put them in order.

6:04 Let's imagine you, me, and uh and Dr.

6:07 Mike, we've all got uh web pages.

6:09 So, MySpace or something?

6:11 Yeah.

6:11 My space if that is that still a thing?

6:16 I don't.

6:18 So, let's imagine There we go.

6:20 We've all got our little web pages.

6:22 Now, I'm only an academic.

6:24 I'm not getting a million hits to my web page.

6:26 But let's imagine I link to your web page cuz we

6:29 chat and we sometimes go to the pub and what have you.

6:32 And you link back to my web page and you link to Mike's web page.

6:38 Mike link back to yours and maybe I link to Mike's but actually

6:40 I've never met Mike so maybe he doesn't link back to mine.

6:43 And that forms a network.

6:45 We've now we've got a network or a graph structure.

6:48 Now name me a celebrity.

6:50 The Rock.

6:50 What about The Rock?

6:51 The Rock.

6:51 All right.

6:52 Brilliant.

6:52 Yeah.

6:52 Yeah.

6:53 Obviously, he's writing his own web page.

6:56 Uh, let's imagine.

6:57 So, we got the rock now.

6:59 Yeah.

7:00 So, he's working on his HTML.

7:02 Pops it up.

7:03 He got obviously I'm got a link to he's got a link to Mike, right?

7:07 He's a big fan of computer.

7:08 He links to Mike's, but he's got a million links incoming.

7:12 So, there's a big cloud of things here.

7:16 Maybe I've linked out to one of those.

7:19 So now when we decide who's the most important, we can say, okay,

7:23 the rock is is is real important because he's got loads and loads of links,

7:30 but Mike got a link from the rock.

7:33 So that's going to make him pretty important, right?

7:37 Because this this this high profile has um linked him.

7:44 So here's the model that page rank uses.

7:48 It's kind of a random clicks model.

7:51 I should actually say these are all the pages

7:54 about a certain now I've painted myself into a corner.

7:56 These are all the pages about a certain topic.

7:58 We're all fans of computer file and the rock watches computer file all the time.

8:01 It's like so where these are all people who list computer file

8:06 and the rock he doesn't like to talk about it too much

8:09 in public but he watches computer file all the time I happen to know.

8:12 So these are the web pages about computer file.

8:15 So now we want to decide what's important

8:17 and we use this this random clicking model.

8:20 So we assume that we're just kind of uh

8:23 it's not doom scrolling but we're just idly

8:26 browsing the web looking for people who um

8:31 who are on our list of computer file websites.

8:34 Right.

8:34 So we start off at Mike's maybe and actually

8:38 I've only draw so let's draw another link on here.

8:41 So, we go to Mike's and there's two he's got two links on his web page.

8:47 We'll just flip a coin, choose at random.

8:50 So, we choose to go that way to yours.

8:54 And again, random clicking.

8:56 So, we're just clicking with our mouse, following the links on the website.

9:00 Flip a coin.

9:01 You link to me.

9:02 You link back to Mike.

9:04 So, we're going to go to me.

9:06 I've got three links.

9:07 So, there's a 1/3 probability.

9:08 One/3 probability.

9:10 1/3 probability.

9:11 So, I'll go back to Mike maybe.

9:14 And we keep following this process of randomly flipping coins.

9:19 And then we ask the question, if we follow that process,

9:23 how much time do we spend on each of what

9:26 proportion of the time do we spend on Mike's,

9:30 Sean's, mine, or the Rock's website about computer file?

9:35 And if you've got loads of links in, you're going to get more time.

9:41 But if your link is from somebody with loads of links,

9:45 you're also going to get loads more links.

9:48 Mathematically, we can form that up as a model.

9:50 It's like a ratio thing, isn't it?

9:51 Yeah.

9:51 It's like a ratio of the time we

9:53 would spend if we follow this random clicks process.

9:57 So we can we can formally say that I've

10:00 drawn three links from the Richard web page.

10:04 So onethird of the time I go to Sean, oneird of the time go to Mike,

10:07 and one/ird of the time I go to whatever this one is over here.

10:11 And we can mathematically follow that, formulate

10:14 it as a markoff chain, and solve that.

10:16 And we're going to get something like, oh,

10:19 The Rock scores 0.3 and Mike scores 0.2 and me and you

10:25 only score 0.1 and everybody else on here gets some little score.

10:30 So he's like more important,

10:32 but he's still Mike's quite important cuz we got that link

10:35 and we're a bit less important cuz we've not got the link.

10:37 We've not got that major celebrity endorsement we're looking for.

10:41 It'll happen.

10:42 It will happen one day.

10:43 One day the probably watching this now.

10:46 Exactly.

10:46 Exactly.

10:48 Okay.

10:48 So, I haven't made that algorithm terribly formal,

10:52 but it's it's this is the the essence of it.

10:55 There's some little tweaks like what if you get stuck in a dead end.

10:58 But so what we're going to do now is look at this and ask

11:05 when is something most important and I'll show you how to do that.

11:09 But we've we've chopped the network up into time.

11:12 So let's get over to the computer and we we'll take a look.

11:15 Okay.

11:16 So if we've talked about the page rank algorithm,

11:20 but that wasn't temporal when we did it there.

11:23 wasn't changing in time.

11:25 So now I'm going to take an example network.

11:27 Um, and the example network we've chosen here is

11:31 actually it's quite an it's quite a cute one.

11:34 It's the network of Lord of the Rings.

11:42 Now I think the the project this comes out

11:44 of is called One Network to Rule Them All.

11:47 That's a great title, isn't it?

11:48 Lovely.

11:49 Um, so what they've done is they've done some natural language in processing

11:53 on the text of all the volumes of Lord of the Rings.

11:57 I'm going to say something wrong about Lord

11:59 of the Rings at some point in this video

12:00 because I haven't read it in 25 years and I've not even seen all the films.

12:05 But these people have done natural language processing on Lord of the Rings.

12:08 And every sentence where people appear together, we count that as a link.

12:14 Now what about time?

12:16 We're going to say the time is the order in which that's happened.

12:21 Right?

12:21 So for people who don't know the story,

12:24 they're a group of people on this epic quest and they they

12:28 they meet up and they split apart and this happens multiple times.

12:32 So like in this particular sentence,

12:35 uh the hobbits have met the elves because it was the early days.

12:39 The hobbits learned their letters and here's

12:42 Bilbo and Gandalf together in a sentence.

12:46 and it says Bilbo meets Gandalf and that's on sentence 13.

12:51 Now in some of these cases meets there's a little bit they've not really

12:55 because we're we're actually I think we're

12:56 in intro in introduction of the book here.

12:59 They're not actually meeting just happened to be in the same sentence.

13:02 If we go on later Frodo stripped the blankets from Pippen and rolled him over.

13:07 So Frodo and Pippen are clearly together right there.

13:11 So, we're going to do page rank to see

13:14 who's important in Lord of the Rings, right?

13:16 I say who's who's the the champion, right?

13:19 Who's the most important Lord of the Rings character?

13:22 Um, in terms of their social connections, right?

13:26 Their fame.

13:27 Who's the most famous Lord of the Rings person?

13:29 Is it is it Plucky Young Sanwise?

13:31 Is it uh is it Gandalf?

13:33 Whatever.

13:34 So, um here's my uh terrible Python code.

13:40 And I'm sure there's better ways of doing this.

13:42 Um, but we've got our text file here.

13:46 It's got a bunch of things in it,

13:48 but the main things I'm interested in are this column two and column 3.

13:51 And that's the the character and the character they're meeting.

13:55 We're just going to read that as a CSV commaepparated values file.

14:00 So I'm using the pandas library which pretty much everybody uses

14:03 Python's using but we're also rafter to read this this code

14:08 that my PhD student originated open source so please do have

14:13 a fiddle with it it is so useful for this kind

14:15 of thing and we're going to import that as RP and we're

14:19 just going to do the page rank algorithm on the whole

14:23 graph just everything right so shove that out there shove

14:27 the whole graph through But then we're gonna do some other playing.

14:32 So we're gonna get the top five.

14:34 Who's our best five Lords of the Ringsers?

14:37 And we're gonna focus on Gandalf and Frodo.

14:43 But then we're going to do something a bit more clever.

14:45 We're going to use this this concept of time

14:48 or in this case it's not precisely like a clock time.

14:52 We're using where

14:56 ordering.

14:55 Ordering.

14:56 Yeah.

14:56 Yeah.

14:56 Which is a form of time.

14:58 So I'm going to pretend the order that they meet up is a time

15:03 and I'm going to use the rafter software to split this up into a window.

15:08 So here's our just getting the page rank.

15:11 It'll call the rafter standard page rank algorithm.

15:14 But here now we're setting up

15:17 a list for Gandalf importance and Frodo importance.

15:23 And we're going to take this graph and push

15:25 it through a rolling window every 250 meetings.

15:29 Right?

15:30 So we're chopping the book up into 250 meeting cycles.

15:35 We're going to ask how Frodo and Gandalf evolve through the book.

15:42 And this is just some map plubbins to plot it all out.

15:47 So we're going to give a marker and a legend and what have you.

15:51 So let's just run that code.

15:55 Legendarily when I press run on these they

15:57 normally break but uh let's see how we're doing.

16:01 So we've loaded in the graph and we can see so this is our page rank

16:07 algorithm and it's telling us initially it's telling

16:10 us Gandalf ranks as 0.04 Frodo ranks as 0.06.

16:15 You know here's our our top five Lord of the Ringers.

16:17 are I don't know whether to announce it top of the pop style really.

16:20 Coming in at number five is Gimly.

16:23 A little unexpected actually for me that Gimly.

16:26 Well, is he's in it and he meets all the people, doesn't he?

16:28 I suppose

16:29 he does.

16:29 He's hanging about.

16:30 Is he Is he the one who has you have my axe?

16:33 Yes.

16:33 Yeah.

16:33 Yeah.

16:34 Very dangerous across short distances.

16:36 That's right.

16:36 Yeah.

16:36 You throw him across the chasm at Helms Deep.

16:39 So,

16:40 moving to number four, Gandalf.

16:42 Three, Pippen.

16:43 Aragon at number two, Strider, the the heroic ranger.

16:47 But number one, probably not unexpectedly Frodo.

16:50 But so this is the bit that I really like.

16:52 We can look at it over time

16:54 because there's huge chapters about various different characters.

16:58 All right.

16:58 So yeah.

16:58 So look at this.

16:59 At the start of the book, Gandalf's kind of there,

17:03 but he's just doing some firework displays.

17:05 They're messing around in the Shire.

17:07 Then Gandalf for some reason has a little holiday and he's not in it.

17:11 You remember?

17:12 Uh he's and they're all all hobbits are running about hiding from the ring race.

17:16 It's tremendously exciting.

17:18 Uh you know they're going towards um going to Riendell.

17:22 Riendell.

17:23 Thank you.

17:23 They're going to Riendell.

17:25 So Frodo and all this super team are hiding out.

17:29 It's all it's all Frodo all the time.

17:31 Meeting lots of people.

17:32 Meeting lots of people.

17:34 Meeting Tom Bombarded and uh all of that good team.

17:38 So early on in the book, lots of Frodo.

17:42 Um, not quite so much Gandalf.

17:44 He comes in, he he shows up a little bit now.

17:48 Then Balro doesn't go so well for Gandalf, right?

17:54 Yeah.

17:54 Spoil spoiler.

17:55 Oh god.

17:55 Yeah.

17:56 Spoiler alert.

17:58 You shall not pass.

18:02 Spoiler alert.

18:03 Fly, you fools, etc., etc., all of that.

18:06 So Gandalf then little bit of decline in importance then heroic uh

18:14 Gandalf the White comes back um has a fight with Peter Cushing.

18:18 Is it Peter Cushing?

18:20 Sarman.

18:20 Yeah.

18:20 Yeah.

18:20 Yeah.

18:21 Saramman.

18:21 Yes.

18:22 Um so then like a lot of Gandalf in there and now Gandalf actually in the later

18:28 bit of the book if we think about it in terms of what page rank is doing.

18:32 It's all about how you meet.

18:33 So I hated this bit as a child cuz Frodo and Sam

18:37 are just waving through a swamp for a long long time.

18:41 They're not meeting anybody apart, right?

18:43 The dead marshes, right?

18:45 So now if you think about their page rank,

18:47 they've not got a link to the rock or Taylor Swift or whatever.

18:50 They've got a link to Gollum and Gollum is not important.

18:54 So you know that photo is is is sunk

18:56 in the charts by the latest stage of the book.

18:58 Yeah.

18:59 Gandalf's like way ahead cuz he's off.

19:02 Is he Is he at Helms Deep?

19:03 Can we remember?

19:04 Uh yeah, he goes off to help the Rahan.

19:08 The Rohan.

19:09 Yeah, he's back flashing his staff about doing all that good stuff.

19:12 So Gandalf's later in the book,

19:13 Gandalf's actually well ahead of Frodo on his page rank algorithm.

19:18 He's um he's getting to the top of the Google searches there.

19:21 Um but then back to the end and I've got do the scouring of the Shire.

19:26 And so Frodo's like popped ahead and he's meeting all

19:28 the people again and he's he's back at the beginning.

19:32 Um and that's the kind of thing you can

19:34 see when you're treating these graphs as uh temporal graphs.

19:39 There's one last thing I'd like to show you cuz I want to show this software.

19:42 I'm so um proud of not my achievement.

19:46 Uh Ben Steer's achievement.

19:48 Oh, is it visualizing it?

19:49 Yes.

19:49 So, it's a nice little visualizer.

19:51 So, we can zoom in and pull out the various people and see who they link to.

19:56 So, here's Elron, your your like uh El

20:01 uh Chief or whatever it is, and there's Balon.

20:04 And we can pull out those nodes and see the connected.

20:07 Oh, Balon's not meeting Elon, but here's Frodo.

20:11 I'll tell you what that reminds me of.

20:12 A few years ago on number file they did a video on game books and they took

20:18 one of these choose your own style game

20:20 books and they turned it into a node graph.

20:22 Oh yeah.

20:22 Yeah.

20:22 So yeah that's perfect for this kind of graph thing and it

20:25 is time ordered because you can only go through that certain way.

20:28 Let's see if there's any surprises if we go further down.

20:31 So if I ask for the bottom people it will be people who you don't even remember.

20:37 Whoops.

20:37 Guard B.

20:38 Exactly.

20:39 Exactly.

20:40 Uh so uh get the top 50 and we'll look down and see if there's any surprises.

20:47 Um so uh here's our top 50.

20:52 So look, this is this is a toy fun example,

20:55 but we can use this for serious research.

20:58 Like we if we're thinking about those crypto networks,

21:02 we could ask the question, is there a sudden spike in popularity that makes

21:07 us think something is um something is suspicious?

21:12 Oh, right.

21:12 This suddenly this person who was doing nothing has now become

21:17 top of the pots and is the most important person on earth.

21:20 Why is that?

21:21 Or maybe if we're thinking about the old NFTts, which aren't so popular anymore.

21:27 When we looked at those, we could see them being traded

21:29 round and round in circles because people were swapping them between

21:33 each other in a little gang pumping up the price

21:35 and then dumping them later when they traded them between themselves enough.

21:39 Um, so while the Lord of the Rings example

21:43 is not the most serious thing I might have chosen,

21:47 actually this can be used for some real real important stuff like finding fraud,

21:52 looking into social networks, um,

21:57 looking into how people interact on social media.

22:00 Loads and loads of examples, use your information.

22:02 So this software rafter is is it's really great for looking into any

22:07 network where the thing changed in time and that's what you're interested in.

22:19 We've proved ourselves the world's worst

22:21 people to discuss celebrities I think today.

22:23 Um absolutely cuz it's not I got the wrong person the first Oh.

22:27 Um it's Christopher Lee.

22:28 Yes.

22:29 Not Peter Cushion.

22:30 And I think I you can see why I muddle them.

22:32 They're always fighting in films.

22:33 But no.

22:34 Right.

22:34 Okay.

22:34 Yes.

22:34 I think earlier I said Taylor Smith.

22:36 Taylor Smith.

22:37 Yeah.

22:38 That very famous singer.

22:40 We've not got We've not got our fingers

22:42 on the pulse of pop culture today, have we?

22:44 Now fight.