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.