0:00

[MUSIC]

Hi there.

In this lecture, we're going to see some very interesting and

cool properties of networks or graphs as you have seen them.

So before we get started, a few definitions again.

What is a network or a graph?

A network or a graph are synonyms by the way.

So a network or a graph has vertices or nodes.

For instance, in the Facebook graph, each user is a vertex.

In the Internet graph, each router or switch is a vertex.

There are edges that connect pairs of vertices.

In the Facebook graph, a friend relationship between you and

one of your friends is an edge.

Similarly, in the Internet graph, the link joining to

switches in the Internet constitute an edge in that graph.

0:50

So there are networks of graphs all around us.

The Internet of course is one of the largest networks that we use.

The World Wide Web is a network where the vertices are webpages and

the edges joining them are links that point from one web page to another.

This is often called the directed graph as the edges are uni directional.

They're also social networks such as Facebook, Twitter and LinkedIn,

which are all networks where the users are vertices, and the friend relationships or

the connections are edges.

And of course a biological graph such as DNA interaction graphs,

ecosystem graphs, and of course all of these are networks, as well.

So there's a variety of networks and all these networks are fairly complex.

They have different kinds of complexities.

The first kind of complexity is structural complexity.

For instance, the human social network has about 7 billion.

That's a number of people alive in the world as of this year 2014.

There are millions of computers on the Internet.

The graphs, or the networks, as a result of

these large numbers of vertices are also structurally very, very complex.

2:25

There's a lot of diversity even inside any one of these graphs.

Inside the human social network for instance, some folks are more popular than

others, so they might have more friends than others.

In the World Wide Web, some websites may have many more links than others,

they have many more links pointing to them than other websites do.

For instance, the BBC website has many more links pointing

to it than your or my personal homepage does, likely.

And of course, the vertices in these networks are fairly complex.

In the Internet graph, the endpoints, the routers and

switches have different kinds of CPUs, they're running different kinds of OSs.

And these OSs themselves have a lot of complexity.

And of course human beings in the human social network are very

complex individuals as well.

3:14

And even though you might be able to represent each of these vertices by a few

simple rules, when you put a large number of these vertices together in a network,

you get some very complex, global behaviors.

These are often called as emergent phenomena.

So, even from simple end vertex behavior, and end edge behavior, which

are governed by simple rules, you might get very complex system-wide behavior.

One of the best examples of this is climate change.

So, you could represent climate change as a network,

where the weather is different points on the globe.

And the edges are causatical relationships between them.

And really we do understand all the basics of climate change, for

instance, wind flows from high pressure to low pressure.

The rainfall happens when there's lower pressure and so on and so forth.

And yet, weather, it's kind of hard to predict, and that's precisely because it's

an example of an emergent phenomenon where even though you know the simple rules,

you aren't necessarily able to predict the emergent global behaviors when

you put all of these tools together in a very large complex system.

4:18

So, these networks have a lot of structure in the sense that many of these networks,

you are able to reach one node from another in just a few hops.

For instance, there is this well known myth, actually almost a fact,

known as six degrees of Kevin Bacon.

In this case, if you draw the actor graph, if you use the Internet Movie Database,

IMDB, and if you represent each actor or actress by a vertex in the graph, and

an edge joining two actors if those actors have acted together in at least one movie,

then it can be shown that any actor can be reached from Kevin Bacon,

the word extrapolated into Kevin Bacon within six hops.

You can take just six jumps, one over each edge,

and reach any actor from Kevin Bacon.

Milgram, a researcher assigned to research at Stanford,

did an experiment in the 1970s which showed that the human social

network separates any pair of human beings with just a few edges.

Typically, it's, again, only six degrees of separation,

where there are an expected number of six hops between any two

individuals in the world, no matter how far or how unrelated they happen to be.

And so the actor network, the human network, and

also other networks such as the World Wide Web, the human social networks that

are in real online social networks such as Facebook, Twitter, and LinkedIn,

peer-to-peer overlays, electric power grids, protein networks.

A lot of these shared this common characteristics,

where you can reach any node from any other node within just a few hops.

Just six hops or so.

So, why is this?

5:53

We should be wondering why this is.

And one of the common characteristics among all these networks is that they

evolve naturally.

It's not been the case that someone has come along and said,

hey here's how the network is going to be, now and forever.

Instead these networks started small and then they evolved over time.

All of these, whether it's the World Wide Web,

whether it's a human social network or whether it's the electric power grid,

they evolved, whether it's evolution over a few years or over a few decades.

And in the case of Facebook or in the case of the electric power grid, or

as in the case of human social network, evolution over many, many centuries and

millennia.

A lot of these are small world networks.

Here I'm introducing a new term, a very interesting and

very popular term called small world networks.

We need to see exactly what they are.

6:37

Before we see small world networks,

let's see two important matrix that we can use to characterize networks.

They are called clustering coefficient and path length.

Let's do the path length first.

The path length is something that you've already seen so far in our discussion.

Path length essentially is, if you take any pair of vertices in the graph,

you take the shortest path in between them,

the shortest number of vertices you need to jump from one to reach the other.

That's the path length of that vertex pair.

You calculate this path length for every pair of vertices and

you take the average among them, that's the path length of the entire graph, or

the average path length in that graph or network.

7:11

So the longer the path length is, the more spread out the network is, in a sense.

And the shorter the path length is, the more clustered the network is.

But clustering is captured by a different metric, known as a clustering coefficient,

also abbreviated as CC.

This defines something like the following, given three word, this is A, B, and C.

If there's an edge between A and C, given an edge between A and C, and

given an edge between C and B.

That is A and B are common neighbors at C.

What is the probability that A and B are also connected to each other?

In other words, C has two friends, A and B.

What is the probability that C's two friends are also friends of each other?

That is a clustering coefficient.

This is a probability, so it has values between zero and one.

If the values is zero,

then it means essentially this is a very highly unclustered graph.

For instance, tree networks have a clustering coefficient of zero.

However, if it has a clustering coefficient of 1.0,

the highest value possible, then it means that this is a highly clustered network.

For instance, a complete graph where every vertex is joined every other

vertex is an example of a graph that has a 1.0 clustering coefficient.

But different graphs lie different points on the spectrum of clustering coefficient

and path length.

First, if you take the ring graph, the graph that you have seen when we

discussed a peer to peer systems and distributed hash tables before.

You did the ring graph and you add a few successors and predecessors to each

vortex, you got a graph that has a very high clustering coefficient.

Because if you have two neighbors, they're likely also to be neighbors of each other

because they're likely to be successor and predecessor as well, but

it has very long paths.

If you have n vertices in your network, then the paths are on average n in length.

On the other hand, if you draw a random graph where the edges are added

between random pairs of vertices, this can be shown to have a very low clustering

coefficient, but it has really short paths.

So the paths in between any pair of orders are very short in general.

So ideally, you know what we are used to in the human social network is high

clustering coefficient.

The fact that two of your friends are also likely to know each other, but also very

short paths as we have discussed from Milgram's experiments and the 60 degrees

of separation that you can reach any other human being within just a few hops.

That is what is characterized by the small world networks,

which have a high clustering coefficient and short paths.

9:27

So, the reason I discuss the extended ring graph and

the random graph is that you can actually show how to read some types of small world

networks by using these two types of graphs.

Specifically, you take an extended ring graph which has very structured edges and

you take one edge at a time and you make their edge point to random notes.

Okay, so you don't change the number of edges, but you take one edge at a time and

make it point across random pairs of notes.

What happens as a result of doing that is that, eventually,

you have changed all the edges to being random, you get to a random graph, right?

So, you go from an extended ring graph to a random graph, and a result,

the clustering coefficient, which is very high for extended ring graphs,

falls to very low for random graphs, and the path length also reaches very high for

extended ring graphs also falls to be very low for random graphs.

But these two things, the clustering coefficient and path length,

don't fall at the same rate.

In fact, the clustering coefficient falls much slower.

It stays stable for much longer as you move from the ring graph to

random graph while the path length falls very quickly.

In other words,

if you change just a few edges in your extended ring graph to be random edges,

the path length falls very quickly because now a lot of the sharp paths will grow by

these random edges because they join very disparate portions of the graph.

10:34

So you get these region of networks in between the ring graphs and the random

graphs which have a very high clustering coefficient as high as an extended ring

graphs but have a very short path length almost has low as random graphs.

And that is the region of small world networks.

Once again, this is not all the small world networks that exist.

This is one particular class of small world networks that exist.

But essentially, this is a way of deriving small world networks which have this

high clustering coefficient and short path length characteristic as we are used to

in the separation and in the human social network.

So small world networks are all around us.

The network of actors is a small world network.

The network of humans is a small world network.

All online social networks such as Facebook, Twitter,

LinkedIn are small world networks.

Many of them have been shown by measurements to be small world networks.

And the co-authorship network where vertices are researchers and

edges between researchers, joint researchers have co-authored at least one

paper together is an example of a small world network.

In fact, there is number where that between

a famous scientist and you in the correlation network.

The worldwide Internet, all of these are examples of small word

which have a very high coefficient, and yet have a very short.

And many of these networks have grown incrementally, and in fact,

they can be modeled by using a preferential model of growth where you

add vertices sequentially or.

When you add a vertex to a graph, you add some edges and you add from an existing

vertex v with a probability proportional to the number of neighbors of v.

So the number of neighbors of v already has is proportional to

the probability with which v will be added to the newly added vertex.

So if you use the you can actually show that you end up with small word networks.

12:30

So we've discussed small world networks and we discussed it a little bit.

Let's change that a little bit and we'll come back to small world networks.

Let's change that a little bit and discuss degree.

The degree of a given vertex in a graph or

a network is essentially the number immediate one hop neighbors.

So if a vertex has three edges, then its degree is three.

So the degree distribution in a network or

a graph is the probability that a given node has k edges.

There are different kinds of degree distributions.

You can have a regular graph where all the nodes have exactly identical degrees or

Gaussian distribution.

Or you can have a random graph with an exponential

distribution where the probability that

the vertex have k edges is e power minus k x c where c is a constant, some constant.

And, of course, you have a power log graph which says that the probability that you

have a k edges incident on you as a vertex is proportional to k power

minus alpha where alpha is a constant.

This is a very interesting distribution, because when k is pretty small, like one,

two or three, this probability is very high.

But as k increases, this probability drops off very quickly.

So there's a very large number of vertices that have very low degrees, but

there are a few vertices that have very high degrees as well.

So how do you represent this?

Well, this can be represented by what is known as the log plot.

This is a well-known plot.

Here, you represent the no degree on the exact sys, instead,

what you plug is the logarithm of the node degree.

So you notice that the values of node degree go exponentially up, 1, 10,

100, 1000, rather than 1, 10, 20, and 30.

And on the Y axis, you plug the number of nodes that actually have that node degree.

For instance, if the point is X axis equals 1 and Y axis equals 1M,

it means 1M vertices in this graph.

14:32

Okay, so a very large numbers.

We have very small degrees in the top left portion of the curve but

some also have very high degree and

these are the high degree work presents in any power law graphs.

The exponential graphs is not a straight line.

It's curve at its head, the top left portion of the plot.

And it's also curved at its tail, the bottom right portion of the plot.

And also some distributions which are heavy tailed distributions

which are straight downward sloping at their tail, the bottom right portion, but

they are not necessarily heavy headed which is top left portion.

Okay, so they're almost like power law graphs in the sense that they have some

vertices that have a very high degree, but

they don't have that many vertices with a low enough degree as a power law graphs.

15:19

So this log node plot is the best way for you to distinguish when a particular

graph, or when a particular network is either power law, or heavy tailed, or

exponential, or something else.

You draw the log node plot.

If we'd just trade down your sloping line, it's the power law graph.

If it has a heavy tail, if it has straight tail, that's heavy tailed.

And otherwise, it is some other distribution.

So a lot of small world networks are also power law graphs.

For instance, the internet backbone graph, the telephone call graph,

protein networks, the worldwide world graph is, in fact, a small-world graph.

And also, power law graph has a value of alpha equals somewhere between 2.1 and

2.4, remember that.

You have in our power law graph a degree of

with probable deeper version of they key minus alpha.

The Gnutella p2p system has a heavy-tailed degree distribution.

It's not necessarily power law but it is heavy tail, so

it has a straight downward sloping tail in the log log point.

Power law networks are often called a scale-free networks, for instance,

in Gnutella, you have about 3.4 edges per vertex independent of

the number of vertices that are present in your network or in your graph.

But then, not all small world networks are power-law graphs and vice versa.

For instance, co-authorship networks are small world but

they're not necessarily power-law.

And also, not all power-law graphs are small-world.

You can generate power-law networks using the data distribution,

where you have disconnected components of the graph, where they're not necessarily

reachable from each other and so the graph is not a small-world network.

But many small world networks are in fact power-law graphs as far as you find them

in reality, and because a lot of these graphs,

a small world and power-law, their resilience comes into question.

Most nodes have a small degree in these graphs, but

a few nodes have a very high degree in these graphs.

So if you launch an attack on one of these graphs, if the attack is random, for

instance, you kill a very large number of randomly chosen nodes,

this will not disconnect the graph, okay?

This is why attacking a power-law small world graph randomly is not really

effective at all.

But if you target some of these very high degree nodes in the power-law

small world graph, this has a much higher chance of disconnecting the graph, okay?

And this is essentially why, in the human body for

instance, because the graph of proteins in the human body or chemicals in

the human body is a small world network and also a power-law network,

a few of the nutrients are very high degree nodes in the graph.

So, essentially edges in this protein graph,

edges are joined to chemicals that react with each other.

And so some nutrients happen to have a much higher degree than

other nutrients because they react with a lot of other chemicals in the body.

And these nutrients are essentially, the vitamins in the human body,

the minerals that the human body acquires like calcium and potassium.

So, if you have a shortage of any of these vitamins or nutrients in your body,

or minerals, your likely to be in trouble.

But if you have a shortage of some of these other random chemicals that

are there in your human body,

then it's not likely that you're going to be affected all that much.

Similarly, networks like the internet as well as the electric power grid,

if you target a few high degree vertices, that's much more likely to disconnect

the graph and cause a partition, and cause outages in the network.

But if you target randomly chosen vertices,

that's not likely to have any effect on the network itself.

18:36

What about routing in these networks such as the Internet?

If you build shortest-path routes between every pair of vertices,

it turns out that in small-world power-law networks, most of these

shortest-path routes will pass through some high-degree vertices in the graphs.

So these high degree vertices get highly overloaded with these shortest paths and

they're likely to suffer congestions and perhaps, in fact, even crash.

As we have seen from the previous slide, if you disconnect some of these

high-degree vertices, it's also likely that the entire graph would be

disconnected and you might have an outage in the network.

So this should tell you why there are these frequent outages in

networks such as the internet, in networks such as the electric power grid.

It's because these high-degree vertices suffer congestion and

they might crash as a result of that, and because when they do,

they disconnect large portions of the graph and end up having an outage.

19:52

To wrap up our discussion of structure of networks, the networks are all around us,

both man-made networks, such as the internet, the World Wide Web and peer2peer

networks, as well as natural networks that have evolved over centuries and

millennias such as protein networks and the human social network.

Yet a lot of these networks have common characteristics.

Many of them are small world networks that have a very high clustering coefficient

and very short path lengths.

And there's also power-law where you have a very large number of vertices that have

a small degree, but some vertices have very high degrees.

And it's useful to know these characteristics because when you design

distributed systems and

distributed protocols that run over networks like the internet, that run over,

that be with social networks such as online social networks.

It's useful to know these characteristics so

that you know exactly how your protocol is going to behave when it sends packets,

when it sends messages over these networks, or when you run a graph

processing algorithm that is dealing with such power-law graphs.

So you can better predict how your distributed system is going to behave

when it runs over small-world networks, such as the internet.

[MUSIC]