0:58

So the application of a modelling of network modeling

Â of complex systems started in 1736 by Euller who used

Â the newfound field of graph theory mathematics

Â to prove the seven bridges of Konigsberg problem.

Â A lot of advancement in graph theory and

Â application of network analysis in complex systems was made by

Â those two Hungarian mathematicians,

Â A Paul Erdos and Alfred Renyi in the late 50s.

Â What they did is to study the properties of random networks.

Â So their famous random network model placed some

Â buttons on the table and then connected those buttons with random connections.

Â And they tried to understand the properties of those networks,

Â of those graphs.

Â And one of the properties is that nodes in those graphs have an average connectivity,

Â 2:10

and that connectivity distribution if you plot the number of connections per node.

Â And the frequency of nodes having a specific number of connections,

Â it follow a Poisson distribution, which is similar to the normal distribution.

Â It's a bell-shaped curve distribution.

Â Erdos and Renyi were also famous for proving the problem of,

Â how many colors would you need in order to distinctly color states on a map?

Â So in the late 90s there were two seminal

Â publications that really made a huge impact on this

Â idea of applying network analysis to real world complex systems.

Â And first the paper was published in nature by Steve Strogatz and Duncan Watts.

Â And what they showed is that real world systems follow this Small World topology.

Â So what does that mean?

Â And this actually has a very specific mathematical definition.

Â So real world networks are not random or not like the erostainiant model networks.

Â The actually have these properties where they have high clustering coefficient and

Â relatively short characteristic path length.

Â 3:32

So, those are two network properties that can measure the levels clustering and

Â the average distance between pairs of nodes.

Â So, as Stevens struggled and

Â Duncan Watts analyze three complex systems abstracted to networks.

Â One is the Movie Actor database IMDB.

Â They also analyze the power grid system that

Â lists transformers and generators and

Â also they analyze the normal connectivity map of the warm C elegans.

Â Where this worm is the only organism that we mapped its entire neuronal connectivity

Â system or has 200 neurons that we know exactly how they're connecting.

Â So as you see, they compared the actual L, which is the characteristic path

Â length to the L that is expected for random networks of the same size,

Â as well as the C, which is the clustering coefficient, and compare that

Â to the clustering coefficient expected in random network of the same size.

Â So how do you compute the clustering coefficient and

Â the characteristic path length?

Â So the computer clustering coefficient or what the clustering coefficient means

Â is it's a measure of how the neighbors are a known or connection.

Â A direct neighbor of a node or connected.

Â And in this particular example you can see that the red

Â node has four neighbors and in the first example on the clustering

Â coefficient nodes C=1, all of the neighbors are connected.

Â So there are six possible connections that those four nodes can be connected.

Â And the first example on the left, all of the are implemented.

Â 6:20

So in this model I started with a regular lattice and then gradually randomized

Â the connections, taking a link, and then putting it somewhere else.

Â So they extract it, one of those links, and then gradually randomize the network.

Â So if you do that process starting with this regular lattice, going all the way to

Â random network, somewhere in the middle you're going to get a Small-World Network.

Â So what they then as they go through this process of randomizing

Â those links from the regular lattice to the completely random network,

Â they can do a measurement of the clustering coefficient and

Â a characteristic path name that every few steps.

Â And what they found is like, somewhere in the middle you still are retaining

Â the high clustering while your path lengths drops very rapidly and

Â this explains, or fits, the real world topology.

Â So just, think there are shortcuts in real-world networks,

Â that connect modules that are highly clustered.

Â So in this paper that was published in Science in 1999, Albert and

Â Barabasi noticed, is that real-world network connectivity distribution is not

Â like the Pearson Distribution that was reported by Erdos and Renyi in 1959.

Â It's actually following a power law distribution.

Â A power law, so

Â the connectivity distribution has a power law density distribution histogram.

Â And this is what is shown here.

Â And then they also, like Watts and Strogatz,

Â they had a model that can generate those power law

Â distributed networks that they called Scale Free Networks.

Â So, let's look at how the model works.

Â Instead of starting with all the nodes and

Â all the links, and gradually shuffling the links.

Â The Rich-Get-Richer model, network growth model, is can

Â generate scale free networks, or networks that have a parallel distribution,

Â starts with very few nodes that are randomly connected.

Â So here, we have an example of five nodes.

Â With some random links that connect.

Â Then you start adding nodes and links to the system.

Â So your introducing nodes,

Â growing the network in size until it reaches your desired size.

Â And that growth model has some basic rules of how the node,

Â the new node, that is introduced to the network.

Â Will be connected to those other nodes.

Â If we are interested in generating an [INAUDIBLE] connected

Â network we will just randomly connect a new node and just grow

Â the network by adding nodes and randomly connect those nodes to the network.

Â However with the Rich- Get- Richer model we are connecting the new incoming nodes

Â by assigning a probability for each node to be connected to the new node

Â based on the nodes already existing connectivity degree.

Â One of the things that Barabosi showed is the importance of hub nodes.

Â Most of the nobs in the network have very few connections, either one or

Â two connections.

Â And then there are those highly connected nodes that although there

Â are not that many of them, compare to the the lowly connected nodes.

Â There is a lot more of these hubs compared to the hubs that

Â 9:52

you can find in an network.

Â And those hubs are important components in the network.

Â If you destroy those hubs obviously the network will fall apart faster.

Â And what they showed in this two papers that were published in Nature.

Â Is that when you knock down genes that are highly connected,

Â you the viability of the organism is going to be

Â much lower than if you would have knocked down genes at their lowly connections.

Â So in this review article that Barabasi wrote many years ago,

Â he compared the view of a random network to a scale-free network.

Â One of the criticisms about the scale-free model is that when you look at many

Â complex systems, you see those power law distributions a lot.

Â This is because complex systems are made of diverse components, diverse agents.

Â And those different types of agents will have different properties,

Â when you are comparing a lot of things that are different, that are diverse,

Â heterogeneous.

Â Then you will get those parallel distributions.

Â So this is not necessarily, or at least the proponents,

Â the opponents of the scale-free model suggest that this is not necessarily

Â a feature of the structure of the system by design but

Â just because we are looking at a very diverse system.

Â If you compare people's height you won't get a bell shaped curve distribution.

Â However, if you compare all animal's height and weight you will

Â probably get a power law because you are comparing so many diverse things.

Â So now I'm going to turn my camera around and I'll show you what I'm looking at.

Â And this is the North part of New York City in Manhattan.

Â And you can see that there are many buildings of many different heights

Â that I'm looking at.

Â And in this particular case, if you would've just plotted the distribution of

Â the height of those buildings, you probably also would

Â obtain a parallel distributions, because those buildings are very different.

Â But if you only picked a specific type of building, or

Â only the five floor buildings, or the.

Â You'll see that then you can obtain a normal, you can see that you can obtain

Â a bell shaped curve distribution, and not necessarily a parallel distribution.

Â One thing that to keep in mind about, the scale free distribution

Â is that there is sometimes a drop in the hubs.

Â So the hubs you cannot find infinitely large hubs.

Â So although the power log curve would suggest that there are very large hubs,

Â sometimes we see a drop in the size of hubs.

Â And this can be explained by two mechanisms.

Â So for an interesting paper that came after the publications of Albert and

Â Barbossi suggested an explanation for that drop in distribution of hubs and

Â the tale of the scaled free distribution.

Â And this, like the building that we just looked at,

Â suggests that there could be some type of a limit of how tall a building can be.

Â They modeled two types of mechanisms that can explain this drop of the tail

Â in the hubs and is one is suggesting that the hub nodes age.

Â And as they age they lose the capacity to accept new

Â links in the Rich-Get- Richer model.

Â Another one is that there is some type of a physical limit,

Â a maximum physical capacity for a hub to grow and

Â once it has reached that peak max physical capacity that hub will stop growing.

Â We will talk more later about other mechanism that can generate

Â scale free networks.

Â [MUSIC]

Â