In this subunit
we will go over some of the
terminology used in the study of
networks.
We've already talked about
nodes and links, those are the main
components of networks.
A new term is the degree of a node;
this is the number of links coming into a node
or going out of a node.
So for example, this node here
has degree of 1 , because
there is only one link emanating from it,
where as this node has degree 2, since it has
2 links coming out of it.
Similarly this node has degree 2 and
this node has degree 3.
Now links can be either undirected or directed.
This networks shows undirected links;
this could be something like Facebook frienship links
where if you are friend with another person
they are automatically friend with you.
On the other hand, if you follow
someone on Twitter, that does not
necessarily mean that they also follow you.
So these would be directed links, where the arrow
indicates the arrow of direction.
So this might be me following somebody else on Twitter,
but that other person does not follow me.
So similar to the notion of degree,
in a directed graph, or network,
we would have the notion of in-degree,
which is the number of links coming into a node,
and out-degree, the number of links that are going out of a node.
So this node here has an in-degree of 0, no links coming into it,
and out-degree of 1.
Similarly, this one has an in-degree of 3, 3 links coming into it,
and an out degree of 1, and so on.
Now let me introduce the concept of a degree distribution of a network.
A degree distribution, here I am plotting it; it shows for each possible degree,
the number of nodes in the network that has that degree.
For example, this node has degree 1
and it is the only node that has degree 1.
So we have a bar that goes up to 1 here.
There is 2 nodes that have degree 2, and
1 node that has degree 3.
If this was a directed network then we would have
the in-degree distribution and the out-degree distribution.
So degree distribution can be represented as a plot,
in which the horizontal axis has degrees,
and the vertical axis has the frequency of
those degrees in the network.
Here is a little more complicated example;
this is from my book "Complexity; A Guided Tour",
where I show a little bit of my own social network.
Here is me,
and some of my friends,
some of my friends are also friends.
Here a list a degree distribution for this network.
There is a lot of nodes in this network that have
very low degree, for instance 1, and a very small number, namely one here,
myself, that has a high degree.
That's because the graph is rather Melany' o centric!
Here we see a very typical kind of distribution
which there is many individuals with low degree,
and few individuals with high degree.
Now let's look at the notion of distance and paths in the network.
When one node can reach another node
via one link, we call that a hop;
so you can hop from this node to this node in one link.
So we have connections of hops, sequence of hops,
which produce a path! So a path from this node here
to this node here, goes over 3 hops.
But that is not the only path, of course,
we can find a shorter path,
from this node to this node
that goes through this middle node
of 2 hops, and in fact this is the shortest path
in the network from this node to this node.
And we can define the distance between two nodes,
A and B, as the number of hops in the shortest path
between A and B.
We will stop here for a quick quizz on these various concepts.