Placeholder Image

Subtitles section Play video

  • [MUSIC]

  • My pleasure to introduce to you professor Remco van der Hofstad.

  • Actually I met Ramco in Brasil.

  • That's how we met first time.

  • But I heard about many of his great work.

  • Ramco is professor of probability at Eindhoven University.

  • He's doing a lot of work in the stochastic networks.

  • And you'll hear something today.

  • Ramco won many beautiful prizes.

  • Among other, Prix Henri Poincare, 2003, and Rolo Davidson in 2007.

  • He's also the director of EURANDOM, but

  • today he will be talking about structure of complex networks.

  • Small worth and scale-free random graphs.

  • Ramco, please. >> Thank you very much, and thank you for

  • the kind introduction.

  • So I'm a probabilist, working from the math department.

  • I'm interacting as well with engineers with various different backgrounds.

  • I'll be giving a talk that hopefully is at a relatively high level.

  • If there's anything that I'm saying that is unclear to you,

  • do ask because I'm giving this talk for you guys, and not for myself.

  • I'm supposed to know what I'm talking about.

  • Let's see whether that's indeed true.

  • And what I'll be talking about is structures of complex networks.

  • And this is very long line of research that we've been seeing all over the world.

  • Basically starting slightly before 2000, and

  • all of the empirical observation that have been found,

  • we'll discuss some of those as well, and then all of the efforts in modeling and

  • driving consequences of the observed phenomena.

  • And that's what I'll talking about today, all right.

  • Complex networks.

  • Here are two examples, certainly the one on the left

  • is a very famous one from a paper of Balabassi and others.

  • And this is a picture about

  • the interactions that exist between proteins in a yeast cell.

  • So first of all, there is quite a few proteins as you can see.

  • And there's quite a few interactions between them as well.

  • And the interactions come in different forms.

  • It could be that two proteins together form a third protein.

  • But it could also be that certain proteins act as catalysts for

  • reactions that others are being involved in.

  • So the edges here can really signify lots of different biological interactions.

  • And you can imagine that producing a picture like this

  • is an enormous amount of work in biology, because you've gotta figure out what all

  • of the different reactions are that are taking place in one of these yeast cells.

  • And one of the things we see is that it's a fairly complex picture, and

  • that's my very informal definition of what a complex network is.

  • It consists of many entities and

  • their many connections between them and it's pretty complex.

  • I don't think that there's any better definition of what a complex network is,

  • even though lots of people are using this terminology.

  • Now on the right, we see an artistic impression for

  • what the Internet Topology looks like in 2001.

  • I don't think that the artistic pictures are going to be changing a lot over time.

  • But again what you see is that, like here, we're on the outskirt,

  • you have things that are very loosely connected to the inside.

  • Which the inside being sort of a very highly connected bit,

  • sometimes called the core, certainly in Internet.

  • You see something very similar here.

  • Here, the connections are so dense that you can't even visualize them.

  • Whereas on the outskirts here, you see lots routers,

  • as we're talking about Internet here, that are only connected through one or

  • two links to the rest of the network.

  • Now, these networks come from completely different backgrounds.

  • And you can imagine that there's many more backgrounds to be observed.

  • Social networks, acquaintances, but also sexual relations, collaborations, etc.

  • Information networks, technological networks and biological networks.

  • So these networks come from various different backgrounds, so

  • it's actually quiet surprising that they share something.

  • And that's actually was one of the most profound empirical observations.

  • And many of these networks have things in common.

  • And that of course raises the question of whether these things that they

  • have in common are typical in such networks,

  • whether almost all of those networks have those properties, or

  • whether it is something very special, and if it's something very special,

  • what are the underlying principles that actually give rise to these properties?

  • So these are very broad questions in science.

  • I'm a humble mathematician, so we can certainly not answer all of those

  • questions for all of these different disciplines at the same time, but

  • it's just to indicate that network science is a very interdisciplinary field in which

  • lots of different communites look at their networks in their own different ways and

  • give rise to very interesting questions that are on the interplay with

  • mathematics.

  • And mathematicians can really say something sensible here and

  • we help these petitioners from different fields in answering their questions

  • All right, so very basic.

  • What are we talking about when we're talking about a network?

  • Well, in general, we're just talking about graphs, and

  • graphs consist of entities that are connected to one another.

  • So the entities are called vertices.

  • Sometimes nodes or sites, depending on the precise fuel that you're talking about.

  • And then you have connections between them.

  • And these are called edges, sometimes bonds, and

  • there's probably many more names for them.

  • And you should really think of these edges as being the building blocks of

  • the network.

  • They really indicate which vertices are interacting with which other vertex.

  • And you can think of an edge as being the building block of relational data.

  • Really think of an edge as indicating that there is some relation,

  • whatever the relation means, between the two vertices on the sides of the edge.

  • So that's what we are talking about here.

  • Now there's a lot of confusion about Internet and the World Wide Web, and

  • many people treat these two words as being exchangeable.

  • But they're really not.

  • They're really very different.

  • So when we're talking about the Internet,

  • we're really talking about the physical Internet.

  • So this means that there are routers, and

  • these routers are connected to one another by physical cables.

  • And that actually allows us to send emails, but

  • also to do our searches on the World Wide Web.

  • So that's what the Internet is.

  • Something physical, and therefore it's large, but it's not humongously large.

  • When we're talking about the World Wide Web, we're talking about something

  • which is much bigger because the vertices in the World Wide Web, or web pages, and

  • you connect two vertices with one another when there's a hyperlink between the two.

  • Now, we can build as many web pages as we wish, and there's

  • the estimates of how many web pages there are, are ranging in the trillions.

  • So this is a virtual object.

  • And it's much larger than the Internet as a physical system.

  • All right, but they're both manmade.

  • Now, what are some of the properties?

  • Well, if you think about the Internet, it's very large, it's chaotic.

  • Again, this word of a complex network, it's fairly complex.

  • Yet it's fairly homogeneous.

  • And there are studies about that.

  • So for example, if you look at the amount of connectivity,

  • let's say, within a continent.

  • And how many hops do you need in order to send the message between two sources

  • within a continent.

  • You don't really get a much different result compared to

  • the same question in the entire network.

  • So that's what I mean with it's fairly homogeneous.

  • Of course, it's also not quite homogeneous in the sense that

  • the routers that are there, some and certainly the cables that are there.

  • Some, of course, transport much more information than others.

  • So in that sense, it's not homogeneous at all.

  • It is connected by default because if the Internet would not be connected you would

  • not be able to communicate on it.

  • Now for the world wide web it's directed,

  • that makes a difference, it's much larger than the Internet by itself.

  • It's extremely hard to measure.

  • Just how the hell are we going to find, for example,

  • a uniform web page out of the collection of all web pages.

  • Well, even Google does not know all the web pages that are there.

  • The estimates are that Google probably knows about 50%,

  • maybe 60% of the web pages.

  • And the rest, it doesn't know.

  • I'll just give you an example of a part that probably not many people know about,

  • the dark web is an example.

  • And there's good reasons why people wanna keep the dark web dark, right?

  • So it doesn't wanna have Google accessing it.

  • So it's very difficult to measure.

  • There's no reason why it should be connected, and it isn't.

  • So it really is a completely different world between the two

  • networks, that are playing such a profound role in our lives.

  • So here's a very simplistic picture of what the web looks like.

  • So there is something called the strongly connected component.

  • So this consists of all the vertices for

  • which you can travel both ways between pairs of vertices.

  • Then there's all the stuff from which you can go to the strongly connected component

  • but not back.

  • There's all the stuff that you can reach from the strongly connected component.

  • But you cannot go back, and then there's all sorts of stuff in between.

  • So this is very simplistic sort of cartoon picture of what

  • the world wide web looks like.

  • And this is due to.

  • This is already quite a bit older,

  • which is also why these numbers are not that humongously large.

  • All right, so

  • I was already talking about the common features that these networks have.

  • And what are those?

  • Well the first is what physicists are calling the scale free property.

  • So scale free basically means that there's no typical scale.

  • Let's look at two different statistics which really are very different.

  • So if I look at the height of people in the Netherlands,

  • then this is pretty well concentrated.

  • So men on average are, I think, 185 in centimeters in the Netherlands.

  • I have no idea how much that is in feet and inches.

  • And if you add, let's say,

  • 20 centimeters on either side, you have the majority of people.

  • Now there are people who are quite a bit taller like up to 210 and so on, but

  • that it's really rare.

  • If you would add 40 centimeters you basically have everybody.

  • So you could say that 180 or 185 is the typical height of a Dutch man.

  • Now on the other hand if you look at incomes that's a completely different

  • order of magnitude.

  • So I've understood that the model income in the Netherlands is 35,000 Euro.

  • That's $45,000 US.

  • But you have tons of people who actually earn ten times as much.

  • Have some people who earn 100 times as much.

  • You have few people who actually earn 1000 times as much.

  • That would be like having a Dutch man who is 180 meters tall.

  • Right, so you can immediately feel that there is two different sets of data.

  • That are just not combinable, that are completely different.

  • So you have the normal world where actually normal approximations work

  • pretty well.

  • And then you have another world where you see heavy tilt behavior.

  • You see values that are much larger than you would expect.

  • Now, that's the kind of property that we see also for the degrees in networks.

  • We see huge amount of variability.

  • Even though the average degree may be something like three or four or ten.

  • It could be that the maximum degree is 10,000 or even 100,000,

  • orders of magnitude larger.

  • Now physicists are saying that this is related to

  • power law in the degree distribution.

  • There's a lot of debate about this.

  • There is also a recent paper about Claussette and

  • one of his students that actually debates that this is true.

  • So, there it is, this is very interesting discussion, which,

  • which probably is going to have all sorts of effects.

  • But nobody argues the fact that you have huge amount of variability in

  • the degree distributions as they are.

  • So, this is the Internet movie database.

  • It's a network at the time that we were.

  • Investigating it, it had size roughly a million.

  • And what you see is that there's there are individuals who have degree ten

  • to the power of five.

  • So that's pretty humongous.

  • And here we're talking about the Internet.

  • This picture looks much smoother,

  • that's because some sort of binning has taken place here.

  • That is consistent with it being a parallel.

  • This is a picture by Krioukov from Northeastern University.

  • And again here you see lots of variability.

  • The majority, because it's in log-log scale this picture, as you can see,

  • the majority of vertices is actually here.

  • Let's say 90% is here.

  • As is here 90% of the data is here.

  • But then on the right here you have very rare

  • individuals in this case actors that have a humongous degree.

  • And here you have on the right, very rare routers that have a humongous degree.

  • So that's what is called scale free.

  • It's not entirely obvious why it's called scale free.

  • You could say that it's called scale free because there is a parallel.

  • But you could also somehow more inefficiently argue that,